Um método de equivalência de funções Booleanas através de grafos bipartidos

Abstract

Atualmente uma das etapas mais críticas no fluxo de projeto de circuitos integrados é a etapa denominada mapeamento tecnológico. Essa dificuldade se deve ao fato que esta etapa precisa resolver um problema NP-completo denominado equivalência Booleana. A proposta deste trabalho é a de acelerar esse processo representando uma função Booleana através de um grafo bipartido, e utilizar esta estrutura para calcular Pequivalência por permutação, uma etapa da equivalência Booleana. O grafo bipartido gerado é denominado Grafo Bipartido Booleano, ou GBB. Diversos métodos de resolução são apresentados e uma discussão quanto à qualidade deles é exposta. Os resultados mostram que essa estrutura é correta e que pode ser utilizada para calcular eficientemente equivalência por permutação. Trabalhos futuros vão desde estender esta abordagem para outros tipos de equivalência até a utilização do GBB para resolução de outros problemas na área de síntese de circuitos digitais.

Currently one of the most critical steps in the design flow of integrated circuits is the step called technology mapping. This difficulty is due to the fact that this step needs to solve an NP-complete problem called Boolean matching. The purpose of this work is to accelerate this process representing a Boolean function by a bipartite graph, and use this approach to calculate Boolen equivalence by permutation, a step of Boolean matching. The bipartite graph generated is called Bipartite Boolean Graph, or GBB. Various methods of resolution are presented and a discussion about the quality of them is exposed. The results show that this structure is correct and can be used to efficiently compute equivalence by permutation. Future work will extend from this approach to other types of equivalence to the use of GBB to solving other problems in the field of synthesis of digital circuits.