Minimização de funções majoritárias de 3 entradas como um problema de programação não linear inteira binária

Abstract

Com a tecnologia CMOS atingindo limitações físicas, nanotecnologias emergentes baseadas em portas lógicas majoritárias têm ganhado destaque. Um dos grandes desafios é a minimização dos circuitos que utilizam essa arquitetura. Tradicionalmente, métodos de otimização dependem do uso de funções majoritárias primitivas. Esta tese demonstra que essa dependência não é obrigatória e, como objetivo principal, apresenta uma nova metodologia para a minimização de funções booleanas expressas na forma majoritária de 3 entradas. O cerne da proposta baseia-se na introdução dos conceitos de funções booleanas fundamentais, que restringem as funções primitivas, e das classes de complexidade de uma função majoritária, para estruturar a busca pela solução minimizada. Deste modo, esta teoria apresenta a problemática da minimização como um problema de programação não linear inteira binária. Esta teoria foi implementada utilizando a linguagem Python e o solucionador CPLEX, obtendo-se resultados experimentais que validaram a abordagem, minimizando funções majoritárias de 3 entradas com até 15 variáveis e 5 níveis, obtendo circuitos otimizados que minimizam o número de portas e níveis lógicos. O trabalho estabelece, portanto, um novo paradigma teórico e computacional para a síntese de circuitos em lógica majoritária, podendo ser a base para o desenvolvimento de técnicas de otimização mais eficientes no futuro.

With CMOS technology reaching physical limitations, emerging nanotechnologies based on majority logic gates have gained prominence. One of the major challenges is the minimization of circuits using this architecture. Traditionally, optimization methods depend on the use of primitive majority functions. This thesis demonstrates that this dependence is not mandatory and, as its main objective, presents a new methodology for minimizing Boolean functions expressed in 3-input majority form. The core of the proposal is based on the introduction of the concepts of fundamental Boolean functions, which restrict primitive functions, and the complexity classes of a majority function, to structure the search for the minimized solution. Thus, this theory presents the problem of minimization as a binary integer nonlinear programming problem. This theory was implemented using the Python language and the CPLEX solver, obtaining experimental results that validated the approach, minimizing 3-input majority functions with up to 15 variables and 5 levels, obtaining optimized circuits that minimize the number of gates and logic levels. This work therefore establishes a new theoretical and computational paradigm for the synthesis of circuits in majority logic, and may form the basis for the development of more efficient optimization techniques in the future.