Sibling-substitution-based BDD minimization using don´t cares

Author

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

Author_Institution

Dept. of Electr. Eng., Dongguk Univ., Seoul, South Korea

Volume

19

Issue

1

fYear

2000

fDate

1/1/2000 12:00:00 AM

Firstpage

44

Lastpage

55

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

Keywords

Boolean functions; binary decision diagrams; formal verification; logic CAD; minimisation of switching nets; Boolean functions; binary decision diagrams; binary values; computer-aided design tools; don´t cares; heuristic algorithms; incompletely specified functions; minimization quality; minimization speed; sibling-substitution-based BDD minimization; synthesis application; Application software; Binary decision diagrams; Boolean functions; Data structures; Design automation; Hardware; Heuristic algorithms; Minimization methods; Runtime; Software algorithms;

fLanguage

English

Journal_Title

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

Publisher

ieee

ISSN

0278-0070

Type

jour

DOI

10.1109/43.822619

Filename

822619