Functionally decomposing finite field multipliers for efficient implementation on field programmable gate arrays

Finite field multipliers are key components of error control coding, cryptographic, and communication circuits yet they pose considerable challenges for functional decomposition algorithms. This is because the functional decompositions that lead to the best circuits cannot be achieved through simple partitions of the input literals nor through the numerous functional decompositions techniques based on trees or Binary Decision Diagrams (BDDs). Deriving efficient finite field multipliers circuits for FPGAs is important because they are a critical component in Reed-Solomon error control coding circuits which are in turn needed components of emerging systems such as Software Defined Radios (SDR) and dynamic cryptographic devices. Thus, developing logic synthesis algorithms to efficiently derive small and fast finite field multiplier circuits for FPGAs is a key step in the logic synthesis of larger systems with real-world applications.; This work presents five algorithms designed to produce FPGA-specific functional decompositions of finite field multiplier equations. Included in these algorithms is a table-based exhaustive search algorithm that uses information about the solution space to reduce the algorithm's run time. It is shown that this algorithm can derive optimal duplication-free functional decompositions in reasonable time for finite field multiplier of size up to and including GF(256). A second algorithm extends and improves the heuristic cube-packing functional decomposition approach. A third algorithm seeks to further reduce the finite field multiplier functional decomposition size by extracting common sub-expressions from the set of finite field multiplier equations. A fourth algorithm is presented that exploits specific characteristics of finite field multiplier equations to improve the results achieved by the common sub-expression extraction algorithm. A fifth algorithm is presented that is a variant of the XOR common sub-expression algorithm in that it considers only the specific case of FPGAs with 4-input logic blocks. Finally, the algorithms presented are combined into a logic synthesis system that derives the FPGA-specific functional decomposition for finite field multipliers for all finite fields of size up to and including GF(232) and for any desired logic block input size K. (Abstract shortened by UMI.)...