CANONICAL RESTRICTED MIXED-POLARITY EXCLUSIVE-OR SUMS OF PRODUCTS ANDTHE EFFICIENT ALGORITHM FOR THEIR MINIMIZATION

The concept of canonical restricted mixed polarity (CRMP) exclusive-OR sum of products forms is introduced. The CRMP forms include the incon sistent canonical Reed-Muller forms and the fixed-polarity Reed-Muller (FPRM) forms as special cases. The set of CRMP forms is included in t he set of exclusive-OR sum-of-product (ESOP) expressions. An attempt t o characterise minimal CRMP forms for completely specified Boolean fun ctions is presented as well as an insight into the complexity of compu tation needed to find such a form. Some fundamental properties unique to CRMPs are proven. It is also proven that the upper bound on the num ber of terms in the CRMP form is smaller than that in the conventional normal forms and equal to that of the ESOPs. A theorem providing a lo wer bound on the number of CRMP terms is given. Finally, based on thes e theoretical results, a heuristic algorithm and its implementation to obtain a quasiminimal CRMP form for a multioutput function are resent ed.