BOOLEAN FUNCTIONS CLASSIFICATION VIA FIXED POLARITY REED-MULLER FORMS

In this paper, we present a new method to characterize completely spec ified Boolean functions. The central theme of the classification is th e functional equivalence (a.k.a. Boolean matching). Two Boolean functi ons are equivalent if there exists input permutation, input negation, or output negation that can transform one function to the other. We ha ve derived a method that can efficiently identify equivalence classes of Boolean functions. The well-known canonical Fixed Polarity Reed-Mul ler (FPRM) forms are used as a powerful analysis tool. The necessary t ransformations to derive one function from the other are inherent in t he FPRM representations. To identify uniquely each equivalence class, a set of well-known characteristics of Boolean functions and their var iables (including linearity, symmetry, total symmetry, self-complement , and self-duality) are employed. It is shown that all the equivalence classes of four-variable functions [10] are uniquely identified where majority of the classes have a single FPRM form as their representati ve. The Boolean matching has applications in technology mapping and in design of standard cell libraries.