Safe BDD minimization using don't cares
Youpyo Hong, Peter A. Beerel, Jerry R. Burch, Kenneth L. McMillan · 1997
In many computer-aided design tools, binary decision diagrams(BDDs) are used to represent Boolean functions. To increase theefficiency and capability of these tools, many algorithms have beendeveloped to reduce the size of BDDs. This paper presents heuristicalgorithms that minimize the size of BDDs representing incompletelyspecified functions by intelligently assigning don't cares tobinary values. The traditional algorithm, restrict [Verification of Synchronous Sequential Machines Based on Symbolic Execution], is often effectivein BDD minimization, but can increase the BDD size. We proposenew algorithms based on restrict which are guaranteed neverto increase the size of the BDD, thereby significantly reducing peakmemory requirements. Experimental results show that our techniquestypically yield significantly smaller BDDs than restrict.