Minimizing ROBDD sizes of incompletely specified Boolean functions by exploiting strong symmetries

Author

Scholl, Christoph ; Melchior, S. ; Hotz, Günter ; Molitor, P.

Author_Institution

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

fYear

1997

fDate

17-20 Mar 1997

Firstpage

229

Lastpage

234

Abstract

We present a method computing a minimum sized partition of the variables of an incompletely specified Boolean function into symmetric groups. The method can be used during minimization of ROBDDs of incompletely specified Boolean functions. We apply it as a preprocessing step of symmetric sifting presented by Panda (1994) and Moller (1994) and of techniques for ROBDD minimization of incompletely specified Boolean functions presented by Chang (1994) and Shiple (1994). The technique is shown to be very effective: it improves ROBDD sizes of symmetric sifting by a factor of 51% and by a factor of 70% in combination with a slightly modified version of the technique of Chang and Shiple

Keywords

Boolean functions; decision theory; diagrams; directed graphs; group theory; minimisation; symmetry; ROBDD size minimization; incompletely specified Boolean function; partitioning; reduced order binary decision diagram; symmetric group; Boolean functions; Circuit faults; Computer science; Data structures; Field programmable gate arrays; Inspection; Logic circuits; Logic testing; Minimization methods; Polynomials;

fLanguage

English

Publisher

ieee

Conference_Titel

European Design and Test Conference, 1997. ED&TC 97. Proceedings

Conference_Location

Paris

ISSN

1066-1409

Print_ISBN

0-8186-7786-4

Type

conf

DOI

10.1109/EDTC.1997.582364

Filename

582364