Title :
Minimizing the number of paths in BDDs: Theory and algorithm
Author :
Fey, Gorschwin ; Drechsler, Rolf
Author_Institution :
Inst. of Comput. Sci., Univ. of Bremen, Germany
Abstract :
The complexity of circuit and systems design increases rapidly. Therefore, a main focus of research in the area of electronic-design automation are efficient algorithms and data structures. Among these, binary decision diagrams (BDDs) have been used in a wide variety of applications and were intensively studied from a theoretical point of view. But mostly, when complexity issues were considered, only the number of nodes in a BDD has been analyzed. Here, we study minimizing the number of paths in BDDs from a theoretical and a practical point of view. Connections to different areas in computer-aided design are outlined, theoretical studies are carried out, and an algorithm to minimize the number of paths is presented. Experimental results show the efficiency of the algorithm.
Keywords :
binary decision diagrams; circuit complexity; electronic design automation; high level synthesis; logic design; binary decision diagrams; circuit complexity; computer-aided design; data structures; electronic-design automation; formal verification; logic synthesis; Algorithm design and analysis; Binary decision diagrams; Boolean functions; Circuit testing; Circuits and systems; Data structures; Design automation; Formal verification; Integrated circuit synthesis; Minimization; Binary decision diagrams; formal verification; logic synthesis;
Journal_Title :
Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on
DOI :
10.1109/TCAD.2005.852662
