Worst and Best Irredundant Sum-of-Products Expressions.
AbstractIn an irredundant sum-of-products expression (ISOP), each product is a prime implicant (PI) and no product can be deleted without changing the function. Among the ISOPs for some function $f$, a worst ISOP (WSOP) is an ISOP with the largest number of PIs and a minimum ISOP (MSOP) is one with the smallest number. We show a class of functions for which the Minato-Morreale ISOP algorithm produces WSOPs. Since the ratio of the size of the WSOP to the size of the MSOP is arbitrarily large when $n$, the number of variables, is unbounded, the Minato-Morreale algorithm can produce results that are very far from minimum. We present a class of multiple-output functions whose WSOP size is also much larger than its MSOP size. For a set of benchmark functions, we show the distribution of ISOPs to the number of PIs. Among this set are functions where the MSOPs have almost as many PIs as do the WSOPs. These functions are known to be easy to minimize. Also, there are benchmark functions where the fraction of ISOPs that are MSOPs is small and MSOPs have many fewer PIs than the WSOPs. Such functions are known to be hard to minimize. For one class of functions, we show that the fraction of ISOPs that are MSOPs approaches 0 as $n$ approaches infinity, suggesting that such functions are hard to minimize.
2. MSOP : STn; k  n .
3.
Proof. See the Appendix. tu
In the proof of Lemma 2.1, we showed that
which is six more than the lower
bound given in 3 of Theorem 3.1. Therefore, for n  7 and
k  3, the lower bound is not tight. However, for k  1, the
lower bound is exact. That is,
Theorem 3.2.
2:
Proof. See the proof of Theorem 7.3 in the Appendix. tu
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 937
A special case of these theorems occurs when n  3 and TABLE 1
k  1. and for STn; 1 versus n
Example 3.3. ST3; 1x1 _ x2 _ x3x1 _ x2 _ x3 has the
following properties:
2. MSOP : ST3; 1  3.
3.
Fig. 1a and Fig. 1b show the MSOP and WSOP of
respectively. Interestingly, the ISOP generator
of Minato [19], which is based on Morreale's [20]
algorithm produces a WSOP for ST3; 1 instead of an
MSOP. This will be discussed in more detail later.
Definition 3.2. The redundancy ratio of a function f is
The normalized redundancy ratio of an n-variable
function f is
are the sizes of
WSOPs and MSOPs. If this ratio is small, any logic
minimization algorithm will do well since, even if a WSOP
is generated, it is not much worse than an MSOP. On the
other hand, a large ratio suggests that care should be exercised.
The normalized redundancy ratio is normalized with respect to
the number of variables. It is a convenience; it allows one to
compare the redundancy ratio of two functions with a different
number of variables.
From the expressions for MSOP : STn; k and
given in Theorem 3.1, we can state:
Theorem 3.3.
s
From the expressions for MSOP : STn; 1 and
Theorems 3.1 and 3.2, respec-
tively, we can state:
Theorem 3.4.STn; 1  2  ;
r

Table

