6. Synthesis of Majority Expressions Through Primitive Function Manipulation

Due to technology advancements and circuits miniaturization, the study of logic systems that can be applied to nanotechnology has been progressing steadily. Among the creation of nanoelectronic circuits the reversible and majority logic stand out. This paper proposes the MPC (Majority Primitives Combination) algorithm, used for majority logic synthesis. The algorithm receives a truth table as input and returns a majority function that covers the same set of minterms. The formulation of a valid output function is made with the combination of previously optimized functions. As cost criteria the algorithm searches for a function with the least number of levels, followed by the least number of gates, inverters, and gate inputs. In this paper it’s also presented a comparison between the MPC and the exact_mig, currently considered the best algorithm for majority synthesis. The exact_mig encodes the exact synthesis of majority functions using the number of levels and gates as cost criteria. The MPC considers two additional cost criteria, the number of inverters and the number of gate inputs, with the goal to further improve exact_mig results. Therefore, the MPC aims to synthesize functions with the same amount of levels and gates, but with less inverters and gate inputs. Tests have shown that both algorithms return optimal solutions for all functions with 3 input variables. For functions with 4 inputs, the MPC is able to further improve 66% functions and achieves equal results for 11%. For functions with 5 input variables, out of a sample of 1000 randomly generated functions, the MPC further improved 48% functions and achieved equal results for 11%.