Title :
Incremental reduction of binary decision diagrams
Author :
Jacobi, Ricardo ; Calazans, Ney ; Trullemans, Charles
Author_Institution :
Lab. de Microelectron. Univ., Catholique de Louvain, Louvain-la-Neuve, Belgium
Abstract :
A new method is presented to reduce the number of nodes of a binary decision diagram (BDD) after its construction, which the authors call incremental reduction. It is based on an algorithm that swaps two adjacent variables in the BDD ordering. The initial ordering is obtained by an algorithm. Experiments have shown that an average reduction of 20% on the number of nodes of these initial BDDs can be achieved with the authors´ method
Keywords :
Boolean functions; logic design; trees (mathematics); BDD ordering; adjacent variables; binary decision diagrams; incremental reduction; initial ordering; nodes; Binary decision diagrams; Boolean functions; Circuit synthesis; Circuit testing; Data structures; Explosions; Input variables; Iron; Jacobian matrices; Tree graphs;
Conference_Titel :
Circuits and Systems, 1991., IEEE International Sympoisum on
Print_ISBN :
0-7803-0050-5
DOI :
10.1109/ISCAS.1991.176226