1 shows the values of and for STn; 1, where
8. It can be seen that takes its maximum value
when That is, as n increases above 2, first increases,
peaking at 4, and then it continually decreases.
From Theorem 3.4, is monotone increasing with an
upper limit of 2. Thus, for STn; 1 functions, the number of
PIs in a WSOP is never more than two times the number of
PIs in an MSOP. An important question is whether there
exist functions where is larger than 2. Indeed, we show a
class of functions in which increases without bound as n
increases. This has important consequences for heuristics
that produce ISOPs. For such heuristics there is the prospect
of generating an ISOP whose size is much larger than the
minimum. We consider this topic now.
Definition 3.3. Let STm; kr be the n  m r-variable
function
^r
where r is the AND (product) of r functions.
Theorem 3.5. STm; kr has the following properties:
r
r mr
2. MSOP : STm; k  .
3.
Proof. See the Appendix. tu
For k  1, we have:
Theorem 3.6.
Example 3.4. For m  3 and k  1, ST3; 1r has 6r PIs,
We have:
Theorem 3.7.
"#r
Example 3.5. For m  4 and k  1, we have
From this, it can be seen that becomes arbitrarily large as r
approaches infinity. In this example, there are n  4r
938 IEEE TRANSACTIONS ON COMPUTERS, VOL. 50, NO. 9, SEPTEMBER 2001
variables. This represents a class of functions for which
grows without bound as the number of variables grows.
4EXTENSION TO MULTIPLE-OUTPUT FUNCTIONS
In the case of multiple-output functions, minimization of
two-level networks or programmable logic
arrays (PLAs) can be done using characteristic functions
[26], [27], [29].
Definition 4.1. For an n-variable function with m output values,
form an n  1-variable two-valued single output function
Fx1;x2; .;xn;Xn1, where xi is a binary valued
variable, for 1 i n and Xn1 takes m values such
that Fx1;x2; .;xn;j1 iff fjx1;x2; .;xn1
represents all and only the
permitted combinations of inputs and nonzero output values of
f. F is called the characteristic function (for nonzero
outputs).
The significance of the characteristic function is seen in
Theorem 4.1 below.
Definition 4.2. XS is a literal, where X takes a value in
1g such that XS  1
if X  a 2 S and XS  0, otherwise. A logical product of
literals that contains at most one literal for each variable is a
product term. Products combined with OR operators form a
sum-of-products expression (SOP). A Prime implicant (PI),
irredundant sum-of-products expression (ISOP), worst ISOP
(WSOP), and minimum SOP (MSOP) are defined in a
manner similar to the two-valued case.
Theorem 4.1 [15], [27], [29]. The number of AND gates in the
minimum AND-OR two-level network for the function
f0;f1; .;fm1 is equal to the number of PIs in the MSOP
for the characteristic function F.
Definition 4.3. An n-bit decoder has n inputs x1;x2; .;xn,
and 2n outputs f0;f1; .;f2n1, where fi  0 iff the binary
number representation of x1x2; .;xn is i.
Example 4.1. The 4-bit decoder has 16 outputs, as follows:
.
.
.
Definition 4.4. DEC_n is the characteristic function of an n-bit
decoder.
Example 4.2. DEC_4 is shown in positional cube notation in
the upper table of Fig. 2. That is, each entry in this table is
a prime implicant of DEC_4, where xi appears as xi, xi,
or don't care (absent) if the corresponding entry is 10, 01,
or 11, respectively. For X5, the entry 0111111111111111 is
the literal X , etc. Therefore, thefirst corresponds to
Fig. 2. Positional cubes for two ISOPs of DEC_4.
the prime implicant x1x2x3x4X5 .
Collectively, the 16 entries in the upper table of Fig. 2
represent an ISOP of DEC_4 with PIs. An ISOP for
DEC_4 with only eight PIs exists, as shown in the lower
table of Fig. 2.
The observations of Example 4.2 can be generalized as
follows:
Theorem 4.2. The function DEC_n has a WSOP that requires at
least 2n PIs and an MSOP that requires at most 2n PIs.
The above theorem proves the existence of an n-variable
2n-output variable function, where the sizes of the MSOP
and the WSOP are at most 2n and at least 2n, respectively.
The upper ISOP for DEC_4 shown in Fig. 2 is not a WSOP
since an ISOP with 20 PIs has been found for DEC_4.
5DERIVATION OF ALL ISOPs
Very little is known about the distribution of the sizes for
ISOPs. For example, even for single-output functions, we
know of no study that shows how many ISOPs exist with
various number of product terms.
Although various methods to generate all the ISOPs for a
logic function are known [22], [12], [21], [6], [35], [25], no
experimental results have been reported. Experiments are
computationally intensive even for functions with a small
number of variables. However, we can obtain the statistical
properties of ISOPs for some interesting functions.
Before showing the complete algorithm, consider the
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 939
has two MSOPs with three PIs and four WSOPs with
four PIs.
Fig. 3. fx1;x2;x3ST3; 1.
Example 5.1.
f  ST3; 1x1 _ x2 _ x3x1 _ x2 _ x3
has six minterms (Fig.
Fig. 4 is the covering table for ST3; 1. It shows the
following relations:
To cover m1;p1 _ p6 is necessary:
To cover m3;p1 _ p2 is necessary:
To cover m2;p2 _ p3 is necessary:
To cover m6;p3 _ p4 is necessary:
To cover m4;p4 _ p5 is necessary:
To cover m5;p5 _ p6 is necessary:
To satisfy all the conditions at the same time, we have
Pf1, where
Pf is called the Petrick function [22]. By expanding
Pf into SOPs, we have
p1p3p5 _ p2p3p5p6 _ p1p2p4p5 _ p2p4p5p6
_ p1p3p4p6 _ p2p3p4p6 _ p1p2p4p6 _ p2p4p6:
Note that each product with an underline is covered by
another product having fewer literals. Such products are
redundant. Deleting these products, we have
_ p2p3p4p6 _ p2p4p6:
Pf consists of all the PIs of the Petrick function [23] and
each PI of Pf corresponds to an ISOP for f.
Furthermore, each literal pi in the PI of Pf corresponds
to a PI for f. For example, p1p3p5 corresponds to the ISOP
x1x3 _ x2x3 _ x1x2. Note that there are six ISOPs; two
have three PIs, while four have four PIs. Thus, ST3; 1
Fig. 4. Covering table of ST3;1.
In this way, all the ISOPs are obtained. For general
functions, the number of minterms and PIs are very large.
Thus, we use an ROBDD (reduced ordered binary decision
diagram) to represent the function and a Prime_TDD
(Ternary decision diagram) [31] to represent the set of all
the PIs. In the Prime_TDD for f, each path from the root
node to the constant 1 node corresponds to a PI for f.We
also use an ROBDD to represent the Petrick function. While
there are many ways to generate all the ISOPs of a given
function f, we use the following algorithm:
Algorithm 5.1 (Generation of all ISOPs for a function f).
1. Generate all the PIs for f by using the Prime_TDD
(the ternary decision diagram representing PIs) of f.
2. From the set of PIs and the set of minterms for f,
generate the Petrick function Pf (which represents
the covering table [22]).
3. Generate the Prime_TDD (which represents all the
PIs) of Pf.
4. Generate the 1-paths of the Prime_TDD and, for each
1-path, generate the corresponding ISOP.
In the Prime_TDD in Step 4, each path from the root node to
the constant 1 corresponds to a PI for Pf and to an ISOP
for f. Each 1 edge has weight 1 and each 0 edge has
weight 0. The total sum of weights from the root node to the
constant 1 nodes is the number of PIs in the ISOP. Note that
the shortest path corresponds to an MSOP and the longest
path corresponds to a WSOP.
6.1 STn; k Functions
Using Algorithm 5.1, we compare the number of PIs in
STn; kr for different n, k, and r. Table 2 shows the number
of PIs in the MSOP and the WSOP of STn; kr, as well as
the total number of PIs. Shown also are the results of the
Minato-Morreale algorithm.
The 9SYM (or SYM9) [11], [15] function shown in [3,
p. 165] is identical to ST9; 3. It has 1,680 PIs,
POP [9], a PRESTO-type [4], [33] logic minimization
algorithm, produced an ISOP with 148 products. CAMP
[1] produced an ISOP with 130 PIs, while MINI [15] did
well, producing 85 PIs.

Table

3 shows the distribution of ISOPs to the number of
PIs in an ISOP for STn; 1 for 3 n 7. This data was
obtained by Algorithm 5.1. It can be seen that the set of
MSOPs is small compared to the set of all ISOPs.
6.2 Other Functions
We also applied Algorithm 5.1 to compare the number of
PIs for multiple-output functions. Table 4 shows the
distribution of the number of PIs in ISOPs for various
functions [32].
INCn is an n-input n  1 output function such that the
value of the output is x  1, where x is the value of the
940 IEEE TRANSACTIONS ON COMPUTERS, VOL. 50, NO. 9, SEPTEMBER 2001

Number of PIs and Redundancy Ratio for Various Functions
input; WGT5 is the same as RD53, a 5-input 3-output
function, where the output is a binary number whose value
is the number of 1s on the inputs; ROT6 computes the
square root of a 6-bit integer; LOG5 computes the logarithm
of the 5-bit integer; ADR3 is a 3-bit adder; and SQR5
computes the square of the 5-bit input.
Note that all the ISOPs for INC6 have the same number
of PIs. This means any logic minimizer obtains an exact
minimum solution. This is also is true for WGT5. For ADR3,
most of the ISOPs have 31 PIs or 33 PIs. This is consistent
with the observation that the logic minimization of ADR3 is
relatively easy. For SQR5, the distribution is very wide. The
MSOPs have 27 PIs, while WSOPs have 37 PIs. This is
consistent with the observation that the minimization of
SQR5 is more difficult. Note that SQR5 is a 10 output binary
function. The data shown is for all outputs.
Although we could not obtain the distribution for SQR6
due to the memory overflow, we conjecture that the
distribution of number of PIs for SQR6 is also wide. We
also developed WIRR, a heuristic algorithm to obtain ISOPs
with many products. For SQR5, SQR6, and 9SYM, the
numbers of PIs in the solutions are shown in Table 5.
7DISTRIBUTION OF ISOPs-AN ANALYTIC
APPROACH
The distribution of ISOPs to the number of PIs is a way to
represent the search space a heuristic algorithm must
traverse in a minimization of an expression. For the case
of STn; 1 functions, we can show a part of this distribu-
tion; a graph representation of the set of PIs allows this.
Definition 7.1. Let F be an ISOP of STn; 1.Inthegraph
representation GF of F
1. GF has nodes x1;x2; ., and xn, and
2. GF has an edge from xi to xj iff xixj is a PI in F.
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 941

Distribution of ISOPs in STn; 1 Functions
Example 7.1. Fig. 5 shows the graph representations of the
MSOP and WSOP for ST3; 1 (shown in Fig. 1).
We show that the graph representation of an ISOP of F
has a special property.
Definition 7.2. A directed graph G is strongly connected iff for
every pair of vertices a; b in G, there is a path from a to b and
from b to a. A directed graph G is minimally strongly
connected iff it is strongly connected and the removal of any
edge causes G not to be strongly connected.
Theorem 7.1. Let GF be a graph representation of F. F is an
ISOP of STn; 1 iff GF is minimally strongly connected.
Proof. See the Appendix. tu
The graph representations of the MSOP and WSOP of
shown in Fig. 5, are both strongly connected, as
they should be by Theorem 7.1. Since each edge represents a
prime implicant, an MSOP has a graph representation with
the fewest edges. This observation facilitates the enumeration
of MSOPs.
Theorem 7.2. The number of MSOPs for STn; 1 is n  1!.
Proof. See the Appendix. tu
The graph representation allows a characterization of
ISOPs. Specifically, complementing all variables in an ISOP
of STn; 1 is equivalent to reversing the direction of all
edges in the graph representation GF of F.IfGF is
minimally strongly connected, then the graph obtained
from GF by reversing the direction of all edges is also
minimally strongly connected. This proves:
Lemma 7.1. If F is an ISOP of STn; 1, then the SOP derived
from F by complementing all variables is an ISOP of
STn; 1.
Example 7.2. When all variables are complemented, the
graph representations of the ISOPs shown in Fig. 5
produce the graphs in Fig. 6, which also represent an
MSOP and a WSOP.
It is important to note the difference between changing an
ISOP F and changing the function realized by F. That is, an
function is unchanged by a complementation of
variables, i.e. it is a self-anti-dual function [32].
However, an ISOP for an STn; k function may or
may not be changed when all variables are comple-
mented. For example, F  x1x2 _ x2x3 _ x3x1 is an ISOP
for ST3; 1. Complementing all variables in F yields,
F  x1x2 _ x2x3 _ x3x1, a different ISOP.
It is interesting that the WSOP for ST3; 1 is unchanged
by a complementation of all variables, as can be seen by
comparing Fig. 5b with Fig. 6b. The invariance of an ISOP
with respect to complementation of all literals is a unique
characteristic of WSOPs, as shown in the next result.
Lemma 7.2. Let F be an ISOP of STn; 1. F is a WSOP iff
complementing all variables in F leaves F unchanged.
Proof. See the Appendix. tu

Distribution of ISOPs in Arithmetic Functions
942 IEEE TRANSACTIONS ON COMPUTERS, VOL. 50, NO. 9, SEPTEMBER 2001

Number of PIs Produced by Various Algorithms on Three Benchmark Functions
It is interesting that Lemma 7.2 does not generalize to
k. Specifically, for ST5; 2, the ISOP
F  x1x2x3x5 _ x3x5x1x2 _ x1x3x2x4 _ x2x4x1x3
_ x1x4x2x5 _ x2x5x1x4 _ x1x5x3x4 _ x3x4x1x5
_ x2x3x4x5 _ x4x5x2x3
is invariant with respect to complementation of all
variables. However, it is an MSOP and not a WSOP.
We can also enumerate WSOPs as follows:
Theorem 7.3. The number of WSOPs for STn; 1 is nn2.
Proof. See the Appendix. tu
The graph representation allows the enumeration of
other classes of ISOPs. For example, we can enumerate
ISOPs that have one more PI than is in the MSOP.
Specifically,
Theorem 7.4. The number of ISOPs for STn; 1 with n  1 PIs
is

Proof. See the Appendix. tu
By comparing the number of MSOPs with either the
number of WSOPs or the number of ISOPs with one more PI
than in the MSOP, we find that the former is much less than
either of the latter for large n. That is, as n approaches
infinity, the ratio of MSOPs to WSOPs approaches 0 (use
Stirling's formula to replace n  1! in the expression for
the number of MSOPs). This proves the following:
Theorem 7.5. The fraction of ISOPs for STn; 1 that are
MSOPs approaches 0 as n approaches infinity.
It is interesting that the ratio of the number of ISOPs with
than is in an MSOP) to the number of
WSOPs also approaches 0 as n approaches infinity. This
suggests that WSOPs are much more common than minimal
or near-minimal ISOPs.
The existence of an algorithm that finds the worst sum-of-
products expression for a class of functions is surprising. It
counters our expectation that a heuristic algorithm should
perform reasonably well. Also, the large difference
between the size of the worst and the best expression is
especially compelling since such an algorithm will perform
very poorly. It is, therefore, an interesting question of
whether there are other algorithms and other functions that
exhibit the same characteristics.
Fig. 6. Graph representations of Fig. 5 with all variables complemented.
Fig. 5. Graph representations of the MSOP and WSOP for ST3;1.
(a) MSOP. (b) WSOP. (a) MSOP. (b) WSOP.
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 943
We show a multiple-output function where the worst
and the best ISOPs differ greatly in size. Specifically, a
decoder with 2n outputs and n inputs realizes a function
where a WSOP has at least 2n PIs and an MSOP has at most
2n PIs. Since this is a commonly used logic function,
disparity in the size of WSOPs and MSOPs cannot be
viewed as a characteristic of contrived functions only.
Although computationally intensive, enumeration of the
ISOPs for representative functions gives needed insight into
the problem. We show an algorithm to compute all ISOPs of
a given function. We apply it to benchmark functions and
show there are significant differences in the distributions of
ISOPs. That is, some functions have a narrow distribution,
where the WSOP is nearly or exactly the same size as the
MSOP. These tend to be easy to minimize. For example, for
unate functions [17] and parity functions, there is exactly
one ISOP. Such functions are classified as trivial in the
Berkeley PLA Benchmark Set (e.g., ALU1, BCD, DIV3,
CLP1, CO14, MAX46, NEWPLA2, NEWBYTE, NEWTAG,
and RYY6) [26]. Other functions display a wide range and
tend to be hard to minimize. For example, 9SYM or SYM9
(ST9; has a wide range, i.e., the number of PIs in a
WSOP and an MSOP is 148 and 84 PIs, respectively. This
function is known to be hard to minimize.
For a class of functions, we provide an analysis showing
that the number of MSOPs is significantly smaller than the
number of WSOPs. That is, by showing a correlation with
directed graphs, we enumerate all MSOPs and all WSOPs of
the class and show that the number of MSOPs and WSOPs
is n  1! and nn2, respectively. As n increases, the ratio of
PIs in a WSOP to the PIs in an MSOP grows without bound.
This suggests such functions are hard to minimize.
A complete understanding of the minimization process
will require knowledge of the search space and how various
algorithms progress through it. However, such an understanding
is not likely to be achieved in the near future. Our
research suggests that there is merit to understanding the
correlation between the degree of difficulty in minimizing a
function and the distribution of its ISOPs.


Lemma 2.1.
Proof. There are two steps. In the first step, we prove that
an ISOP with 70 PIs exists for this function. In the second
step, we show that it is a WSOP. For the first step, it is
convenient to view the symmetric function as having
three parts. Specifically,
f0;1;3;4;6;7g f0;1g f3;4g f6;7g
A WSOP is obtained by finding a WSOP of each of the
three parts separately. Consider the 7-bit Hamming code
shown in Table 6.
For each code word, create a PI that covers two
minterms by replacing one of the most abundant bits in

A 7-Bit Hamming Code
the code word by a don't care. In the case of code word,
0000000; this creates seven PIs, each of which covers the
minterm with all variables 0 and one minterm with
exactly one 1. This covers all minterms of S7 .
Similarly, seven PIs generated from code word 1111111
cover all minterms of S7 .
All of the remaining 14 code words have either four 0s
and three 1s or four 1s and three 0s. For each, create four
PIs by changing one of the four logic values in the
majority to a don't care. Collectively, the four PIs cover
the original code word and four words that are a
distance one away from the code word. Because the
distance between any pair of code words is at least three,
a change in a single bit of a code word in the Hamming
code creates a word that is not a code word that is
distinct from either another code word or a word that is
one bit different from another code word. This implies
that those minterms a distance one away from a code
word are covered by at most one PI. It follows that each
PI is irredundant. Since each of the 14 code words
corresponds to a set of PIs that cover five distinct
minterms, there are 14 5  70 minterms total. On the
otherhand,thenumberofmintermsforS7 is
f3;4g
It follows that these PIs cover
all the minterms of S7 . In all, 7  56  7  70 PIs cover
all of the 8  minterms of the function.
It follows that this set of PIs is a cover for S7 .
Further, it is an irredundant cover and we have an ISOP.
We have proven that an ISOP with 70 PIs exists for
S7 . We show that this is a WSOP by showing that
no more than seven, 56, and seven PIs can cover the
minterms in S7 , S7 , and S7 , respectively. Since
f0;1g f3;4g f6;7g
S7 and S7 are monotone functions, their ISOPs are
unique. Each consists of seven PIs. For S7 , the ISOP of
above covers the 70 minterms associated with this
function. On the contrary, assume that the proposed
ISOP is not a WSOP. Thus, there is a set of p>56 PIs that
forms an ISOP for these minterms. Each PI covers exactly
two minterms, for a total of 2p>112 instances of a PI
covering a minterm. Let m1 and m>1 be the number of
minterms covered by one and more than one PI,
944 IEEE TRANSACTIONS ON COMPUTERS, VOL. 50, NO. 9, SEPTEMBER 2001
respectively. m>1  70  m1. Since the set of PIs is
irredundant, each PI covers at least one minterm that is
not covered by any other PI. Thus, m1 p>56.It
follows that 2p  3m1 > 280. Further, 2p  m1 > 280
4m1  470  m1 and we can write
> 4: A:1
Here, the numerator is the number of instances in which
a PI covers a minterm that is covered by more than one
PI, while the denominator represents the number of
minterms covered by more than one PI. Since this ratio
exceeds four, by the Pigeonhole Principle, there is at least
one minterm covered by at least five PIs. But, this is
impossible; each minterm is covered by no more than
four PIs (i.e., each code word is covered by a PI derived
from a code word by converting one of the four most
abundant variables, 0 or 1, to a don't care). Thus, it must
be that the proposed ISOP is a WSOP. tu
Theorem 3.1.

2. MSOP : STn; k  n .
3.
Proof.
1. An implicant of STn; k has the form
xi1 xi2 xik xink1 xink2 xin :
Thatis,forthisimplicanttobe1,atleast
k variables (xi1 ;xi2 ; ., and xik ) must be 1 and at
least k variables must be 0 (xink1 ;xink2 ; ., and
xin ), where 2k n.Thisimplicantisprime;
deleting a literal creates an implicant that is 1
when STn; k should be 0. Specifically, deleting
creates an implicant that is 1
when less than n variables are 1, while deleting
creates an implicant that is
1 when more than n  k variables are 1.
The number of such PIs is the number of ways 3.
to separate n variables into three parts, where
order withina part is not important. This is the
multinomial n  n! .
2. First, we show that n is a lower bound on the
number of PIs of STn; k. Then, we show a set
of n PIs that covers all and only minterms in the
function STn; k. It follows that the OR of all PIs
in is an MSOP for STn; k.
Consider the set MI of n minterms of
the form xi1 xi2 .xik xik1 xik2 .xin , where ij 2
of minterms that are 1 when exactly k of the n
variables are 0. No PI for STn; k covers two or
more minterms in MI. As such, MI is a set of
independent minterms and at least n PIs are
needed.
is formed as follows: For each minterm mt in
MI, apply Algorithm 1.1 below, producing Pmt,a
PI that covers mt. Add Pmt to . Since noPI
covers two or more minterms in MI, has n
distinct PIs. Since Pmt has exactly k 0s and k 1s, it
covers only minterms in STn; k. Next, we show
that covers all minterms in STn; k by applying
Algorithm 1.1 to an arbitrary minterm mt0 of
producing Pmt0 , a PI that covers mt0.
from Pmt0 by setting all -s to 1s. Applying
Algorithm 1.1 to mt00 yields Pmt00 that is identical
to Pmt0 , from which we can conclude Pmt0 2 .
Algorithm 1.1 (Produce a PI that covers a given
minterm).
Input: Minterm mt  mt0mt1 .mtn  1
Output: Prime implicant
Pmt  Pmt0Pmt1 .Pmtn  1
(Initially, Pmtifor all i where
1. ZeroOnePairs  0
2. Repeat until ZeroOnePairs  k do {
if
and mtimti  s01
then
and ZeroOnePairs ZeroOnePairs  1g;
where index addition is mod n (in this
algorithm, we assume that subscript indices
range from 0 to n  1, i.e., the variables are
It is straightforward to show that Algorithm 1.1
produces a PI in if the minterm input has at
least k 1s and k 0s. This PI may be different
depending on the values of i chosen in each
repetitive step.
Assume
We can form an ISOP of STn; k as follows:
F  xnF1 _ xnF2 _ F3;
where
a. F1 is an SOP such that each product term
is formed as the AND of i) a set X1 of
fxng, and of ii) k uncomplemented
variables from X fxngX1,wherethe
indices of the uncomplemented variables
are all as small as possible (given the choice
of X1). Because X1 can be chosen in nk1
ways, F1 has nk1 product terms.
b. F2 is an SOP such that each product
term is formed as the AND of i) a set
X2 of k  1 uncomplemented variables,
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 945
where X2 X fxng and of ii) k complemented
variables from X fxngX2, where
the indices of the complemented variables are
all as small aspossible. Because X2 can be
chosen in nk1 ways, F2 has nk1 product
terms.
c. F3 is one of the WSOPs for STn  1;k.
Fromthe inductive hypothesis, F3 has
F is an expression for STn; k as follows:
Consider a minterm m in STn; k.Ifm has at
least k 1s and at least k 0s, regardless of the
value of xn, then m is covered by F3.Ifm has
exactly k 0s, including a 0 value for xn, and at
least k 1s, then it is covered by xnF1.Ifm has
exactly k 1s, including a 1 value for xn, and at
least k 0s, it is covered by xnF2. Thus, F
covers all minterms in STn; k. Because each
PI in xnF1 and xnF2 (and also in F3) has
exactly k uncomplemented and exactly
complemented variables, F covers only
minterms with at least k 0s and at least k 1s,
i.e., only minterms in STn; k. It follows that
F is an SOP for STn; k.
If F has no redundant PIs, its n1
k1
k1
an ISOP for STn; k. Thus,

Next, we show that F has no redundant
PIs. First, each PI in xnF1 covers a minterm m0
having k 0s and n  k 1s that is not covered
by any combination of PIs from xnF2 and F3.
Thus, no PI in xnF1 is redundant. By a similar
argument, no PI in xnF2 is redundant.
Second, no PI in F3 is redundant, as follows:
Since F3 is a WSOP for STn  1;k,noPIin
F3 is covered by the OR of one or more PIs in
F3. If the OR of PIs from xnF1 and xnF2 covers
aPIP from F3, then it follows that at least
one product term P1 in F1, when ANDed
with at least one product term P2 in F2, yields
a non-0 result. Let
and
If P1P2  0,nosi is the same as a uj and no tpis the same as a vq. But, t1;t2; ., and tk were
chosen to be as small as possible without
overlapping s1;s2; .,andsk1, while
v1;v2; ., and vk were chosen to be as
small as possible without overlapping
u1;u2; ., and uk1. Consider the indices
I f1; 2; .;kg. The smallest index in I that
appears neither in S fs1;s2; .;sk1g nor in
U fu1;u2; .;uk1g appears in both T
ft1;t2; .;tkg and V fv1;v2; .;vkg, causing
P1P2  0, a contradiction. tu
Theorem 3.5. STm; kr has the following properties:
r
r mr
2. MSOP : STm; k  .
3.
Proof. Items 1, 2, and 3 follow from the observation that a
minterm in the product function STm; kr can be
viewed as the AND of a minterm from each of the factor
functions STm; k. Thus, a PI of STm; kr can be
viewed as the product of a PI from each STm; k and
directly.
Also,
r mr
r
follows directly. That is, m is an upper bound on the
number of PIs in an MSOP for STm; kr, as an ISOP for
STm; kr can be formed as the AND of PIs from the
MSOPs of STm; k. As is shown by Voight and Wegener
[36], certain product functions can have fewer PIs in their
MSOPs than the product of the number of PIs in the
MSOPs of the factor functions. However, when the factor
functions are STm; k, we can observe the following: Let
M be the set of minterms covered by STm; k, in which
exactly k variables are uncomplemented. Since the PIs of
exactly k uncomplemented and k complemented
variables, none cover two or more minterms
in M. It follows that at least m PIs are needed to cover
STm; k. It follows that at least PIs are needed to
cover the minterms in STm; kr that are the product of
minterms in the set M for each factor function. Thus,
r mr
A WSOP for STm; kr can be formed as the product of
WSOPs for each factor function. Since 2 m  2k is a
lower bound on the number of PIs in each factor
directly. tu
Theorem 7.1. Let GF be the graph representation of F. F is an
ISOP of STn; 1 iff GF is minimally strongly connected.
Proof. (if) Consider a minimally strongly connected digraph
GF , where F is its corresponding SOP. Thus, for every
edge xj;xi in GF , there is an implicant xjxi in F.Onthe
contrary, assume that F is not an ISOP for STn; 1. That
is, either 1) F does not cover STn; 1 or 2) F covers
STn; 1 but has a redundant PI.
Consider 1). If F does not cover STn; 1, then there is
a minterm mt such that mt either a) has no complemented
variables or no uncomplemented variables, but F is 1
for this assignment or b) has at least one uncomplemented
variable and at least one uncomplemented variable,
but F is 0 for this assignment. The first part, a), is not
possible; all PIs cover only minterms with at least one
946 IEEE TRANSACTIONS ON COMPUTERS, VOL. 50, NO. 9, SEPTEMBER 2001
complemented variable and at least one uncomplemented
variable. The second part, b), is also not possible, as
follows: Because GF is strongly connected, there is a path
xj  xk1 ;xk2 ; ;xkm  xi, from xj to xi. Since xj  0 and
xi  1, the assignment of values to xk1 ;xk2 ; ., and xkm
corresponding to mt has the property that there is an s
such that xks  0 and xks1  1. The corresponding PI
xks xks1 is in F and is 1 for the assignment associated
with mt. Thus, F covers mt.
Consider 2). If F covers STn; 1, but has a redundant
PI, xjxi, then F0, which is F with xjxi removed, also
covers STn; 1. But, GF0 is GF with one edge, xjxi,
removed. It follows that GF is not minimally strongly
connected.
(only if) Let GF be a graph representation of an ISOP F
of STn; 1. Assume, on the contrary, that GF is not
minimally strongly connected. That is, either 1) GF is not
strongly connected or 2) GF is strongly connected, but is
not minimal.
If GF is not strongly connected, there are two
nodes xj and xi such that no path exists from xj to
xi. Let Sucxj be the set of all nodes for which
there is a path from xj, i.e., all successors of xj. Let
Prexi be the set of all nodes for which there exists
a path to xi, i.e., all predecessors of xi. Consider a
minterm mt that is 0 for xj and all variables associated
with nodes in Sucxj and is 1 for xi and all variables
associated with nodes in Prexi. Since there is no path
from xj to xi, Sucxj\Prexi and such an
assignment assigns exactly one value to nodes in
Sucxj[Prexi[fxj;xig. Choose the values of all
other variables to be 1 (or 0). No edge in GF has a 0 at
its tail and a 1 at its head. Thus, all PIs are 0 and F is not
an SOP for STn; 1. It is, thus, not an ISOP, a contradiction

If GF is strongly connected, but is not minimal, there
is at least one edge xj;xi that can be removed without
affecting the connectedness of GF . It follows that GF0 ,
where F0 is F with xjxi removed, is a graph representation
of F0, an SOP for the same function as F. Thus, F is
an SOP, but not an ISOP, contradicting the assumption.tu
Theorem 7.2. The number of MSOPs for STn; 1 is n  1!.
Proof. From Theorem 7.1, an MSOP for STn; 1 corresponds
to a directed graph with the fewest edges which
is strongly connected, but is not strongly connected
when any edge is removed. Such a graph is a directed
cycle of arcs through all variables. As such, it represents
a cyclic permutation on the variables. The number of
such permutations is n  1!. tu
Lemma 7.2. Let F be an ISOP of STn; 1. F is WSOP iff
complementing all variables in F leaves F unchanged.
Proof. (if) Let F be an ISOP that is unchanged by a
complementation of all variables. This implies that if xixj
is a PI of F, then so also is xjxi. It follows that if xi;xj is
an edge in GF , then xj;xi is an edge in GF . That is, all
edges between nodes occur in pairs, one going one way
and the other going the other way. In such a graph, there
are n  1 pairs or 2n  2 edges in all. (Replace each pair
by an undirected edge. If the directed graph is strongly
connected, the undirected graph must be connected.
From Harary [14], there must be n  1 edges.) Since there
are 2n  2 edges in GF , there are 2n  2 PIs in F and,
thus, F is a WSOP.
(only if) Let F be a WSOP of STn; 1. We show that
GF consists of cycles of length 2 only. Thus, if xixj is a PI
of F, so also is xjxi. It follows that complementing all
variables of F leaves F unchanged. Suppose that GF
contains a cycle of length m, where m>2. Such a cycle
represents a strongly connected subgraph of GF in which
there are m edges. However, the cycle can be replaced by
a minimally strongly connected graph with more edges
(e.g., where all edges occur in pairs). The result is a
strongly connected graph, where the deletion of an edge
leaves it unconnected, which has more edges than the
original version. This contradicts the statement that F is
a WSOP. tu
Theorem 7.3. The number of WSOPs for STn; 1 is nn2.
Proof. From Theorem 7.1, a WSOP for STn; 1 corresponds
to a minimally strongly connected graph with the largest
number of edges. We show that this graph consists of
cycles of length 2 exclusively, as follows: Suppose, on the
contrary, the graph has a cycle of length m>2. There are
m edges in this cycle. However, this subgraph can be
replaced by a subgraph with more edges, 2m  1.It
follows that the original graph does not represent a
WSOP.
Each cycle of length 2 connects two nodes by edges in
the two directions. Replace each pair of edges by an
undirected edge, forming an undirected tree with n  1
edges. Thus, there are 2n  1 PIs in a WSOP for
STn; 1. This proves Theorem 3.2. It follows that the
number of WSOPs is the number of undirected trees on n
labeled nodes. Cayley [5] in 1889 showed that this
number is nn2. tu
Theorem 7.4. The number of ISOPs for STn; 1 with n  1 PIs
is

Proof. From Theorem 7.1, an ISOP of STn; 1 that has n  1
PIs corresponds to a minimally strongly connected graph
with edges. All graphs with this property have two
cycles of nodes, of which i are common, where
2. We can represent each instance as a
permutation of nodes that has been divided into three
nonempty sets, the i common nodes, nodes N1, in one
cycle only, and nodes N2 in the other cycle only. N1 and
N2 must be nonempty since an empty set corresponds to
a redundant edge. There are n! ways to permute the
nodes and n1 ways to divide them into threenonempty sets. However, this double counts graphs
since interchanging N1, and N2 does not change the
graph. Thus, the total number of graphs with n  1 edges
is 1 n1 n!. tu
SASAO AND BUTLER: WORST AND BEST IRREDUNDANT SUM-OF-PRODUCTS EXPRESSIONS 947

ACKNOWLEDGMENTS

This work was supported in part by a Grant in Aid for
Scientific Research of the Ministry of Education, Culture,
Sports, Science, and Technology of Japan and in part by
NPS Direct Funded Grant UHCD1. Discussions with
Dr. Shin-ichi Minato were quite useful. Mr. Munehiro
Matsuura and Mr. Shigeyuki Fukuzawa did part of the
experiments. The authors acknowledge the contributions of
two referees. This paper is an extended version of T. Sasao
and J.T. Butler, Comparison of the Worst and Best Sum-of-
Products Expressions for Multiple-Valued Functions,
Proceedings of the IEEE International Symposium on Multiple-Valued
Logic, pp. 55-60, May 1997.


--R



Logic Minimization Algorithms for VLSI Synthesis.






Logic Design of Digital Systems


Introduction to Switching and Automata Theory.
Graph Theory.







Logic Design and Switching Theory.







Representation of Discrete Functions

Switching Theory for Logic Synthesis
Advanced Logical Circuit Design Techniques.
The TTL Data Book for Design Engineers



--TR
PALMINIMYAMPERSANDmdash;fast Boolean minimizer for personal computers
Two-level logic minimization: an overview
Switching Theory for Logic Synthesis
Logic Design and Switching Theory
Logic Design of Digital Systems
Logic Minimization Algorithms for VLSI Synthesis
A Remark on Minimal Polynomials of Boolean Functions
A State-Machine SynthesizerMYAMPERSANDmdash;SMS
An application of multiple-valued logic to a design of programmable logic arrays

--CTR
Alan Mishchenko , Tsutomu Sasao, Large-scale SOP minimization using decomposition and functional properties, Proceedings of the 40th conference on Design automation, June 02-06, 2003, Anaheim, CA, USA
Olivier Coudert , Tsutomu Sasao, Two-level logic minimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
symmetric functions;worst sum-of-products expressions;prime implicants;logic minimization;multiple-output functions;minimum sum-of-products expressions;graph enumeration;irredundant sum-of-products;heuristic minimization;complete sum-of-products expressions;minimally strongly connected digraphs