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. Our main results are: 1) the regularity of a Boolean function  of n variables is expressed by its autosymmetry degree k (with 0 &xle; k &xle n), where means no regularity (that is, we are not able to provide any advantage over standard synthesis); 2) for k &xge; 1 the function is autosymmetric, and a new function k is identified in polynomial time; k is "equivalent" to, but smaller than , and depends on n-k variables only; 3) given a minimal SPP form for k a minimal SPP form for  is built in linear time; 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.
Introduction
The standard synthesis of Boolean functions is performed with Sum of Products (SP) minimization
procedures, leading to two level circuits. More-than-two level minimization is much harder, but
the size of the circuits can signicantly decrease. In many cases three-level logic is a good trade-o
among circuit speed, circuit size, and the time needed for the minimization procedure. Note that, in
all cases, algorithms for exact minimization have exponential complexity, hence the time to attain
minimal forms becomes huge for increasing size of the input.
Two level minimization is well developed [10, 4, 9]. Several techniques for three level minimization
have been proposed for dierent algebraic expressions. Among them EX-SOP forms, where
two SP forms are connected in EXOR [5, 6]; and Sum of Pseudoproducts (SPP) forms, consisting
of an OR of pseudoproducts, where a pseudoproduct is the AND of EXOR factors [8]. For example
is an EX-SOP form, and
is an SPP form. Experimental results show that the average size of SPP forms is approximately
half the size of the corresponding SP, and SPP forms are also smaller than EX-SOP [2]. As a limit
case each EXOR factor reduces to a single literal in SPP, and the SP and SPP forms coincide.
In this work we refer to SPP minimization. Initially this can be seen as a generalization of
SP minimization, and in fact an extension of the Quine-McCluskey algorithm was given in [8] for
SPP. In particular the pseudoproducts to be considered can be limited to the subclass of prime
pseudoproducts, that play the same role of prime implicants in SP. The algorithm for SPP, however,
was more cumbersome than the former, thus failing in practice in minimizing very large functions.
A deeper understanding of the problem, together with the use of ad hoc data structures, has allowed
to widely extend the set of functions practically tractable [2]. Still a number of standard benchmark
functions can be hardly handled with this technique.
In fact the aim of this paper is to exploit the \regularity" of any given Boolean function, in order
to decrease the time needed for its logical synthesis. Our main results are: 1) the regularity of a
Figure

1: An autosymmetric function f with in a Karnaugh map of four variables. The
reduced function f 2 is the set of points in the dotted line, and depends only on the variables x 1
and x 3 .
Boolean function f of n variables can be expressed by an autosymmetry degree k (with 0  k  n),
which is computed in polynomial time. means no regularity, that is we are not able to provide
any advantage over standard synthesis; 2) for k  1 the function f is said to be autosymmetric, and
a new function f k is identied in polynomial time. In a sense f k is \equivalent" to, but smaller than
f , and depends on n k variables only. A function f with its corresponding function
are shown in gure 1; given a minimal SPP form for f k , a minimal SPP form for f is built
in linear time; experimental results show that 61% of the functions in the classical Espresso
benchmark suite are autosymmetric: the SPP minimization time for them is critically reduced, and
we can also solve cases otherwise intractable. Indeed, although autosymmetric functions form a
subset of all possible Boolean functions, a great amount of standard functions of practical interest
fall in this class. In the last section we speculate on the possible causes of this fact. Observe that
even if we can study an autosymmetric function f in a n k dimensional space, f depends, in
general, on all the n input variables, i.e., f is non degenerated.
In the next section 2 we recall the basic denitions and results of SPP theory, and present a
companion algebraic formulation later exploited for testing autosymmetry. In section 3 we discuss
the properties of autosymmetric functions, and how the problem of determining their minimal SPP
forms can be studied on a reduced number of variables. In section 4 we show how autosymmetry
can be tested in polynomial time, and derive a new minimization algorithm that includes such a
test in the initial phase. In section 5 we present an extensive set of experimental results which
validate the proposed approach, also proving that the number of benchmarks practically tractable
is signicantly increased. A nal discussion on the role of autosymmetry is developed in section 6.
2 The Underlying Theory
The basic denitions and properties that we now recall were stated in [8] and extended in [2].
We work in a Boolean space f0; 1g n described by n variables x 0 each point is
represented as a binary vector of n elements. A set of k points can be arranged in a k  n matrix
whose rows correspond to the points and whose columns correspond to the variables. Figure 2
represents a set of eight points in a space of six variables. A Boolean function
can be specied with an algebraic expression where the variables are connected through Boolean
operators, or as the set of points for which denotes the number of such points.
From [8] we take the following. Let u be a (Boolean) vector; u be the elementwise complementation
of u; and b
denote u or u. The constant vectors 0 and 1 are made up of all 0's or all 1's,
respectively. Vector uv is the concatenation of u and v. A vector u of 2 m elements, m  0, is
normal normal. For example all the columns in

