Title :
Minimization of free BDDs
Author :
Günther, Wolfgang ; Drechsler, Rolf
Author_Institution :
Inst. of Comput. Sci., Albert-Ludwigs-Univ., Freiburg, Germany
Abstract :
Free BDDs (FBDDs) are an extension of ordered BDDs (OBDDs). FBDDs may have different orderings along each path. They allow a more efficient representation, while keeping (nearly) all of the properties of OBDDs. In some cases even an exponential reduction can be observed. In this paper we present for the first time an exact algorithm for finding a minimal FBDD representation for a given Boolean function. To reduce the huge search space, it makes use of a pruning technique. The algorithm also considers symmetries of the function. Since the algorithm is only applicable to small functions, we also present a heuristic for FBDD minimization starting from an OBDD. Our experiments show that in many cases significant improvements can be obtained
Keywords :
Boolean functions; binary decision diagrams; minimisation; Boolean function; FBDD minimization; exponential reduction; free BDDs; function symmetries; minimal FBDD representation; ordered BDD; pruning technique; Binary decision diagrams; Boolean functions; Circuit synthesis; Circuit testing; Computer science; Data structures; Minimization methods; Very large scale integration;
Conference_Titel :
Design Automation Conference, 1999. Proceedings of the ASP-DAC '99. Asia and South Pacific
Conference_Location :
Wanchai
Print_ISBN :
0-7803-5012-X
DOI :
10.1109/ASPDAC.1999.760024
