Geração de circuitos a partir de BDDs : junção de funções booleanas incompletamente especificadas

Abstract

Funções booleanas especificadas incompletamente (também conhecidas como rela ções booleanas) são definidas por seu On-set, Off-set e DC-set (Don’t care set). Como o conjunto DC-set pode ser atribuído ao On-set ou ao Off-set, uma relação booleana pode conter várias funções completamente especificadas que satisfaçam a relação booleana original. Este trabalho propõe um algoritmo para a atribuição de don’t cares para relações booleanas representadas como um par de Binary Decision Diagrams (BDDs). O algoritmo consiste em explorar o On-set e Off-set da relação booleana de entrada representada como BDDs e juntá-los em um terceiro BDD, que terá um número menor de nodos. Em média, nosso algoritmo foi capaz de gerar coberturas com 23,53% do número de nodos comparado aos BDDs dos on-sets das relações booleanas originais. Enquanto que métodos como restrict, constrain e leaf identifying compaction geraram coberturas com tamanho em torno de 30%. Além disso, o algoritmo mostrou-se eficaz na redução do número de variáveis de entrada, onde apresentou uma redução média de 15,67%.

Incompletely specified Boolean functions (a.k.a. Boolean Relations) are defined by their On-set, Off-set, and dc-set (don’t care set). As the dc-set can be assigned either to the On-set or to the Off-set, a Boolean relation can contain several completely specified functions that satisfy the original Boolean Relation. This work proposes an algorithm for the assignment of don’t cares for Boolean relations represented as a couple of Binary Decision Diagrams (BDDs). The algorithm consists of exploring the On-set and Off-set of the input Boolean relation represented as BDDs and join ing them into a third BDD, which will have a lower number of nodes. On average, our algorithm was able to generate coverage with 23.53% of the number of nodes compared to the BDDs of the on-sets of the original Boolean relations. While meth ods such as restrict, constrain and leaf-identifying compaction generated coverage with size around 30%. In addition, the algorithm proved to be effective in reducing the number of input variables, where it presented an average reduction of 15.67%.