数理解析研究所講究録
第 876 巻 1994 年 50-59

50

An Exact Minimization of AND-EXOR
Expressions Using Reduced Covering Functions
笹尾 勤
Tsutomu SASAO
Department of Computer Science and Electronics
Kyushu Institute of Technology, Iizuka 820, Japan

August 9, 1993
Abstract
This paper considers a metliod to derive an EXOR sum-of-products expression (ESOP) having theminimum number of products for a given logic function. The minimization method uses a reduced
covering function, which is an improvement of the method proposed by Perkowski and ChrzanowskaJeske. Binary Decision Diagrams (BDDs) are used to obtain exact solutions. Various techniques toreduce computation time and memory storage are developed. Experimental results for functions withup to 9 variables are shown.

I

Introduction

EXOR sum-of-products expressions (ESOPs) are obtained by EXORing arbitrary products. ESOPs
have several advantages over sum-of-products expressions (SOPs) [23]. The most important one isthat ESOP realizations are often less expensive than SOP realizations. For example, to represent
arbitrary function of four variables, ESOPs require, on the average, 3.66 products while SOPs require
4.13 products [25]. We conjecture that this is true for an arbitrary . We have also proved that anarbitrary function of variables can be realized with at mostproducts when $n\geq 6$ , while SOPs
require at mostproducts [25]. In addition, we demonstrated that ESOPs require fewer products
and fewer literals than SOPs to represent arithmetic functions and other functions [24]. An ESOP
requires at most 2
products to realize an arbitrary n-variable symmetric function, where $n=2r$ .
For any symmetric function, an ESOP requires no more products than an SOP $[23, 20]$ . Because manyof the arithmetic functions have symmetrical properties, ESOPs are useful for arithmetic circuits. In
most technologies, EXOR gates are more expensive than OR gates. However, even if we assume thatthe cost of a 2-input EXOR is twice as expensive as a 2-input NOR, the EXOR based circuits are
more economical than ones based on only ANDs and ORs [24]. Also, in LUT based FPGAs [21], ORs
and EXORs have exactly the same cost and the same propagation delay.
In the ESOP minimization problem, one seeks an ESOP having the minimum number of products.
Many papers have considered this problem [6, 18, 16, 23, 22, 7, 9, 2]. Recently, Perkowski and
Chrzanowska-Jeske[19] formulated the problem by using a Helliwell equation. Their formulation is
to find a 3“ bit vector with the minimum weight satisfying the Helliwell equation, where is thenumber of the variables in the given logic function. They also presented various methods to solve thiscomputational complexity of their methods areproblem. However,
because they consider
most of the combinations of the 3 bit vectors. Thus,
order of the complexity is the same as inexhaustive search. However, their formulation bas provided insights into exact ESOP minimization.
In tbis paper, we present an improved method for ESOP minimization by using reduced coveringfunction and BDDs.
$n$$2^{n-2}$$n$$2^{n-1}$$\cdot 3^{r}$$n$$t1_{1}e$$O(2^{3^{\mathfrak{n}}})$$n$$t1_{1}e$II

Minimization of SOPs and ESOPs

2.1

Minimization of SOPs

Suppose that we want to obtain a minimum SOP representing an n-variable function . Assume weare given the set of true minterms (l-cells in Karnaugh map) and the set of all prime implicants (PIs)$f$

51. Let there be PIs for . Any SOP of is a subset of PIs that covers $aU$ true minterms. For
some SOP for , let be a logic variable that is 1 iff the j-th PI is in this SOP. Thus, the problem offinding a minimal SOP is identicaJ to the problem of finding an assignment for thesuch that theis minimum. We derive such an assignment
corresponding SOP represents and the weightby using the Petrick Equation defined as follows:
for

$f$

$\xi$

$f$

$f$

$f$

$g_{j}$$g_{j}’ s$$\sum_{i=0}^{\xi-1}g_{j}$$f$,$P(g_{0},g_{1}, \cdots,g_{\xi-1})=\bigwedge_{:=0}^{N-1}S_{i}$$N$ is the number of true minterms in
, and
where
represents the set of PIs
that covers the i-th minterm. . is 1 iff the i-th true minterm is covered by at least one PI, and$P(g_{0},g_{1}, \cdots , g_{\xi-1})$ is 1 iff every minterm is covered by at least one PI[17].
A solution to the SOP minimization problem is an assignment of $O’ s$ and l’s to : that satisfies $P$
with the fewest l’s.
$f$

