Boolean functions classification via fixed polarity Reed-Muller forms

TitleBoolean functions classification via fixed polarity Reed-Muller forms
Publication TypeJournal Article
Year of Publication1997
AuthorsTsai, C-C, Marek-Sadowska, M
JournalComputers, IEEE Transactions on
Pagination173 -186
Date Publishedfeb
KeywordsBoolean functions, Boolean functions classification, Boolean matching, equivalence classes, fixed polarity Reed-Muller forms, four-variable functions, functional equivalence, input negation, input permutation, logic CAD, output negation, Reed-Muller codes, standard cell libraries, technology mapping
AbstractIn this paper, we present a new method to characterize completely specified Boolean functions. The central theme of the classification is the functional equivalence (a.k.a. Boolean matching). Two Boolean functions are equivalent if there exists input permutation, input negation, or output negation that can transform one function to the other. We have derived a method that can efficiently identify equivalence classes of Boolean functions. The well-known canonical Fixed Polarity Reed-Muller (FPRM) forms are used as a powerful analysis tool. The necessary transformations to derive one function from the other are inherent in the FPRM representations. To identify uniquely each equivalence class, a set of well-known characteristics of Boolean functions and their variables (including linearity, symmetry, total symmetry, self-complement, and self-duality) are employed. It is shown that all the equivalence classes of four-variable functions are uniquely identified where majority of the classes have a single FPRM form as their representative. The Boolean matching has applications in technology mapping and in design of standard cell libraries