Emprego do método de Quine-Mccluskey estendido para gerar circuito mínimo com estruturas ESOP (XOR-XNOR)

Abstract

Com a disseminação de dispositivos eletrônicos cada vez menores e o advento de novas tecnologias. A busca por métodos de minimização de funções booleanas tem sido a base para eletrônica digital. Neste trabalho apresenta-se a implementação da primeira fase do método Quine-McCluskey Estendido que utiliza-se de estruturas AND-XOR-XNOR para a geração de implicantes primos. O objetivo do trabalho foi comprovar que, na maioria das vezes, a implementação de uma função Booleana utilizando expressões AND-XOR-XNOR requerem menor quantidade de termos produtos, quando comparado com implementação com expressões AND-OR. A fase de cobertura dos mintermos em ambos os métodos foi formulada como um problema de programação linear inteira 0 e 1 que através do programa Lp_solve obteve a solução de menor custo. Na comparação da eficiência dos métodos foram analisados os custos dos circuitos mínimos gerados, a quantidade de memória utilizada e o tempo de execução. Com os resultados obtidos pode-se concluir que, para a maioria dos casos executados, o método Quine-McCluskey Estendido gera uma solução de menor custo. No entanto, com relação ao desempenho computacional (tempo de execução e memória), o método Quine-McCluskey Estendido apresentou-se inferior se comparado ao Quine-McCluskey.

With the dissemination of smaller and smaller electronic devices and the advent of new technologies. The search for methods of minimizing Boolean function has been the basis for digital electronics. This work presents the implementation of the first phase of the Extended Quine-McCluskey method, which uses AND-XOR-XNOR structures to generate prime implicants. The goal of this work is to prove that, in most cases, the implementation of a Boolean function using the expressions AND-XOR-XNOR requires fewer product terms than the implementation with AND-OR expressions does. The stage of mini terms covering in both methods was formulated with the 0-1 integer linear programming problem, which obtained lower cost through the Lp_Solve program. While comparing the efficiency of these methods we analised: the costs of the minimum circuits generated, the amount of memory that has been used and the runtime. With the obtained results it is possible to conclude that, for most of the executed cases, the Extended Quine-McCluskey method generates a solution of lower cost. On the other hand, with regards to the computational performance (runtime and memory), the Extended Quine-McCluskey method has shown itself inferior when compared to the Quine-McCluskey method.