$S_{i}=v_{g_{j}\in\tau_{:}g_{j}},$$T_{i}$$S_{*}$$g$

Example 2.1 Let us derive the minimum SOPs for the function $f$ shown in Fig. 2.1 by using thePetrick equation. Note that $f$ has 6 min terms and 6 $PIs$, which are shoum in Figs. 2.2 and 2.3. For

Figure 2.1:

Figure 2.2: Minterms

Figure 2.3: PIs

these minterms, we have the following relations:$m_{0}$$m_{1}$$m_{2}$$m_{3}$$m_{4}$$m_{5}$

:
:
:
:
:
:

$S_{0}$$=$$S_{1}$$=$$g_{1}Vg_{3}$$S_{2}$$=$$g_{1}Vg_{4}$$S_{3}$$=$$g_{0}Vg_{5}$$S_{4}$$=$$g_{2}\vee g_{5}$$S_{5}$$=$$g_{2}\vee g_{4}$$g_{0}\vee g_{3}$

,
,
,
,
, and

.

All the minterms are covered iff $S_{i}=1(i=0, \cdots, 5)$ . This is true iff $P(g)=1$ , where$P(g)=(g_{0}\vee g_{3})(g_{1}\vee g_{3})(g_{1}\vee g_{4})(g_{0}\vee g_{5})(g_{2}\vee g_{5})(g_{2}\vee g_{4})$.

Two assignments satisfyin$gP(g)=1$ with minimum weights are $g_{0}=g_{1}=g_{2}=1$ and $g_{3}=g_{4}=$. One can find them by expanding $P(g)$ into an SOP form. Thus, the corresponding minlmum
SOPs for areand.

$g_{5}=l$$f$$\overline{x}_{1}\overline{x}_{2}\vee x_{1}\overline{x}_{3}\vee x_{2}x_{3}$$\overline{x}_{2}\overline{x}_{3}\vee x_{1}x_{2}\vee\overline{x}_{1}x_{\}$ESOP minimization problem

2.2

In the case of ESOP minimization, we have to consider all the products instead of just the PIs. Also,
the covering problem is an odd-even type, since $1\oplus 1=0$ . This problem corresponds to finding aminimum cost solution of the Helliwell Equation $H(g)=1,$ $w1_{1}ereH(g)$ is a product-of-EXOR sums
expression defined as follows:$H(g_{0},g_{1}, \cdots,g_{\xi-1})=\bigwedge_{i=0}^{N-1}S_{i}$.

,$N$ is the total number of the cells in the Karnaugh map $(=2”)$ ,where
and is the number of all possible products $(=3^{n})$ . $g_{j}=1$ iff the j-th product is contained in
the ESOP.
shows the condition that each true minterm is covered by products an odd number oftimes, and each faJse minterm (O-cell in $I\langle amaugh$ map) is covered by products an even number oftimes. $H(g_{0},g_{1}, \cdots , g_{\xi-1})$ shows that products cover true minterms an odd number of times and false
minterms an even number of times. Thus, the number of variables in the Helliwell function is .
$S_{i}= \sum_{gj}\epsilon\tau$$\oplus g_{j}\oplus f(a;)\oplus 1,$$\xi$$S_{i}$$3^{\mathfrak{n}}$52
Example 2.2 Let us derive the minimum ESOPs for the function shown in Fig. 2.4 by using theHelliwell equation. Note that $N=4$ is the number of cells in the map, and $\xi=9$ is the number ofloops in Fig. 2.6. For each cell, we have$f$$m_{0}$$m_{1}$$m_{2}$$m_{3}$

:
:
:
:

,
,
, and

