Safe BDD minimization using don't cares

Youpyo Hong, Peter A. Beerel, Jerry R. Burch, Kenneth L. McMillan

Research output: Contribution to journalConference articlepeer-review

40 Scopus citations

Abstract

In many computer-aided design tools, binary decision diagrams (BDDs) are used to represent Boolean functions. To increase the efficiency and capability of these tools, many algorithms have been developed to reduce the size of BDDs. This paper presents heuristic algorithms that minimize the size of BDDs representing incompletely specified functions by intelligently assigning don't cares to binary values. The traditional algorithm, restrict [8], is often effective in BDD minimization, but can increase the BDD size. We propose new algorithms based on restrict which are guaranteed never to increase the size of the BDD, thereby significantly reducing peak memory requirements. Experimental results show that our techniques typically yield significantly smaller BDDs than restrict.

Original languageEnglish
Pages (from-to)208-212
Number of pages5
JournalProceedings - Design Automation Conference
StatePublished - 1997
EventProceedings of the 1997 34th Design Automation Conference - Anaheim, CA, USA
Duration: 9 Jun 199713 Jun 1997

Fingerprint

Dive into the research topics of 'Safe BDD minimization using don't cares'. Together they form a unique fingerprint.

Cite this