Logic minimization using exclusive OR gates

Recently introduced pseudoproducts and Sum of Pseudoproduct (SPP) forms have made possible to represent Boolean functions with much shorter expressions than standard Sum of Products (SP) forms LP99. A pseudo product is a product (AND) of Exclusive OR (EXOR) factors, and an SPP form is a sum (OR) of pseudoproducts. The synthesis of SPP minimal forms requires greater effort than SP minimization. In this paper we present a new data structure for this problem, leading to an efficient minimization method for SPP forms implemented with an exact algorithm and an heuristic. Experimental results on a classical set of benchmarks show that the new algorithms are fast, and can be applied to “complex” functions with a reasonable running time.