$S_{0}$$=$$g_{0}\oplus g_{2}\oplus g0\oplus g_{8}\oplus 1\oplus 1$$S_{1}$$=$$g_{1}\oplus g_{2}\oplus g_{7}\oplus g_{8}\oplus 0\oplus 1$$S_{2}$$=$$g_{3}\oplus g_{5}\oplus g_{6}\oplus g_{8}\oplus 0\oplus 1$$S_{3}$$=$$g_{4}\oplus g_{5}\oplus g_{7}\oplus g_{8}\oplus 1\oplus 1$.

True minterms are covered by loops an odd number of times and fatse minterms are covered by loops

Figure 2.4:

Figure 2.5:

Figure 2.6: Products
an even number of times iff $S_{i}=1(i=0,1,2,3)$ . This is true iff the Helliwell equation is $H(g)=1$ ,where$H(g)$$=$.

$(g_{0}\oplus g_{2}\oplus g_{6}\oplus g_{8}\oplus 1\oplus 1)\cdot(g_{1}\oplus g_{2}\oplus g_{7}\oplus g_{8}\oplus 0\oplus 1)$$(g_{3}\oplus g_{5}\oplus g_{6}\oplus g_{8}\oplus 0\oplus 1)\cdot(g_{4}\oplus g_{5}\oplus g_{7}\oplus g_{8}\oplus 1\oplus 1)$.

Assignments that make $H(g)=1$ with minimum weights are $g_{0}=g_{4}=1,$ $g_{2}=g_{7}=1$ or $g_{5}=g_{6}=1$ .
, respectively.
The corresponding minimum ESOPs areand$x_{2}\oplus\overline{x}_{1}$$x_{1}x_{2}\oplus\overline{x}_{1}\overline{x}_{2},\overline{x}_{2}\oplus x_{1}$[19] presented various methods to find a minimum solution for the Helliwell equation, but did not show
any computational results. To evaluate the usefulness of their methods, we implemented a similar
method and confirmed that “the methods are very time and memory consuming” [19].

III

Reduced Covering Function

This section presents a new method for exact ESOP minimization by using reduced covering function .
variables, and requires fewer variables than the Helliwell function. Let
This function involves 2
be an n-variable function $(n\geq 5),$ $B=\{0,1\}$ , and $T=\{0,1,2\}$ . Let $X=(x_{1}, x_{2}, \cdots,x_{n})$ be avector of binary variables, and $X=(X_{1},X_{2})$ be a partition of $X$ . Let $(n-r)$ be the number of, and be the number of variables in, where $r=0,1,2,3$ , or 4. Then, can bevariables in
represented as
,
(3.1)
$s$

$r\cdot\cdot 3^{n-r}$$f$$X_{1}$$f$$X_{2}$$f$$f(X_{1}, X_{2})= \sum_{a}\oplus X_{1}^{\dot{a}}\cdot g(a:X_{2})$where $a\in T^{n-r}$ ,$\overline{x}_{i}$$X_{1}^{a}=x_{1}^{a_{1}}\cdot x_{2^{2}}^{a}\cdots\cdot\cdot x_{n-r}^{a_{*-r}}$,$x^{a}:=x$:1$a_{\dot{*}}=0$$a:=1$ ,$a:=2$

53
and $g(a:X_{2})$ is an r-variable function.
By assigning a constant $b\in B^{n-r}$ to$X_{1}$in (3.1), we have$f(b, X_{2})= \sum_{c\geq Rb}\oplus g(c:X_{2})$

,

(3.2)

where $\sum\oplus denotes$ the EXOR with respect to $c\in T^{n-r}$ satisfying $c\geq Rb$ . The symbol
denotesthe binary relation $\{(0,0), (1,1), (2,2), (2,0), (2,1)\}$ . For each , there are $2^{n-r}$ different that satisfy$c\geq Rb$ . Because there are $2^{n-r}$ different, we have $2^{n-r}$ different equations of the form (3.2). Next,
by assigning a constant $d\in B$ “ toin (3.2), we have$\geq R$

$b$

$c$

$b$

$X_{2}$$f(b, d)= c\geq b\sum_{R}\oplus g(c :

d)$

.

(3.3)

