Title :
On relationship between ITE and BDD
Author :
Lam, William K C ; Brayton, Robert K.
Author_Institution :
Dept. of EECS, California Univ., Berkeley, CA, USA
Abstract :
Properties of the if-then-else directed-acyclic graph (ITE) and its relation to the binary decision diagram (BDD) are investigated. It is shown that, for any given variable ordering, there are fewer exponential ITEs than BDDs, and that, for any function f, the size of its canonical ITE is bounded by 4× the size of its corresponding canonical BDD, i.e. ||ITE(f)||<4×||BDD(f)||. However, for most MCNC benchmarks, ||ITE||≈2×||BDD||. It is also shown that the controlling functions of ITEs are maximal with respect to addition, multiplication, and complementation. A graphical relationship between ITEs and BDDs is demonstrated, and algorithms for obtaining canonical ITEs from canonical BDDs, and vice versa, are proposed
Keywords :
directed graphs; logic design; MCNC benchmarks; binary decision diagram; controlling functions; directed-acyclic graph; exponential ITEs; graphical relationship; if-then-else; Binary decision diagrams; Boolean functions; Data structures; Extraterrestrial measurements; Polynomials;
Conference_Titel :
Computer Design: VLSI in Computers and Processors, 1992. ICCD '92. Proceedings, IEEE 1992 International Conference on
Conference_Location :
Cambridge, MA
Print_ISBN :
0-8186-3110-4
DOI :
10.1109/ICCD.1992.276312
