On a new Boolean function with applications
Consider a hypercube of 2(n) points described by n Boolean variables and a subcube of 2(m) points. m less than or equal to n. As is well-known, the Boolean function with value 1 in the points of the subcube can be expressed as the product (AND) of n - m variables. The standard synthesis of arbitrary functions exploits this property. We extend the concept of subcube to the more powerful pseudocube. The basic set is still composed of 2(m) points, but has a more general form. The function with value 1 in a pseudocube, called pseudoproduct, is expressed as the AND of n - m EXOR-factors, each containing at most m + 1 variables. Subcubes are special cases of pseudocubes and their corresponding pseudoproducts reduce to standard products. An arbitrary Boolean function can be expressed as a sum of pseudoproducts (SPP). This expression is in general much shorter than the standard sum of products. as demonstrated on some known benchmarks. The logical network of an n-bit adder is designed in SPP, as a relevant example of application of this new technique. A class of symmetric functions is also defined, particularly suitable for SPP representation.
boolean function pseudocube pseudoproduct exor-factor algebraic expression logical design