There are $2^{n-r}$ different and $2^{n-r}$ different
so we have $2”-r$ . $2‘=2$ “ different equations of form
(3.3). Note that $g(c:d)$ is either or 1. (3.3) holds for all possible combinations of and at thesame time if and only if $R(g)=1$ , where$b$$d_{r}$$b$$0$$R(g)= \wedge([\sum g(c :

$d$

(3.4)

d)]\oplus f(b, d)\oplus 1)$$(b,d)c\geq Rb$

anddenotes the logical product with respect to all possible $b\in B^{n-r}$ and $d\in B^{r}$ . $R(g)$ iscalled a Reduced Covering Function (RCF).
Let $g(c:d)$ be Boolean variables, where $c\in T^{n-r}$ and $b\in B^{r}$ . Then, the total number of variablesin RCF is. An assignment for $g(c, d)$ that satisfies $R(g)=1$ is called a solution of $R(g)=1$ .
A minimum ESOP for can be written in the form (3.1). Let $g(a:X_{2})$ be an r-variable function.
We want to obtain 3 $n-r$ such functions. Because $g(a:X_{2})$ can be written as$\bigwedge_{(b,d)}$$2^{r}\cdot 3^{n-r}$$f$$g(a : X_{2})= \sum_{d\in B^{r}}\oplus X_{2}^{d}g(a :d)$,can be obtained from the set of $g(c:d)$ that satisfy the RCF. A minimum ESOP corresponds
to the solution of the RCF with the minimum value of the cost function:$g(a:X_{2})$$\sum_{a}\tau(g(a:X_{2}))$

(3.5)

,

where
denotes the arithmetic sum with respect to all possible $a\in T^{n-r}$ , andnumber of products in a minimum ESOP for . Thus, we have the following theorem.

$\tau(g)$$\sum_{a}$denotes the$g$Theorem 3.1 A minimum ESOP of an n-variable function corresponds to an assignment of the $RCF$
having a minimum cost of (S.5).

Because we have a table for minimum ESOPs for up to 4-variables, the values of $\tau(g(a:X_{2}))$ for$r=0,1\cdots$ , and 4 are available.

Cost functions$0)$

When $r=0$ . $g(a:X_{2})=g(a)$ are O-variable functions (constants), and do not depend on.
There aredifferent $g(a)$ , and they correspond to the 3“ different products of variables. In
this case, the RCF is the same as the Helliwell function [19]. The cost function is$X_{2}$$3^{n}$$n$$\tau(g(a:X_{2}))=g(a)$.

1) When $r=1$ . $g(a:X_{2})$ are l-variable functions and can be represented as$g(a : X_{2})=X_{2}^{0}\cdot g(a :0)\vee X_{2}^{1}\cdot g(a$

:1 .
$)$

An ESOP uses at most one product to represent $g(a:X_{2})$ , and requires a product only when$g(a:O)\vee g(a;1)=1$ . Thus, the cost function is$\tau(g(a:X_{2}))=g(a :O)\vee g(a$

:1 .
$)$

54
2) When $r=2$ . $g(a:X_{2})=g(u, v)$ are 2-variable functions. An ESOP uses at most two productto represent $g(a:X_{2})$ , and the cost function is$s$,$\overline{u}v^{0}u^{\frac{u}{v}},oru\cdot v=.1,\overline{u.},,\overline{v}’ v,\overline{u}\cdot\overline{v}=$$\tau(g(a :X_{2}))=\{\begin{array}{l}01wheng(u,v)wheng(u,v)2otherwise\end{array}$3) When $r=3$ . $g(a:X_{2})$ are 3-variable functions. An ESOP usae at most three products torepresent $g(a : X_{2})$ . The cost function is complex, but it is possible to represent by logic
functions.
4) When $r=4$ . $g(a:X_{2})$ are 4-variable functions. An ESOP uses at most 6 products. The costfunction is complex, but it is possible to represent by logic functions.

Example 3.1 Let us obtain minimum ESOPs for the function in Fig. 2.4 by using $RCF$. Let $X_{1}=(x)$and $X_{2}=(y)$ be the partition of $X=(x, y)$ . In this case, we obtain the minimum ESOP having thefollowing form:$f(x, y)=\overline{x}\cdot g(0 :y)\oplus x\cdot g(1 :y)\oplus 1\cdot g(2 :y)$.