Figure

2: A canonical matrix representing a pseudocube P in f0; 1g 6 . The canonical columns are
the matrix of gure 2 are normal vectors.
A matrix M with 2 m rows is normal if all its rows are dierent and all its columns are normal.
A normal matrix is canonical if its rows, interpreted as binary numbers, are arranged in increasing
order (the matrix of gure 2 is canonical). A normal vector is k-canonical, 0  k < m, if is
composed of an alternating sequence of groups of 2 k 0's and 2 k 1's. In gure 2, c 0 is 2-canonical, c 2
is 1-canonical, and c 4 is 0-canonical. A canonical matrix M contains m columns c i 0
of
increasing indices, called the canonical columns of M , such that c i j is (m j 1)-canonical for 0
1. The other columns are the noncanonical ones. If M represents a set of points in a Boolean
space (where the rows are the points and the column c i corresponds to the variable x
and noncanonical columns correspond to canonical and noncanonical variables, respectively. We
Denition 1 (From [8]) A pseudocube of degree m is a set of 2 m points whose matrix is canonical
up to a row permutation.
The matrix of gure 2 represents a pseudocube of 2 3 points in f0; 1g 6 . Note that a subcube in
f0; 1g n is a special case of pseudocube where the noncanonical columns are constant.
The function with value 1 in the points of a pseudocube P is a pseudoproduct, and can be
expressed as a product of EXOR factors in several dierent forms, one of which is called the
canonical expression (brie
y CEX) of P . For the pseudocube P of gure 2 we have:
Refer to [8] for the nontrivial rule for generating CEX(P). We simply recall that each EXOR factor
of the expression contains exactly one noncanonical variable directed or complemented, namely
the one with greatest index in the example), and each noncanonical variable is
contained only in one EXOR factor; all the other variables in the expression are canonical
and x 4 in the example); and some canonical variables may not appear in the expression. Note that
the minimal SP form for the above function is x
much larger than
CEX(P).
If P is in fact a subcube, each EXOR factor in CEX(P) reduces to a single noncanonical variable,
the canonical variables do not appear, and the whole expression reduces to the well known product
expression e.g. used for implicants in SP forms.
A general property of the algebraic representation of pseudocubes is given in the following:
Theorem 1 In a Boolean space f0; 1g
(i) the EXOR factor of any subset of variables (directed or complemented) represents a pseudocube
of degree n
(ii) the product of k  n arbitrary EXOR factors represents either an empty set or a pseudocube of
degree  n k.
Point (i) of the theorem can be easily proved by induction on the number of variables in the
then follows from a theorem of [8] which states that the intersection of
two pseudocubes of degrees p, r is either empty, or is a pseudocube of degree
For the example of gure 2, the EXOR factors x 1 , x in the expression
pseudocubes of 2 5 points, and their product represents the pseudocube P of 2 3
points.
Note now that an equality of the form EXOR 1 EXOR satised by all the
points of a pseudocube, can be equivalently written as a system of k linear equations:
that is an instance of a general linear system A is a kn matrix of
coe-cients 0, 1, and the sum is substituted with EXOR. As known [3, 1] such a system species an
a-ne subspace of the linear space f0; 1g n . Then, from the existence of CEX(P) for any pseudocube
, and from theorem 1, we have:
Corollary 1 In a Boolean space f0; 1g n there is a one-to-one correspondence between a-ne sub-spaces
and pseudocubes.
This corollary allows to inherit all the properties of a-ne subspaces into pseudocube theory. In
particular, a pseudocube containing the point (vector) 0 corresponds to a linear subspace. We also
Denition 2 (From [2]) The structure of a pseudocube P , denoted by STR(P), is CEX(P) without
complementations.
For the pseudocube P of gure 2 we have: STR(P
us now extend the symbol  to denote the elementwise EXOR between two vectors. Then  is
the vector obtained from  complementing in it the elements corresponding to the 1's of . For a
vector  2 f0; 1g n and a subset S  f0; 1g n , let   Sg. We have:
Theorem 2 (From various results in [2]) For any pseudocube P  f0; 1g n and any vector
, the subset
Finally recall that an arbitrary function can be expressed as an OR of pseudoproducts, giving
rise to an SPP form. For example if we add the two rows (points) r
to the matrix of gure 2, we have a new function f that can be seen as the union of two partially
overlapping pseudocubes: namely P (already studied), and Q associated to the rows r
Note that Q is in fact a cube, and we have In conclusion f can be expressed
in SPP form as:
The minimal SP form for f contains 40 literals, while the SPP expression (3) contains 11 literals.
Passing from SP to SPP, however, amounts to passing from a two-level to a three-level circuit. This
fact has always to be taken into account and will not be further repeated.
3 Autosymmetric Functions
The class of autosymmetric functions introduced in [8] seems to be particularly suitable for SPP
minimization. The present work is addressed to these functions, for which we give an alternative
denition.
Denition 3 A Boolean function f in f0; 1g n is closed under , with  2 f0; 1g n , if for each w
Each function is obviously closed under the zero vector 0. As proved in [8], if a function f
is closed under two dierent vectors  1 ,  2 2 f0; 1g n , it is also closed under  1  2 . Therefore
the set L f of all the vectors  such that f is closed under  is a linear subspace of f0; 1g n , see
for example [3]. (In fact, combining in EXOR, in all possible ways, k linearly independent vectors
we form a subspace of 2 k vectors that is closed under , and contains the vector 0
generated as  i  i ). L f is called the linear space of f , and k is its dimension. By corollary 1, L f
is a pseudocube, and we will refer to CEX(L f ) and STR(L f ).
Denition 4 A Boolean function f is k-autosymmetric, or equivalently f has autosymmetry degree
linear space L f has dimension k.
We have:
Theorem 3 Let f be a k-autosymmetric function. There exist ' vectors w 1 , w
, such that
(w
and for each
Proof. Let w 1 be any vector in f . By denition 3, w 1 L f  f . Consider the set f
f is a pseudocube of degree k with jf
be any vector of f 1 . Again by denition 3, w 2 L f  f . Observe that (w 1
(by contradiction: let
then that is w which is a contradiction). Therefore we have:
and using the same argument on the set f n ((w 1 the theorem easily follows. ut
Form the proof above we see that the number of points of a k-autosymmetric function is a
multiple of 2 k . Indeed, each a-ne subspace w i  L f contains 2 k points. Recalling that L f is a
pseudocube, and from theorems 2 and 3 we immediately have:
Corollary 2 A k-autosymmetric function f is a disjoint union of jf j=2 k pseudocubes w i  L f of
degree k all having the same structure STR(L f ), and the same canonical variables of L f .
This corollary has two immediate consequences. First we can extend the denition of canonical
variables to autosymmetric functions. Namely, the canonical (respectively: noncanonical) variables
of L f are designated as the canonical (respectively: noncanonical) variables of f . Second, note that
the 2 k points of each pseudocube w i L f contain all the 2 k combinations of values of the canonical
variables, hence in exactly one of these points all such values are 0. We then have:
Corollary 3 The vectors w of theorem 3 can be chosen as the points of f where all
the canonical variables have value 0. Moreover, for 1  i  is obtained from
complementing the noncanonical variables with value 0 in w i .
Example 1 Consider the function
11111g. It can be easily veried that the linear space of f is:
where each vector can be obtained as the EXOR of the other two. f is then 2-autosymmetric. We
are the canonical and noncanonical variables, respectively. From
corollary 3 we have w
From this we derive the following (nonminimal) SPP form for f , where each term w i  L f of expression
(6) is transformed into an EXOR factor derived from (5) complementing the noncanonical
variables with value 0 in w
From the above properties of autosymmetric functions we observe:
Any function is at least 0-autosymmetric, since is closed under 0.
A function is (n 1)-autosymmetric if and only if is a pseudocube of degree n 1.
A function is n-autosymmetric if and only if is a constant.
Pseudocubes of degree k are the only k-autosymmetric functions with only one term in the
union of expression (4).
We will study any k-autosymmetric function f with k  1 through a simpler function f k . We
state:
Denition 5 For a (k  1)-autosymmetric function f , the restriction f k consists of the jf j=2 k
points of f contained in the subspace f0; 1g n k where all the canonical variables of f have value 0.
Note that f k depends only on the n k noncanonical variables of f .
Once L f has been computed (see next section), the canonical variables of f are known, and
f k can be immediately determined applying denition 5. For instance, for the function f with
example depends on the noncanonical variables x 2 ; x 3 , x 4 . To build f 2 we take the
subset f00001; 00100; 00110g of the points of f for which the canonical variables x 0
0, and then project these points into the f0; 1g 3 subspace relative to x 2 ; x 3 , x 4 , where we have
110g. We can then represent as:
Note that the same expression is obtained setting x
We now show that the SPP-minimal form of any autosymmetric function can be easily derived
from the SPP-minimal form of its restriction. Note that nding the latter form is easier because
the restriction has less variables and points. In the example above f depends on 5 variables and has
depends only on 3 variables and has only 3 points (represented by the minterms
The following lemma is an easy extension of Theorem 6 of [8].
function and its restriction have the same number of pseudo-
products in their minimal SPP forms.
In fact we can prove a stronger property, namely not only f k and f have the same number
of pseudoproducts in their minimal forms, but a minimal form for f can be easily derived from a
minimal form for f k . Let x z 0
be the noncanonical variables of f , and let STR(L f
is the EXOR factor containing x z that each
noncanonical variable is in an unique EXOR factor). We have:
Theorem 4 If SPP (f k ) is a minimal SPP form for f k , then the form SPP (f) obtained by substituting
in SPP (f k ) each variable x z i with the EXOR factor p i is a minimal SPP form for f . 1
Proof. By lemma 1, the number of pseudoproducts in SPP (f) is minimum, then we have only to
prove that this form covers exactly all the points of f .
When we transform f into f k , we select a the vector u i with all canonical variables set to zero
from each a-ne subspace w i  L f . Call v i the vector u i without the canonical variables, i.e., its
projection onto a subspace f0; 1g n k . When we apply the linear substitutions x z0
any pseudoproduct that covers v i in f k to cover all the points in w i L f in f ,
and the thesis immediately follows. ut
4 The Minimization Algorithm
In the previous section we have shown that each Boolean function f is k-autosymmetric, for k  0.
If k  1, f will be simply called autosymmetric. For minimization purposes we have an increasing
advantage for increasing k  1, as minimizing a k-autosymmetric function with n variables and '
points reduces to minimizing a dierent function with n k variables and '=2 k points. Even for
we have to cover only one half of the original points.
Fortunately, for a given function f , nding the associated linear space L f and computing the
autosymmetry degree k is an easy task, because the required algorithm is polynomial in the number
n of variables and in the number of points of f . By denition 3, a function f is closed under  if
for any u 2 f there exists v 2 f such that there exists a vector
such that we can express  as In other words,  must be searched within the
vectors of the set fu  v j u; v 2 fg. More precisely we have:
Theorem 5 Let f be a Boolean function. Then L
Proof. Let  2
u2f
ut
Based on theorem 5 we state:
Algorithm 1 Construction of L f (build L f and nd the autosymmetry degree k of a given
function f)
1. for all build the set u  f ;
2. build the set L
3. compute
1 The resulting expressions may be reduced using some properties of EXOR, in particular
The time complexity of algorithm 1 is (jf j 2 n), because we must build a set uf for all
and the construction of each such a set requires (jf j n) time.
Any SPP minimization algorithm can be easily extended for exploiting autosymmetry. For a
given function f we rst compute L f and k with algorithm 1. If f is not autosymmetric)
we proceed with regular minimization, otherwise we compute the restriction f k of f , minimize
it, and nally derive a minimal form SPP (f) from SPP (f k ). We propose the following A (for
autosymmetry) minimization algorithm.
Algorithm 2 A-Minimization (build a minimal SPP form of a given function f)
1. build L f and compute the value of k by algorithm
2. if with any SPP synthesis algorithm
3. else
(a) determine the canonical variables of L f and compute the restriction f k as indicated in
section 3;
(b) compute STR(L f
(c) compute the minimal form SPP (f k ) for f k with any SPP synthesis algorithm;
(d) build SPP (f) by substituting in SPP (f k ) each noncanonical variable x z i with the EXOR
By the theory developed in the previous section, algorithm 2 is correct. Note that the algorithm
builds an SPP form minimal with respect to the number of pseudoproducts. To obtain the minimal
SPP form with respect to the number of literals we must slightly rearrange steps 3(c) and 3(d),
executing the substitutions of all p i for x z i in the prime pseudoproducts of f k , before selecting such
pseudoproducts in the set covering problem implicit in the minimization algorithm.
Example 2 Minimization of the function f of example 1, using algorithm 2.
Derive L f and k by algorithm 1. For this purpose, for all u 2 f compute the set u f . (For
example, for the point 00100 we obtain the set: 00100
11011g). The intersection of all the sets
gives the linear space L 11001g. We then have 2.
proceed with the else branch of algorithm 2. L f has noncanonical variables
is restricted to these variables and we have: f
The minimization problem now consists of nding a minimal SPP cover of the points of f 2 .
Applying the algorithm of [2] we have the minimal form:
Compute: STR(L f
Derive the minimal SPP form for f by substituting x 2 , x 3 and x 4 in SPP (f 2 ) with the EXOR
factors of STR(L f ), respectively immediate
algebraic simplications we obtain: 2
2 E.g., in the rst term of SPP (fk ) we have: x4 [x4 (x0  x4 In the last term of
#funct 365 116 72 95 41 43 28
%funct 38,9 12,3 7,6 10,1 4,3 4,6 4,1 2,9 1,7 2,4 6,2 3,0 1,9 100
28

Table

1: Distribution of k-autosymmetric functions in the Espresso benchmark suite. #funct are
the total numbers of functions (single outputs) for any value of k, and %funct are the corresponding
percentages. The other rows report the number of k-autosymmetric functions synthesized with the
new algorithm A, and with the previous best algorithm C (#AC); synthesized with algorithm A
only (#A), since algorithm C did not terminate; not synthesized at all since both algorithms did
not terminate (#*).

Table

2: Time gain using algorithm A versus algorithm C, for the 546 functions of row #AC of
to 8). and TC are the times required by the two algorithms on the same function.
is the average of the ratio all the functions with the same value of k.
5 Experimental Results
The new minimization algorithm 2, also called algorithm A, has been tested on a large set of
functions without don't cares, taken from the Espresso benchmark suite [11] (the dierent outputs
of each function have been synthesized separately). The performance of algorithm A has been
compared with the performance of the best previous algorithm, that is the one proposed in [2], in
the following indicated as algorithm C (after Ciriani). In fact, also the minimization of function f k
in algorithm A (step 3(c)) has been implemented with algorithm C.
For all the functions considered we have computed the values of the autosymmetry degree k
with algorithm 1, obtaining the results shown in the rst two rows of table 1. Surprisingly the
overall percentage of autosymmetric functions (k  1) is over the 61%. We have then attempted to
run algorithms A and C for all such functions, recording the CPU times whenever the computation
terminated in less than 172800 seconds (2 days) on a Pentium III 450 machine. Results on program
termination are given in the last three rows of table 1.

Table

2 shows the average reduction of computing time using algorithm A instead of C, for all
the benchmark functions for which both algorithms terminated (i.e., for the 546 functions of row
#AC of table 1). Note the improvement introduced by the new algorithm for all the autosymmetric
functions in the set, and how such an improvement drastically increases for increasing k. For
instead, we have actually the ratio (T A =TC ) is slightly greater than 1 for
each such a function. This is because algorithm A computes L f in any case, then calls algorithm
C. The resulting slowdown is however always negligible because L f is computed in polynomial
time by algorithm 1 (see previous section), while algorithm C is exponential in nature. For all the
functions in the table the forms obtained with the old and the new method coincide.
Finally table 3 shows the CPU times for a small subset of the above functions with k  1, and
other relevant minimization parameters for them.
6 The Role of Autosymmetry
To understand the role of autosymmetric functions we must compare them with the set of all possible
functions. The total number of Boolean functions of n variables is N
, corresponding to all
the ways a subset of points can be chosen in f0; 1g n . This is a huge number, however, due to the
function k #L #PP

Table

3: Detailed results for a subset of autosymmetric functions. The last two columns report
CPU times in seconds on a Pentium III 450 machine for algorithms A and C (a star indicates
non termination after 172800 seconds). The results are relative to single outputs, e.g. max512(0)
corresponds to the rst output of max512. #L and #PP are the numbers of literals and of prime
pseudoproducts in the minimal expression.
randomness of the above generating process very many of such functions do not correspond to any
signicant circuit. Autosymmetric functions are just a subset of the above. By a counting argument
(omitted here for brevity) we can in fact prove that autosymmetric functions are
Therefore, for increasing n, autosymmetric functions constitute a vanishing fractions of all the
functions, as NA =N F goes to zero for n going to innity. Still the question remains on how many
signicant functions are autosymmetric.
All what we can say at the moment is that most of the major benchmark functions are indeed
autosymmetric, as shown in the previous section. The more so when n is small and the values of
N F and NA are not too distant. The reason, we might argue, is that a function encoding a real life
problem must exhibit a regular structure that can be re
ected in some degree of autosymmetry.
This regularity may also allow to dene an autosymmetric function f independently on the number
of variables, and then to state a rule for deriving a minimal form for f valid for any n. Well
known functions as, for example, the ones counting the parity of n bits, or giving the next-state
values for an n bit Gray code, can be easily expressed in minimal form for an arbitrary number
of variables just because they are autosymmetric (for the parity see [8]; for Gray codes elementary
considerations su-ce).
It might be relevant to examine the relation between autosymmetric functions, and functions
which are simply symmetric. That is, functions which are invariant under any permutation of their
variables (see for example [7]). The total number of symmetric functions is
but they are not a subset of the autosymmetric ones. In fact a symmetric function
may be autosymmetric (e.g., the parity function), but there are symmetric functions that are not
autosymmetric (e.g., any symmetric function with an odd number of points). At the moment we
have no interesting results in this direction.
We observe that the information content of an autosymmetric function f is represented by its
reduction f k together with the linear transformation x z 0
so that the core of the synthesis problem is the minimization of f k (section 4). This suggests a
formal generalization. For a given function g 2 f0; 1g m ! f0; 1g we can dene the autosymmetry
class C g as the class of all the autosymmetric functions f 2 f0; 1g t ! f0; 1g; t  m, such that
g. Since the information content of any given function f can be easily found, and a minimal
SPP form for f can then be derived from SPP (f k ), minimizing the function f k corresponds to
minimize the entire class C . Exploiting the full potential of such an approach is currently a
matter of study.
Finally another interesting research direction is the generalization of the autosymmetry property
to functions with don't care set. Since the autosymmetry is strictly related to the points of a
function f , the major goal would be selecting a subset of don't cares as points of f to maximize
the autosymmetry degree of the function. However this seems not to be an easy task.



--R

Realization of Boolean Functions by Disjunctions of Products of Linear Forms.
Logic Minimization Using Exclusive Gates.
Algebra Vol.

An Optimization of AND-OR-EXOR Three-Level Networks
AOXMIN-MV: A Heuristic Algorithm for AND-OR- XOR Minimization
Switching and Finite Automata Theory.
On a New Boolean Function with Applications.
Espresso-Signature: A New Exact Minimizer for Logic Functions.
Synthesis of Finite State Machines: Logic Optimization.
Synthesis on Optimization Benchmarks.
--TR
Two-level logic minimization: an overview
Synthesis of finite state machines
On a New Boolean Function with Applications
Logic minimization using exclusive OR gates

--CTR
Synthesis of integer multipliers in sum of pseudoproducts form, Integration, the VLSI Journal, v.36 n.3, p.103-119, October
three-level logic;synthesis;autosymmetry