Configuration Bitstream Reduction for SRAM-based FPGAs by Enumerating LUT Input Permutations

SRAM-based Field-Programmable Gate Arrays (FPGAs) are configured from off-chip memory through a serial link. Hence, a large configuration bit stream adversely increases off-chip memory size as well as bit stream loading time. The following work proposes a novel method to reduce the number of programming bits required for look-up tables (LUT), thereby reducing overall configuration bit stream size. Alternatively, the identified redundancy may be used to hide watermarking or security data. The proposed method does not affect the critical timing paths, nor does it affect the internal architecture of the LUT. The suggested method eliminates floor(log₂(k!)) configuration bits out of the 2^k configuration bits required by a k-input LUT (k-LUT). Hence, a 4-LUT, 5-LUT and 6-LUT only requires 12, 26, and 55 bits, respectively, to be stored in the external configuration bit stream, representing a reduction of 25%, 18.75%, and 14% in LUT configuration bits, respectively. Note the LUTs themselves still contain the full 16, 32, and 64 bits, respectively, but the missing bits are regenerated at bit stream load time. Furthermore, traditional loss less compression methods can still be employed on top of the proposed reduction technique.