Now, we will find three functions such that $\sum_{i=0}^{2}\tau(g(i : y))$ is minimum. Because ( : y) can be
expanded as$g$$g(i : y)=\overline{y}\cdot g(i :0)\oplus y\cdot g(i$

$i$

:1 ,
$)$

we have the following $e\varphi ression$ :$f(x, y)=\overline{x}\cdot\overline{y}\cdot g(O : 0)\oplus\overline{x}\cdot y\cdot g(O : 1)\oplus x\cdot\overline{y}\cdot g(1 :By assigning$(\theta,\theta),$$(0,1),$$(1,\theta)$0)\oplus x\cdot y\cdot g(1 :1)\oplus 1\cdot\overline{y}\cdot g(2 ::1 .

0)\oplus 1\cdot y\cdot g(2$$)$

and $(1,1)$ into $(x,y)$ , we have four equations:$f(O, O)$$=$$g(O:O)\oplus g(2:0)=1$ ,$f(0,1)$$=$$g(O : 1)\oplus g(2 :$f(1,0)$$=$$g(1:O)\oplus g(2:0)=0$ ,$f(1,1)$$=$$g(1 : 1)\oplus g(2 :

1)=0$

1)=1$

,
and

.

The $RCF$ is$R(g)$$=$$[g(O : O)\oplus g(2 :O)][g(0 :1)\oplus g(2 :$[g(1 : O)\oplus g(2 :O)\oplus 1][g(1 :.

1)\oplus 1]$

1)\oplus g(2 :

1)]$

.

The minimum assignments that make $R(g)=1$ true are$g(0:0)$$=$$g(1:1)=1$ ,$g(1:0)$$=$$g(1:1)=g(2:0)=1$ , and$g(O : 0)$$=$$g(O : 1)=g(2 : 1)=1$ .

The corresponding minimum ESOPs are, respectively. Fig. 3.1 showsandthe role of the variables. In the case of $RCF$, the sets of variables represent logic functions.
$x_{1}x_{2}\oplus\overline{x}_{1}\overline{x}_{2},$$x_{1}\oplus\overline{x}_{2}$$\overline{x}_{1}\oplus x_{2}$Figure 3.1: The role of variables.

55
IV

optimization Using Binary Decision Diagrams.

A minimum ESOP for a given function corresponds to an assignment for RCF with the minimum cost.
In this part, we show a method to find uch assignments by using Binary Decision Diagrams (BDDs)$[3, 15]$ . Let $H(g)=1$ be a Boolean equation showing the constraints of an optim\’ization problem,
where $g=(g_{0},g_{1}, \cdots,g_{\xi-1})$ . For example, $H(g)=1$ can be the Petrick equation or the Helliwellequation. Assignments satisfying $H(g)=1$ are called feasible solutions. When $H(g)$ is represented
by a BDD, a path from the root node to a constant 1 node corresponds to a feasible solution. Sucha path is called a l-path of a BDD. By attaching a cost to the set of edges, we can make the paths
represent the cost of the solution. Thus, we can convert the optimization problem into the shortest
path problem [13]. The BDD for $H(g)$ is usually too large to build, so we need various techniques toreduce the size of the BDD.
$s$

Example 4.1 Fig. 4.1 is the $BDD$ for Helliwell function in Bxample 2.2. Fig. 4.2 is the $BDD$ for$RCF$ in Example 3.1. Note that $RCF$ requires fewer nodes than the Helliwell function.

$\mathfrak{g}\{0:0)$$0$$\tau$$g(0;1)$$2$$\mathfrak{g}\{1:0)$$3$4$g\{1;1)$$5$

6$9(2:0)$$7$$g(2;1)$$\epsilon$

Figure 4.1: BDD for Helliwell function

V

Figure 4.2: BDD for RCF

Number of Variables for RCF.

This part considers the number of variables of a RCF for the optimization of an ESOP with variables.
Suppose that we use the table of minimum ESOPs with variables. Then, the number of variablesin RCF is $\xi(n, r)=2^{r}\cdot 3^{n-r}$ . Table 5.1 shows the number of variables for RCFs. It shows that asincreases, $\xi(n, r)$ decreases. However, the computation time for cost functions and $U(t_{1})$ will increase
as increases. Note that the number of the variables in the RCF does not always show the complexityof the problem.
$n$

