Aperfeiçoamento do método clause-column table para a geração eficiente de implicantes primos

• Ano de defesa: 2014
• Autor(a) principal: Barbieri, Caroline Domingues Porto do Nascimento [UNESP]
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Universidade Estadual Paulista (Unesp)
• Palavras-chave em Português: Algebra booleana; Programação linear; Algoritmos de computador; Automação; Linear programming
• Link de acesso: http://hdl.handle.net/11449/126338; http://www.athena.biblioteca.unesp.br/exlibris/bd/cathedra/19-08-2015/000846221.pdf

Efficient generation of prime implicants is an important factor in the coverage phase of minterms in minimization's methods of Boolean functions. This research presents an improved version of the method called Clause-Column Table, used to generate prime implicants. In this new algorithm was added to the adjacency theorem and a new stopping criterion. These modifications prevented the generation of null terms and unnecessary iterations that occurred in the original algorithm. The original and improved algorithms were implemented in C language and compared. The Clause-Column Table Improved method was compared with the Expander and Quine-McCluskey method. The results proved that the improved version generates fewer iterations than the original version, and that in most functions analyzed it was avoided the generation of null terms. Comparing Quine-McCluskey method and the Expander it was proved that the Clause-Column Table Enhanced method is superior in the generation of prime implicants, since in some cases eliminates those who are not required to cover the function. In ownership of the prime implicants the cover problem of minterms was formulated as an integer linear programming problem of 0 and 1, where the solution is open to all advances in the area of linear programming in order to obtain a minimal solution