Majority algebra for the synthesis of combinational logic schemes. Review

S. I. Gurov

Taurida Journal of Computer Science Theory and Mathematics, no. 2 (2020), pp. 39-60

Résumé

The article contains an overview of the results on the application of majority logic of combinational logic schemes. In this first part, the theoretical foundations of majority algebra, its axiomatization and primitive functions, and the use of majority logic in solving practical problems of circuit synthesis are considered. In general, the existing automation tools for the design of electronic systems show satisfactory results of logical synthesis. At the same time, the possibilities of further increasing their efficiency by traditional means have practically been exhausted. This explains the interest of developers of optimization algorithms and software in new methods of synthesis of combinational-logic circuits. The approach with the use of majority and inversion operations as the basic operations for representing Boolean functions seems to be promising. Quantum-dot cellular automaton, Single Electron Tunnelin, Tunneling Phase Logic, etc. are considered as alternatives to CMOS technology. It is important here that in these technologies the main logical units used to implement the schemes are the majority and/or minority logical elements. The article contains the definition of majority algebra and its generally recognized axiomatization $\Omega $. The primitive functions of the majority are considered, which are realized on one majority gate. The main applications of majority logic are described: Logic Optimization, Boolean Satisfiability, Decoding of Repetition Codes. A brief description of the first algorithms for synthesizing majority schemes is given: MALS (Majority Logic Synthesizer, 2007), Kong’s Synthesis (2010), MLUT (Majority Expression Lookup Table, 2015). A comparison of the results of these algorithms is presented

Détail

Keywords: majority logic, boolean algebra, axiomatization, primitive functions, logic synthesis.