$r$

$r$

$r$

VI

Various Techniques to Reduce Computation Time andMemory Requirement.

The BDD formulation of the problem is straightforward. However, the BDDs so formed are usually
very large. In general, almost all the computation time is spent in the generation of BDDs, and the
CPU time for finding the shortest path is relatively small. Thus, the problem is how to generate the
BDD efficiently.

6.1

Lower bound on the number of products.

Although we have various ways to reduce the computation time and memory requirement for the construction of BDDs, the best way is not to construct a BDD. We have very good heuristic minimization

56

program EXMIN2, which finds near optimum solutions quickly. Suppose we know that the ESOP for
products. If
products, and EXMIN2 produced an ESOP witha function requires at least, then the solution obtained by EXMIN2 is a minimum, and we can stop the procedure without
generating the BDD. We have a method to obtain the lower bound on the number of products in
ESOPs.
$f$$t_{1}$$t_{2}$$t_{1}=t_{2}$Theorem 6.1 Let the function be expanded as
at least $\max\{L1, L2\}$ products, where$f$$f;_{2}=f_{1_{0}}\oplus f_{i_{1}},$$q_{j}$$f=\overline{x}_{i}\cdot f_{i_{\Phi}}\oplus x_{i}\cdot f:_{1}$$L_{1}$$=$$\frac{1}{2}\max^{n}\{\tau(f:_{0})i=1+\tau(f:_{1})+\tau(f_{2_{2}})\}$$L_{2}$$=$$1+ \min_{lj}\{L_{1}(q_{j}\oplus f)\}$. Then, the ESOP for contains
$f$

, and

represents a product containing at least one minterm of $f$ , and$\tau(g)$of the products in a minimum ESOP for .

is the number$g$

To use tlie above theorem, we have to know the number of the products in the minimum ESOPs for$(n-1)$ variable functions. Up to $n=6$ , we can do this by a table look-up method [12].

Upper bound on the number of $pro$ ducts.

6.2

EXMIN2 is a heuristic ESOP simplification algorithm and produces near optimum solutions [26].
be the cost of a near optimum solution ofLet
EXMIN2, and let
be the logic function showing that the cost is less than .
$t_{1}$$Q$

1$U(t_{1})$$t_{1}$

2

3$U(t_{1})=\{01$$otherwise(\sum\tau(g(n.:X_{2}))\geq t_{1}$4$s$We can generate the BDD for $R(g)\cdot U(t_{1})$ , insteadof for $R(g)$ . This will drastically reduce the BDD
size and computation time. $R(g)\cdot U(t_{1})$ is called a
Modified Reduced Covering Function (MRCF).
Example 6.1 Fig. 6.1 is the $BDD$ for $H(g)\cdot U(3)$ ,which
the modified $RCF$ ut th $r=0$ . This $BDD$
has only three l-paths.

6
7$\epsilon$$\dot{u}$6.3

Figure 6.1: BDD for $H(g)\cdot U(3)$Methods for multiplication.

To generate the BDD for MRCF, we have to $multiply4^{n}$ parity functions. For each multiplication ofa parity function, the number of nodes in the BDD tends to be double. Thus, we often encounter the
memory overflow errors during the generation of BDDs. To avoid such errors, we carefully choose theorder of the multiplication. Currently, we use the order that increases the least number of variablesin the BDD for each step.

57
6.4

Zero-suppressed BDD.

A MRCF represents a set of vectors that satisfy the RCF. Although the number of variables is $O(3^{n})$ ,“the number of non-zero elements in the vectors is $O(2^{n})$ , because
and the weight is less than. Thus, MRCF represents a set of vectors with small weight. Zero-suppressed BDDs [15] are avariant of BDDs, and represent such sets very efficiently. By using zero-suppressed BDDs, we canreduce the computation time and memory requirement significantly.
$t_{1}\leq 2$$t_{1}$

Minimization Algorithm.

VII

Step 1. Let $F$ be an ESOP for$t_{1}arrow\tau(F)$,$t_{2}arrow Lower$$f$

simplified by EXMIN2.

bound obtained by Theorem 6.1.

Step 2. If $t_{1}=t_{2}$ , then$F$

is the minimum and stop.

Step 3. Construct the BDD for $R(g)\cdot U(t_{I})$ .
If the BDD represents the constant function, then $F$ is the minimum and stop.
$0$

Step 4. Find a shortest path.
Step 5. Construct the ESOP corresponding to tlie path.

VIII

Experimental Results

We coded the algorithm in , and implementing it on an HP9000 Model 720 workstation with 64
Mega-byte main memory. We used two types of BDD packages, one is based on the conventional$C$$edgesBDD|_{14].Inaddition,wedeve1opedcodetogeneratetheBDDsforboundingfunctions.Upperand}^{1]andtheotherisbasedonzero-\sup pressedBDD[15].Neitherofthemusecomp1emented}$

