Fast three-level logic minimization based on autosymmetry

Sum of pseudoproducts (SPP) is a three level logic synthesis technique developed in recent years. In this framework we exploit the "regularity" of Boolean functions to decrease minimization time. The main results are: 1) the regularity of a Boolean function f of n variables is expressed by its autosymmetry degree k (with 0 ≤ k ≤ n), where k = 0 means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for k ≥ 1 the function is autosymmetric, and a new function fk is identified in polynomial time; fk is "equivalent" to, but smaller than f, and depends on n - k variables only; 3) given a minimal SPP form for fk, a minimal SPP form for f is built in linear time; 4) experimental results show that 61% of the functions in the classical ESPRESSO benchmark suite are autosymmetric, and the SPP minimization time for them is critically reduced; we can also solve cases otherwise practically intractable. We finally discuss the role and meaning of autosymmetry.