Efficient Decomposition Techniques for FPGAs

In this paper, we propose AND/XOR-based decomposition methods to implement parity prediction circuits efficiently in field programmable gate arrays (FPGAs). Due to the fixed size of the programmable blocks in an FPGA, decomposing a circuit into subcircuits with appropriate number of inputs can achieve excellent implementation efficiency. The typical EDA tools deal mainly with AND/OR expressions and therefore are quite inefficient for the parity prediction functions since parity prediction function is inherently based on AND/XOR in nature. The Davio expansion theorem is applied here to the technology mapping method for FPGA. We design three different approaches: (1) Direct Approach, (2) AND/XOR Direct, and (3) Proposed Davio Approach and conduct experiments using MCNC benchmark circuits to demonstrate the effectiveness of Proposed Davio Approach. We formulate the parity prediction circuits for the benchmark circuits. The Proposed Davio Approach is superior to the typical methods for parity prediction circuits in terms of the number of CLBs. The proposed Davio expansion approach, which is basedon AND/XOR expressions, is superior to the other common techniques in achieving realization efficiency. The proposed Davio approach only needs 21 CLBs for eight benchmark circuits. It takes only on average 2.75 CLBs or 20 % of the original area.