lower bounds on the number of the products in ESOPs are obtained by separate programs $[26, 12]$ .

8.1

With Helliwell functions.

Up to $n=3$ , we could easily build BDDs of Helliwell functions. Thus, the minimization of 3-variable
functions was easy. However, BDDs of Helliwell functions for $n=4$ involve $3^{4}=81$ variables andwere very expensive.

8.2

With Modified Reduced Covering Functions.

The BDDs of MRCF for $n=5$ were easy to derive, and we could minimize all the 5-variable functions
that we tried. The most complicated 5 variable function required 9 products, and EXMIN2 produced
these solutions. However, up to $n=5$ , we can derive the minimum ESOPs by table look up: it
requires only 6 seconds on the average [12]. For $n=9$ , we could minimize the ESOP with at most
4 products. Table 8.1 shows the cpu time and memory requirement using zero-suppressed BDD. For
large problems, conventional BDDs required more cpu time, and more memory than zero-suppressed
BDDs.

IX

Conclusion

In this paper, we presented a new method to obtain an exact minimum ESOP for an variable
function by using modified reduced covering function. We also presented various techniques to reducethe computation time and memory requirements. By using this approach, we minimized many ESOPs
with $n=5$ and some ESOPs with up to $n=9$ variables. Because minimum ESOPs for up to $n=5$ canbe obtained very quickly by a table look-up method, the proposed method is suitable for the functions
with $n=6$ or more. It is possible to extend RCF to treat multiple-output functions. We successfuly
minimized adr2 (two bit adder) and mlp2 (two bit multiplier) within 18 minutes. Although we havemade a drastic improvement over the previous approach [19], it is till memory and time consumingwhen the functions require many products.
$n$$\cdot$$s$

58

Acknowledgments
This work was supported in part by a Grant in Aid for Scientific Research of the Ministry of Education,
Science and Culture of Japan. Mr. M. Matsuura developed the software and did experiments. Prof. N.
Koda provided the program for lower bounds on the number of ESOPs. Prof. Jon T.’Butler carefully
Zero-suppressed BDD is also acknowledged.
read the manuscript. Mr. S. Minato’s comment on$tl\iota e$

References[1] K. S. Brace, R. L. Rudell and R. E. Bryant,“ Efficient implementation of a BDD package,” Proc.
27th Design Automation Conference, June 1990, pp. 40-45.
[2] D. Brand and T. Sasao, “Minimization of AND-EXOR expressions using rewriting rules, IEEE
Transactions on Comp uters, (to be published).
[3] R. E. Bryant, “Graph-based algorithms for Boolean function manipulation,” IEEE Trans. Comput. Vol. C-35, No.8, Aug. 1986, pp.677-691.
[4] C. Damm, “How much EXOR improve on OR,” IFIP WG 10.5 Workshop on Applications on the
Reed-Muller Expansion in Circuit Design, Sept. 1993.
[5] M. Davio, J-P Deschamps, and A. Thayse, Discrete and $s_{uJ}itching$ Functions, McGraw-Hill International, 1978.
[6] S. Even, I. Kohavi and A. Paz, “On minimal modulo-2 sum of products for switching functions,”
IEEE Tmns. on Electron Computers, Vol. EC-16, pp.671-674, Oct. 1967.
[7] H. Fleisher, M. Tarvel, and J. Yeager, “A computer algorithm for minimizing Reed-Muller canonical forms,” IEEE Trans. on Computers, Vol.C-36, No.2, Feb. 1987.
[8] D. H. Green and I. S. Taylor: “Multiple-valued switching circuit design by mean s of generalized
Reed-Muller expansions,“ Digital Processes, vol.2, pp.63-81, 1976.
[9] M. Helliwell and M. Perkowski, “A fast algorithm to minimize multi-output mixed-polarity generalized Reed-Muller forms,” Proc. of the 25th Design Automation Conference, pp.427-432, June

