Efficient polarity conversion for large Boolean functions
L. Wang, A.E.A. Almaini, Alexander I. Bystrov · IEE Proceedings - Computers and Digital Techniques · 1999
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 Cyrix 6x86-166 CPU and 32MB RAM. The results show that the algorithm is very efficient in terms of time and space for large Boolean functions.