Fast three-level logic minimization based on autosymmetry
Anna Bernasconi, Valentina Ciriani, Fabrizio Luccio, Linda Pagli · Proceedings - ACM IEEE Design Automation Conference · 2002
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. Our 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.