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

2004 2004

Other formats: Order a copy

Abstract (summary)

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.)

Indexing (details)

Electrical engineering
0544: Electrical engineering
Identifier / keyword
Applied sciences; FPGA; Finite-field multipliers; Functionally decomposing
Functionally decomposing finite field multipliers for efficient implementation on field programmable gate arrays
Ahlquist, Gregory C.
Number of pages
Publication year
Degree date
School code
DAI-B 65/05, Dissertation Abstracts International
Place of publication
Ann Arbor
Country of publication
United States
Nelson, Brent E.
Brigham Young University
University location
United States -- Utah
Source type
Dissertations & Theses
Document type
Dissertation/thesis number
ProQuest document ID
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.
Document URL
Access the complete full text

You can get the full text of this document if it is part of your institution's ProQuest subscription.

Try one of the following:

  • Connect to ProQuest through your library network and search for the document from there.
  • Request the document from your library.
  • Go to the ProQuest login page and enter a ProQuest or My Research username / password.