Synthesis and Optimization of Majority Expressions through a Mathematical Model
Nenhuma Miniatura disponível
Data
2020-08-01
Autores
Ferraz, Evandro C. [UNESP]
Junior, Jose V. O. [UNESP]
Grout, Ian
Da Silva, Alexandre C. R. [UNESP]
Título da Revista
ISSN da Revista
Título de Volume
Editor
Resumo
In this paper, the 3MS (Majority Math Model Solver) algorithm is proposed for use in the optimization of majority logic circuits. The new proposed algorithm receives a sequence of binary numbers as input, representing truth tables with a minimum of 3 and a maximum of 8 variables, and returns an optimized majority function that covers the same minterms. Key in this approach is the formulation of constraints that encode a majority logic problem into a mathematical optimization problem. The resulting set of constraints is then applied to an optimization solver and the results are translated into the output majority function. As cost criteria the minimization of levels is prioritized, followed by the minimization of gates, inverters and gate inputs. The 3MS algorithm was evaluated based on a comparison with the state-of-the-art exact synthesis for majority-of-three networks, which considers the number of levels and gates as cost criteria. Since the 3MS considers two additional cost criterias, the goal of the algorithm is to generate functions that are also exact in relation to the number of levels and gates, but uses fewer inverters and gate inputs. Simulation studies have shown that the 3MS is able to further improve 79% of all 77,292 compared functions, and achieves equal results for the remaining 21%.
Descrição
Palavras-chave
logic synthesis, majority logic, mathematical model, optimization solver, primitive functions
Como citar
Proceedings - 33rd Symposium on Integrated Circuits and Systems Design, SBCCI 2020.