A MAJestic Synthesis Review [Special Section on 2025 IEEE Kirchhoff Award]
- 20 May 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Circuits and Systems Magazine
- Vol. 25 (2) , 23-28
Abstract
This article presents a review of Majority-Inverter Graphs (MIGs) and their practical use in various applications within logic synthesis. MIGs are directed acyclic graphs consisting of three-input majority nodes and regular/complemented edges. They represent a paradigm shift in representing and optimizing logic using only majority (MAJ) and inversion (INV) functions. In this article, we review different optimization algorithms that work on MIGs, including algebraic, Boolean, and exact methods. We also describe different applications of MIGs in logic synthesis: From classical CMOS-based synthesis to their use for theoretical results and emerging technologies.Keywords
This publication has 27 references indexed in Scilit:
- Logic Resynthesis of Majority-Based Circuits by Top-Down Decomposition2021
- Computing Majority by Constant Depth Majority Circuits with Low Fan-in GatesTheory of Computing Systems, 2018
- Proposal for nanoscale cascaded plasmonic majority gates for non-Boolean computationScientific Reports, 2017
- Majority Logic Synthesis for Spin Wave Technology2014
- ABC: An Academic Industrial-Strength Verification Tool2010
- Switching Theory for Logic Synthesis1999
- Logical devices implemented using quantum cellular automataJournal of Applied Physics, 1994
- Quantum cellular automataNanotechnology, 1993
- Synthesis of combinational logic using three-input majority gates1962
- A ternary operation in distributive latticesBulletin of the American Mathematical Society, 1947