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 the BDDs. This paper presents heuristic algorithms to minimize the size of the BDDs representing incompletely specified functions by intelligently assigning don't cares to binary values. Experimental results show that new algorithms yield significantly smaller BDDs compared with existing algorithms yet still require manageable run-times. These algorithms are particularly useful for synthesis application where the structure of the hardware/software is derived from the BDD representation of the function to implement because the minimization quality is more critical than the minimization speed in these applications.

Metadata

publication

IEEE Transactions on Computer-Aided Design of Integrated Circuits and …, 2000

year

2000

publication date

2000/1

authors

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

link

https://ieeexplore.ieee.org/abstract/document/822619/

resource_link

https://www.researchgate.net/profile/Peter-Beerel/publication/260585133_Sibling-substitution-based_BDD_minimization_using_don't_cares/links/574b09f908ae5f7899ba1347/Sibling-substitution-based-BDD-minimization-using-dont-cares.pdf

journal

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

volume

19

issue

1

pages

44-55

publisher

IEEE