Title :
Techniques for formal transformations of binary decision diagrams
Author :
Kolotov, G. ; Levin, I. ; Ostrovsky, V.
Author_Institution :
Sch. of Eng., Tel Aviv Univ., Israel
Abstract :
Binary decision diagrams (BDDs), when used for the representation of discrete functions, permit the direct technology mapping into multi-level logic networks. Complexity of a network derived from a BDD is expressed by its number of non-terminal nodes. The paper discusses the problem of reducing the BDDs. It makes two main contributions: (a) the bounds of the potential complexity of the BDD are determined and proven; (b) a formal technique is presented for simplification of Boolean operations on a set of BDDs.
Keywords :
Boolean functions; binary decision diagrams; circuit complexity; logic circuits; Boolean operations; binary decision diagrams; discrete function representation; formal transformations; multi-level logic networks; network complexity; nonterminal nodes; Autocorrelation; Binary decision diagrams; Boolean functions; Data structures; Graphics; Input variables; Logic functions; Optimization methods; Polynomials; Upper bound;
Conference_Titel :
Electronics, Circuits and Systems, 2004. ICECS 2004. Proceedings of the 2004 11th IEEE International Conference on
Print_ISBN :
0-7803-8715-5
DOI :
10.1109/ICECS.2004.1399730
