Estudo da fase de geração de implicantes primos do método de QuineMcCluskey buscando uma heurística

Abstract

O problema de minimização de funções Booleanas busca otimizar os circuitos lógicos mantendo sua funcionalidade e reduzindo custo de implementação. Há diversas técnicas de minimização de funções booleanas descritas na literatura, como o método de Quine-McCluskey, que gera todos os implicantes primos para então fazer a cobertura dos mintermos da função, empregando os implicantes primos gerados. É notável o baixo desempenho computacional do Método de Quine-McCluskey para funções com muitas variáveis. Algoritmos heurísticos têm atingido resultados satisfatórios quanto a essas limitações computacionais, como o programa Espresso. Na maioria das aplicações não se faz necessária a solução exata ou global da função, uma solução local ou mínima será suficiente. Neste trabalho implementou-se em linguagem de programação Python um algoritmo que modifica a fase de geração de implicante primos do método de Quine-McCluskey, de modo a gerar implicantes primos num período relativamente curto de tempo, quando comparado com o método de Quine-McCluskey tradicional. Para avaliar a eficiência, o algoritmo proposto foi comparado com o método de Quine-McCluskey tradicional e com o programa Espresso, considerando a quantidade de memória utilizada, o tempo de execução, os termos gerados e os custos das soluções geradas. A partir dos resultados obtidos pode-se concluir que, o método Quine-McCluskey modificado tem menor tempo de execução que o método de Quine-McCluskey tradicional, e menor tempo de execução que o programa Espresso para menos de 8 variáveis de entrada. Para funções com poucas variáveis o método de Quine-McCluskey tradicional faz menor uso de memória que o método de Quine-McCluskey modificado. Entretanto, do ponto de vista da minimização o método de Quine-McCluskey modificado não apresenta um resultado satisfatório, pois não gera uma solução de custo mínimo para a maioria dos casos ensaiados, como geram o método de Quine-McCluskey tradicional e o programa Espresso.

The minimization problem of boolean functions seeks to optimize logic circuits keeping its functionality and reducing implementation cost. There are many minimization techniques in literature, such as the Quine-McCluskey method, that generates all prime implicants to then do the function minterms coverage using the generated prime implicants. The low computing performance of the Quine-McCluskey method for functions with many product terms is noticeable. Heuristic algorithms have achieved satisfactory results regarding these computational limitations, such as the Espresso program. In most applications an exact or global solution of the function is not necessary, a local or minimal solution will suffice. In this work an algorithm was implemented in the Python programming language that modifies the prime implicant generation phase of the Quine-McCluskey method, in order to generate prime implicants in a relatively short period of time, when compared to the traditional Quine-McCluskey method. To evaluate the method's efficiency, the proposed method was compared to the traditional Quine-McCluskey method and the Espresso program, the amount of memory used, execution time, generated terms and the costs of generated solutions were considered. From the results obtained, it can be concluded that the modified Quine-McCluskey method generates fewer implicants than the other methods, therefore it requires a shorter execution time than the traditional Quine-McCluskey method, and a shorter execution time than the program Espresso for less than 8 input variables. For functions with few variations, the traditional Quine-McCluskey method uses less memory than the modified Quine-McCluskey method. However, from a minimization standpoint the modified Quine-McCluskey method does not present a satisfactory result, since it does not generate a minimum cost solution for many of the cases tested, as does the traditional Quine-McCluskey method and the ESPRESSO program.