Optimization of fixed-polarity Reed-Muller circuits using dual-polarity property (Q5928981)

The paper presents an exhaustive-search method for the optimization of Reed-Muller (RM) polynomials. The authors start by proving that two-fixed polarity RM expansions whose polarities are dual can be derived from each other without resorting to Boolean expressions. This allows the authors to derive all other fixed-polarity RM expansions with the same number of variables from a known fixed-polarity RM expansion. Using the property of a hypercube, the authors show that their conversion method leads to a recursive way of finding all the RM expansions efficiently. Important features of the method are: the conversion from one RM expansion to another is carried out using one-bit checking and a good polarity predictor is not required. As a result, a simple algorithm is developed to facilitate the efficient derivation of RM expansions based on a single-bit difference in polarity. The simplicity of the proposed algorithm makes its implementation straightforward. Comparison results with known exhaustive-search algorithms are presented to illustrate the performance of the proposed method. The method proves to be at least as efficient as already accepted exhaustive-search methods of Boolean-to-RM conversions.