Minimizing the number of paths in BDDs: Theory and algorithm
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.
binary decision diagrams formal verification logic synthesis