Majority-Inverter Graph for FPGA Synthesis

In this paper, we present an FPGA synthesis flow based on Majority-Inverter Graph (MIG). An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. MIG manipulation is supported by a consistent algebraic framework leading to strong synthesis properties. We propose MIG optimization techniques targeting high-speed FPGA implementations. For this purpose, we reduce the depth of logic circuits via MIG algebraic transformations enabling denser LUT mapping on FPGAs. Experimental results show that our MIG-based design flow reduces by 21%, on average, the delay of the arithmetic circuits synthesized on a state-of-art 28nm commercial FPGA device, as compared to a commercial design flow.