Geração de circuitos a partir de BDDs : simplificações possíveis a partir da decomposição de shannon

Abstract

Esta dissertação apresenta uma contribuição para a geração de circuitos digitais a partir de diagramas de decisão binários (BDDs). Existe um método trivial para síntese de circuitos digitais a partir de BDDs onde cada nodo do BDD é mapeado diretamente para um multiplexador em uma correspondência um para um, ou seja: um nodo, um multiplexador. Este método é possível porque cada nodo do BDD é uma decomposição de Shannon que pode ser implementada como um multiplexador. Porém, simplificações podem ser aplicadas no circuito do multiplexador de nodos específicos, dependendo de propriedades da função Booleana representada em cada nodo específico. Esta dissertação cataloga e apresenta simplificações para o circuito do multiplexador baseado em condições apresentadas por nodos de BDDs. Foi também implementado um método para gerar circuitos a partir de BDDs usando a correspondência um para um com os multiplexadores simplificados (conforme o caso) ao invés de utilizar os multiplexadores completos. O método utilizando as simplificações leva a uma redução no número de portas lógicas necessárias para implementar o circuito final, quando comparado com a versão que implementa multiplexadores completos (sem as simplificações). Para os benchmarks apresentados, o método apresenta uma redução de 27.9% no número total de nodos, quando comparado com a versão que não utiliza as simplificações.

This dissertation presents a contribution to the generation of digital circuits from binary decision diagrams (BDDs). There is a trivial method for synthesizing digital circuits from BDDs where each node of the BDD is mapped directly to a multiplexer in a one-to-one correspondence, that is: one node, one multiplexer. This method is possible because each BDD node is a Shannon decomposition that can be implemented as a multiplexer. However, simplifications can be applied to the multiplexer circuit of specific nodes, depending on properties of the Boolean function represented in each specific node. This dissertation catalogs and presents simplifications for the multiplexer circuit based on conditions presented by BDD nodes. A method was also implemented to generate circuits from BDDs using one-to-one correspondence with simplified multiplexers (as applicable) instead of using full multiplexers. The method using simplifications leads to a reduction in the number of logic gates required to implement the final circuit, when compared to the version that implements complete multiplexers (without simplifications). For the benchmarks presented, the method presents a reduction of 27.9% in the total number of nodes, when compared to the version that does not use the simplifications.