Efficient polarity conversion for large Boolean functions

The concept of polarity for canonical sum-of-products (SOP) Boolean functions is introduced. This facilitates efficient conversion between SOP and fixed polarity Reed-Muller (FPRM) forms. New algorithms are presented for the bidirectional conversion between the two paradigms. Multiple segment and multiple pointer techniques are employed to achieve fast conversion for large Boolean functions. Experimental results are given using a personal computer with a Cyrix 6×86-166 CPU and 32 MB RAM. The results show that the algorithm is very efficient in terms of time and space for large Boolean functions