Majority-Inverter Graph (MIG)

A New Paradigm for Logic Optimization


Majority-Inverter Graph (MIG) is a promising data structure for logic optimization and synthesis recently introduced by [1]. An MIG is a directed acyclic graph consisting of three-input majority nodes and regular/complemented edges. MIGs offer a more compact representation for logic as compared to traditional AND/OR-Inverter graphs (see figure below for an example).

MIG manipulation is supported by a consistent algebraic framework. Algebraic optimization of MIGs showed strong synthesis results [1]. As a complement to algebraic optimization, MIG Boolean methods exploit global properties of majority logic, such as bit-error masking, and optimize MIGs even further [2].

For the sake of visualization, the figure below shows the effect of the MIG logic optimization on the MCNC benchmark f51m. After logic optimization using the state-of-the-art ABC synthesis tool [3] this benchmark counts 10 levels of depth and 83 AND nodes. After MIG logic optimization, this benchmarks counts just 7 levels of depth and 70 MAJ nodes [4].


We provide a large set of logic benchmarks optimized by our MIG-synthesis tool (MIGhty) together with their AND/OR optimized counterpart. All MIG files are in Verilog HDL. Original and AND/OR optimized files are in Verilog HDL and AIGER format [5].

Basic characteristics of these circuits are discussed in [2]. If available, newer and more optimized versions of these benchmarks are given.

Other MIG synthesis samples and dedicated runs are available under email request to [email protected] (for academic, non-commercial purposes).

Download link:

Please click here to download. You will access a short on-line survey; after answering the questions you will be able to download the MIG package.


Please contact me for any questions you might have about MIG optimization,  at luca dot amaru at epfl dot ch.

Related publications:

[1]  L. Amarù, P.-E. Gaillardon, G. De Micheli, “Majority-Inverter Graph: A Novel Data-Structure and Algorithms for Efficient Logic Optimization”, Design Automation Conference (DAC), San Francisco, CA, USA, 2014.

[2]  L. Amarù, P.-E. Gaillardon, G. De Micheli, “Boolean Logic Optimization in Majority-Inverter Graphs”, Design Automation Conference (DAC), San Francisco, CA, USA, 2015.

[3] ABC Synthesis tool available at

[4] L. Amarù, A. Petkovska, P.-E. Gaillardon, D. Novo, P. Ienne, G. De Micheli, “Majority-Inverter Graph for FPGA Synthesis”, Workshop on Synthesis And System Integration of Mixed Information technologies (SASIMI 2015), Yilan, Taiwan, 2015.

[5] AIGER format description available at