Orientador: Ivanil Sebastião Bonatti

Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica

Resumo: Este trabalho trata do problema de simplificação de funções booleanas e da redução de estados, em máquinas de estados finitos, modelando-os como um problema de programação matemática. Na minimização lógica, os implicantes são gerados aplicando-se o algoritmo do consenso numa árvore binária...

Resumo: Este trabalho trata do problema de simplificação de funções booleanas e da redução de estados, em máquinas de estados finitos, modelando-os como um problema de programação matemática. Na minimização lógica, os implicantes são gerados aplicando-se o algoritmo do consenso numa árvore binária que representa a função booleana. A cobertura mínima é obtida resolvendo-se um problema de programação linear inteira 0 e 1, cuja função objetivo é a soma ponderada de todos os implicantes primos e as restrições correspondem a soma dos implicantes primos que cobrem cada mintermo da função. Na minimização de funções booleanas com múltiplas saídas o problema de cobertura mínima pode ser modelado como um problema matemático não linear dependendo do critério de otimização utilizado. o método de geração de classes de compatibilidades máximas foi utilizado para a redução de estados. A função objetivo é formulada como a soma das classes primas sujeita às restrições de cobertura e fechamento. Uma vez formulado como um problema de programação matemática, a minimização de funções booleanas e a redução de máquinas de estados se abrem para as novas técnicas desenvolvidas nessa área de pesquisa

Abstract: This work proposes a method of dealing with the problem of boolean function minimization and finite state machine reduction by modeling each of them as a mathematical programming problem. In the logic minimization, prime implicants are generated by applying the consensus algorithm in the...

Abstract: This work proposes a method of dealing with the problem of boolean function minimization and finite state machine reduction by modeling each of them as a mathematical programming problem. In the logic minimization, prime implicants are generated by applying the consensus algorithm in the binary decision tree that represents a boolean function. A minimal cover can then be obtained by solving an integer linear program with objective function as a weighing sum of prime implicants whose constraints are the sums of prime implicants covering each minterm. In a multiple-output boolean function minimization, a minimal cover problem may be modelled as a non-linear mathematical problem depending on the specific optimization criterion that is used. The method of generating the maximal compatibility classes has been used for the state reduction phase. The objective function is formulated as the sum of the prime classes, and the constraints are due to restrictions of covering and closure. Once formulated as a mathematical programming problem, the boolean function minimization and the state machine reduction are opened to the new techniques that have been developed in this research area