Fast Three-Level Logic Minimization Based on Autosymmetry

In the framework of SPP minimization, a three level logic synthesis technique developed in recent years, we exploit the ``regularity'' of Boolean functions to decrease minimization time. Our main results are: 1) the regularity of a Boolean function $f$ of $n$ variables is expressed by its \emph{autosymmetry degree} $k$ (with $0 \le k\le n$), where $k=0$ means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for $k\geq 1$ the function is {\em autosymmetric}, and a new function $f_k$ is identified in polynomial time; $f_k$ is ``equivalent'' to, but smaller than $f$, and depends on $n-k$ variables only; 3) given a minimal SPP form for $f_k$, a minimal SPP form for $f$ is built in linear time; 4) experimental results show that 61\% of the functions in the classical \textsc{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.