Otimização de funções lógicas majoritárias utilizando programação linear inteira binária e quantificação de primitivas

Abstract

A tecnologia semicondutora tem sido a base dos circuitos lógicos digitais da computação moderna. O uso de portas lógicas dos padrões AND e NAND tem direcionado o projeto e implementação destes circuitos. Recentes pesquisas em nanotecnologia têm explorado horizontes para o aumento da velocidade e eficiência de circuitos digitais, diminuindo sua escala de integração. Rompendo um paradigma, as portas lógicas majoritárias têm sido utilizadas no projeto destes circuitos, substituindo suas antecessoras clássicas. Um dos grandes desafios destas tecnologias é a simplificação e a otimização destes circuitos lógicos. Neste trabalho, formula-se a otimização de funções booleanas empregando funções majoritárias primitivas através de um problema de programação linear inteira binária, por meio do desenvolvimento de um software. Resultados obtidos mostram que o método apresentado é compacto e promissor. Adicionalmente, apresenta-se a dedução para a função polinomial que determina a quantidade de funções majoritárias primitivas como função da quantidade de variáveis e sua representatividade dentre todas as funções.

Semiconductor technology has been the basis of the digital logic circuits of modern computing. The use of AND and NAND standards logic gates has guided the design and implementation of these circuits. Recent research in nanotechnology has explored horizons for increasing the speed and efficiency of digital circuits, decreasing their scale of integration. Breaking a paradigm, the majority logic gates have been used in the design of these circuits, replacing their classic predecessors. One of the great challenges of these technologies is the simplification and optimization of these logic circuits. In this work, the optimization of Boolean functions is formulated using primitive majority functions through a problem of binary integer linear programming, through the development of an software. Results obtained show that the developed method is compact and promising. In addition, presents the deduction of the polynomial function which determines the number of primitive majority functions as a function of the number of variables and its representativeness among all functions.