Review of works on the use of majority Boolean algebra for the synthesis of combinational logic schemes

S. I. Gurov

Taurida Journal of Computer Science Theory and Mathematics, no. 3 (2020), pp. 59-76

Résumé

The article contains an overview of the results on the application of majority logic to the synthesis of combinational logic schemes. In the first part, the theoretical foundations of questions of majority algebra and some algorithms of practical problems of the circuit algorithm are considered. In this second part, the basic terminology of logical networks is given first. Majority-inverter graphs (MIG) important for further considerations are described. Illustrated are MIGs versus generic AND/OR/Inverter (AOIG) graphs that include the properties of regular AIGs. It is pointed out that the possibilities of algebraic operations over MIG are much wider than those over AOIG. It is proved that an arbitrary MIG can be transformed by any other logically equivalent one using a sequence of transformations from the axiomatic system $\Omega$. Relevant examples are given. Methods of MIG optimization in terms of size (set of vertices), delay (depth), power (switching frequencies, switching activity) are considered. A transformation-oriented axiomatic system $\psi$ is introduced. The application of MIG size optimization with $\psi$ is illustrated with a simple example. Methods for minimizing MIG depth are discussed and illustrated with examples. The possibility of using the considered methods to optimize the switching frequency in MIG is indicated, at which its size and the probability of switching the state of the vertices $0\longleftrightarrow 1$ decrease. The results of experiments on optimization of various MIG parameters are presented. The MPC (Majority Primitives Combination) algorithm of combinational logic circuits based on majority logic is considered. Optimality criteria used by the MPC when calculating the cost of a circuit in order of importance are the number of levels (depth) of the circuit, the number of gates in it, the number of inverters, the number of element inputs. The results of the MPC algorithm application for the logical synthesis of 4-place functions are presented.

Détail

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