BDD minimization using symmetries

Author

Scholl, Christoph ; Moller, Delwyn ; Molitor, Paul ; Drechsler, Rolf

Author_Institution

Inst. of Comput. Sci., Albert-Ludwigs-Univ., Freiburg, Germany

Volume

18

Issue

2

fYear

1999

fDate

2/1/1999 12:00:00 AM

Firstpage

81

Lastpage

100

Abstract

In this paper we study the effect of using information about (partial) symmetries for the minimization of reduced ordered binary decision diagrams (ROBDD´s). The influence of symmetries for the integration in dynamic variable ordering is studied for both completely and incompletely specified Boolean functions. The problems above are studied from a theoretical and practical point of view. Statistical results and benchmark results are reported to underline the efficiency of the approach. They prove that our techniques lead to improvements of the ROBDD sizes by up to 70%

Keywords

Boolean functions; binary decision diagrams; minimisation; symmetry; Boolean function; ROBDD; completely specified function; incompletely specified function; minimization; reduced ordered binary decision diagram; symmetry; variable ordering; Binary decision diagrams; Boolean functions; Data structures; Field programmable gate arrays; Logic circuits; Logic design; Logic testing; Minimization; Multiplexing; Network synthesis;

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.743706

Filename

743706