Otimização de circuitos digitais: estudo dos principais métodos e desenvolvimento de algoritmo baseado no teorema do consenso iterativo

Abstract

A minimização de funções booleanas já é pauta há muito tempo no meio acadêmico. Desde a década de 50, cientistas das mais diversas formações ligadas às ciências exatas vem buscando uma forma ideal, ou perto da ideal, de minimizar funções lógicas. Minimizar funções lógicas, significa diminuir a quantidade de variáveis e portas lógicas do circuito, no entanto, sem perder funcionalidade. Este é um desafio que persiste há décadas. Tendo em vista que circuitos digitais estão presentes em itens praticamente indispensáveis pela população nos dias atuais, como telefones celulares e televisores. Dessa forma, fica evidente compreender a necessidade de se minimizar, uma vez que, apesar de esses equipamentos estarem cada vez mais potentes, os fabricantes pretendem mantê-los cada vez mais compactos no que diz respeito à exposição de hardware. O trabalho de graduação teve como objetivo o estudo dos principais métodos de minimização de funções booleanas, em ordem cronológica, a fim de evidenciar as principais características, vantagens e desvantagens de cada um e trazer uma visão geral do tema. Para o desenvolvimento de um algoritmo que utiliza-se da teoria do consenso iterativo, estudou-se a linguagem de programação python e técnicas de programação. O algoritmo desenvolvido tem como característica a obtenção de um mínimo local, entretanto, para os testes realizados, na maioria das vezes, obteve-se o mínimo global. Para a avaliação do desempenho computacional, utilizou-se o tempo de execução e o consumo de memória. Foram utilizadas funções com até 5 variáveis e obtidos tempo de execução inferior a 0,01 segundos e um uso de memória de até 0,1 Mega Byte, parâmetros aceitáveis para este tipo de processamento.

The minimization of Boolean functions has been on the academic agenda for a long time. Since the 1950s, scientists from a wide range of backgrounds in the exact sciences have been searching for an ideal, or close to ideal, way of minimizing logic functions. Minimizing logic functions means reducing the number of variables and logic gates in the circuit, but without losing functionality. This is a challenge that has persisted for decades. Given that digital circuits are present in items that are practically indispensable to the population these days, such as cell phones and televisions. In this way, it is clear to understand the need to minimize, since, although these devices are increasingly powerful, manufacturers want to keep them increasingly compact in terms of hardware exposure. The goal of this undergraduate project is to study the main methods for minimizing Boolean functions, in chronological order, in order to highlight the major characteristics, advantages and disadvantages of each method and provide an overview of the subject. In order to develop an algorithm that uses iterative consensus theory, the phython programming language and programming techniques were studied. The algorithm developed has the characteristic of obtaining a local minimum, however, for the tests carried out, the global minimum was obtained most of the time. Execution time and memory consumption were used to evaluate computational performance. Have been used functions with up to 5 variables and obtained execution times of less than 0.01 seconds and memory usage of up to 0.1 Mega Byte, which are acceptable parameters for this type of processing.