1988.

[10] N. Koda and T. Sasao, “An upper bound on the number of product terms in AND-EXOR
minimum expressions,” (in Japanese), Trans. IEICE, Vol. J75-D-I, No.3, pp. 135-142, March

1992.
[11] N. Koda and T. Sasao, “A minimization method for AND-EXOR expressions using lower boundtheorem,” (in Japanese), Tmns. IEICE, Vol.J76-D-I, No.1, pp. 1-10, Jan. 1993.

59[12] N. Koda and T. Sasao, “LP equivalence class of logic functions,” IFIP10.5 Workshop on Application of the Reed-Muller expansion in Circuit Design, Sept. 1993.
[13] B. Lin and F. Somenzi, “Minimization of symbolic relations,” Proc. of the IEEE International.
Conference on Computer Aided Design, pp.88-91, Nov.
[14] S. Minato, N. Ishiura, and S. Yajima, “Shared binary decision diagram with attributed edges for
efficient Boolean function manipulation,”Proc. 27th ACM/IEEE Design Automation Conf., June
1990, pp. 52-57.
[15] S. Minato, “Zero-suppressed BDDs for set manipulation in combinatorial problems,” Proc. 30th
Design Automation Conference, June 1993, pp. 272-277.
[16] A. Mukhopadhyay and G. Schmitz, ”Minimization of Exclusive OR and logical Equivalence ofswitching circuits,” IEEE
. Comput., C-19, pp. 132-140, 1970.
[17] S. Muroga, Logic Design and Suttching Theory, John Wiley&Sons, 1979.
[18] G. Papakonstantinou, “Minimization of modulo-2 sum of products,”IEEE Trans. Comput., C-28,
pp. 163-167, 1979.
[19] M. Perkowski and M. Chrzanowska-Jeske, “An exact algorithm to minimize mixed-radix exclusive
sums of products for incompletely specified Boolean functions,” Proc. ISCAS, pp. 1652-1655, June
$19\Re I$$\mathcal{I}\succ ans$

1990.

[20] U. Rollwage, “The complexity of mod-2 sum PLA’s for symmetric functions,” IFIP WG 10.5
Workshop on Applications on the Reed-Muller Expansion in Circuit Design, Sept. 1993.
[21] S. D. Brown, R. J. Francis, J. Rose, and Z. G. Vranesic, Field Programmable Gate Arrays, Kluwer
Academic Publishers, Boston 1992.
[22] K. K. Saluja and E. H. Ong, ”Minimization of Reed-Muller canonic expansion,” IEEE Trans.
Comput., C-28, pp. 535-537, 1979.
[23] T. Sasao and P. Besslich, “On the complexity of MOD-2 Sum PLA’s, IEEE Trans. on Comput.
Vol. 39. No. 2, pp. 262-266, Feb. 1990.
[24] T. Sasao, “Logic synthesis with EXOR gates,” in (Sasao e.d.) Logic Synthesis and optimization,
Kluwer Academic Publishers, 1993, pp.259-285.
[25] T. Sasao, “AND-EXOR expressions and their optimization,” in (Sasao e.d.) Logic Synthesis andoptimization, Kluwer Academic Publishers, 1993, pp.287-312.
[26] T.
EXMIN2:A simplification algorithm for exclusive-OR-Sum-of-products expressions
for multiple-valued input two-valued output functions,” IEEE Tmnsactions on Computer-Aided
Design of Integmted Circuits and Systems (to be published).
$Sasao\backslash ’$