Efficient ordered binary decision diagrams minimization based on heuristics of cover pattern processing

Author

Wu, Yu-Liang ; Marek-Sadowska, Malgorzata

Author_Institution

Dept. of Electr. & Comput. Eng., Univ. of California, Santa Barbara, CA, USA

fYear

1993

fDate

22-25 Feb 1993

Firstpage

273

Lastpage

277

Abstract

A metric of dynamic binateness for Boolean functions is introduced. Based on it and on an analogy between an ordered binary decision diagram (OBDD) of a function and the process of recognizing strings of patterns representing the function´s cover, a near linear, efficient ordering heuristic for two-level form specified functions is developed. The algorithm stably achieves on average an improvement of over 600% in OBDD size in comparison to results from similar computation complexity heuristics. The results are comparable to those obtained using lexicographic order but are achieved in less CPU time

Keywords

Boolean functions; directed graphs; logic design; minimisation of switching nets; Boolean functions; cover pattern processing; efficient ordering heuristic; metric of dynamic binateness; ordered binary decision diagrams minimization; recognizing strings of patterns; two-level form specified functions; Boolean functions; Circuits; Data mining; Data structures; Input variables; Minimization; Packaging; Pattern recognition; Polynomials; Testing;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation, 1993, with the European Event in ASIC Design. Proceedings. [4th] European Conference on

Conference_Location

Paris

Print_ISBN

0-8186-3410-3

Type

conf

DOI

10.1109/EDAC.1993.386464

Filename

386464