A METHOD TO FIND THE BEST MIXED POLARITY

REED-MULLER EXPANSION

by

DMITRY MASLOV

M.Sc. (Mathematics) Lomonosov’s Moscow State University, 1998

A thesis submitted in partial fulfillment of

the requirements for the degree of

MASTER OF SCIENCE

in

THE FACULTY OF COMPUTER SCIENCE

We accept this thesis as conforming

to the required standard

.....................................

.....................................

.....................................

.....................................

.....................................

THE UNIVERSITY OF NEW BRUNSWICK

June 2001

c Dmitry Maslov, 2001

°
In presenting this thesis in partial fulfillment of the requirements for an advanced degree
at the University of New Brunswick, I agree that the Library shall make it freely available
for reference and study. I further agree that permission for extensive copying of this
thesis for scholarly purposes may be granted by the head of my department or by his
or her representatives. It is understood that copying or publication of this thesis for
financial gain shall not be allowed without my written permission.

(Signature)

Faculty of Computer Science

The University of New Brunswick
Fredericton, Canada

Date
Abstract
In this thesis, we use the transeunt triangle in an efficient algorithm to find the minimum
mixed polarity Reed-Muller expression of a given function. This algorithm runs in
Θ(n2 3n ) time and uses Θ(n3n ) storage space. The algorithm is also designed for multiple
output functions. Efficiency of this algorithm is demonstrated on benchmark functions.

ii
Table of Contents
Abstract ii

Table of Contents iii

Chapter 1. Introduction 1

Chapter 2. Background 3

Chapter 3. Minimization Algorithm 11

3.1 Transeunt Triangle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.2 Getting coefficients from the RTT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Chapter 4. Multiple Output Functions 28

Chapter 5. Experimental Results 30

Chapter 6. Further work 34

Chapter 7. Conclusion 38

Bibliography 39

Appendix A. C code for the program that finds the best mixed polarity
Reed-Muller expansion 41

iii
Chapter 1
Introduction

There are many ways to represent a Boolean function. Much research has been devoted

to sum-of-product expressions in which sum is the Exclusive-OR function and product

is the AND of variables or complements of variables [1]. It is known that such expres-

sions require, on average, fewer product terms than OR sum-of-products [9]. Another

advantage is ease of testability [7].

AND-EXOR circuits have been used in arithmetic, error correcting, and telecommuni-

cations applications [14], [10].

Such expressions can be used to classify a given function into an equivalence class of

functions, where two functions are equivalent if one is transformed into the other by

permuting variables, complementing variables, and/or complementing the function [13],

and is useful for determining library cells in CAD (computer-aided design) tools. This

is called Boolean matching and is important in the determination of library cells for use

by CAD tools.

This thesis focuses on a special class of AND-EXOR circuits, called mixed polar-

ity Reed-Muller (MPRM) expressions. In an MPRM expression of a given function

f (x1 , x2 , ..., xn ), every variable appears either complemented, uncomplemented, or in

1
Chapter 1. Introduction

both forms, in which case all terms contain the variable. If all variables are uncom-

plemented (complemented), the MPRM expression is called the Positive (Negative)

Polarity Reed-Muller or PPRM (NPRM) form. A fixed polarity Reed Muller (FPRM)

expression is one where each variable appears either complemented or uncomplemented,

but never in both forms. FPRM expression are a subset of MPRM expressions. MPRM

expressions are unique [2] for a given polarity. Thus, only one representation exists

for the PPRM or NPRM or indeed any MPRM of f (x1 , x2 , ..., xn ). This leads to the

question of which of the MPRM’s produces the fewest product terms [5], [6], [11].

2
Chapter 2
Background

In this section we give the formal definitions of the terms used in this thesis. One method

to describe a Boolean function f (x1 , x2 , ..., xn ) of n variables is by a truth table. This

construction is nothing, but a table with (n + 1) columns and 2n rows. In the rightmost

column the value of the function for the input that is placed in the first n columns is

given for each row. The number of different inputs for a function of n Boolean variables

is 2n , therefore the height of this construction is 2n . In other words, the truth table

has 2n rows. It can be seen that the truth table requires large amount of storage, so in

order to simplify it, the truth vector method is used. The truth vector for a function of

n variables is the sequence of Boolean numbers of length 2n , where the k-th number of

this sequence is the value of the function on the input that is the binary representation

of number k. In the following example we see the advantage of the truth vector method

of representing a function compared with the truth table method.

Example 1. Consider the following truth table shown in Table 2.1. The truth vector for

the same function is [0, 0, 1, 1, 1, 0, 1, 1], which requires one-fourth of the storage space.

For a function of n variables the truth vector method requires (n + 1) times less storage

than the truth table.

3
Chapter 2. Background

x1 x2 x3 f (x1 , x2 , x3 )

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 1

1 1 1 1

Table 2.1: Truth table method

Now consider Boolean functions f (x1 , x2 , ..., xn ) of n variables and represent them as

polynomials. This means that we consider the operations of conjunction (written as

& or concatenation), negation (¯) and exclusive or (⊕). The popular notation xσi i to

represent xi if σi = 1 and x̄i if σi = 0 will be also used. A proof that the system of

operations {&,¯, ⊕} is a basis can be easily obtained from Shannon’s expansion:

f (x1 , x2 , ..., xn ) = x¯1 f (0, x2 , ..., xn ) ⊕ x1 f (1, x2 , ..., xn ).

Now a polynomial that represents a function of n variables can be built. One of the

simplest ways to do this is:

1. Take the truth vector and for each 1, say, at i-th place, build the product that has

truth vector [0, 0, ..., 0, 1, 0, ..., 0] where 1 is exactly at the i-th place. This product

will look like xσ1 1 , xσ2 2 , ..., xσnn , where i = (σ1 , σ2 , ..., σn ) is the binary decomposition

of the natural number i.

4
Chapter 2. Background

2. The function is the “exclusive or” of all products obtained from the previous step.

By Shannon’s theorem this sum-of-products that is obtained from this algorithm is equal

to the function. For example, the function shown in Table 2.1 (function with truth vector

[0, 0, 1, 1, 1, 0, 1, 1]) can be expressed as: x¯1 x2 x¯3 ⊕ x¯1 x2 x3 ⊕ x1 x¯2 x¯3 ⊕ x1 x2 x¯3 ⊕ x1 x2 x3 .

There are many polynomials which represent the same function. For example,

x1 ⊕ x¯1 x2 ⊕ x1 x¯2 x3 , (2.1)

x2 ⊕ x1 x¯2 x¯3 , (2.2)

and

x1 ⊕ x2 ⊕ x1 x2 ⊕ x1 x3 ⊕ x1 x2 x3 (2.3)

represent the same function shown in Table 2.1. But in this thesis a function will not be

represented as any polynomial, but as a polynomial of some special type (Reed-Muller

canonical form). The first polynomial is not in such a form. This becomes clear from

the following definition.

Definition 1. Mixed polarity Reed-Muller expression is an ESOP that has some

polarity P = (ρ1 , ρ2 , ..., ρn ). Let P = (ρ1 , ρ2 , ..., ρn ) where ρ1 , ρ2 , ..., ρn ∈ {0, 1, 2} be the

polarity of a mixed polarity Reed-Muller expression for the function f (x1 , x2 , ..., xn ),

which means that:

• xi appears complemented if ρi = 0,

5
Chapter 2. Background

• xi appears uncomplemented if ρi = 1 and

• xi appears mixed if ρi = 2.

For example, if ρi = 2, then f can be decomposed as

f (x1 , x2 , ..., xn ) = xi f0 (x1 , ..., xi−1 , xi+1 , ..., xn ) ⊕ x̄i f1 (x1 , ..., xi−1 , xi+1 , ..., xn ),

where f0 (x1 , ..., xi−1 , xi+1 , ..., xn ) and f1 (x1 , ..., xi−1 , xi+1 , ..., xn ) have polarity

(ρ1 , ..., ρi−1 , ρi+1 , ..., ρn ).

According to Sasao’s classification [8] the above is a Kronecker expression. The polarity

P is said to be fixed, iff ρ1 , ρ2 , ..., ρn ∈ {0, 1}. That is each variable appears either

complemented or uncomplemented but never in both forms.

The polynomial x1 ⊕ x¯1 x2 ⊕ x1 x¯2 x3 is not a valid mixed polarity Reed-Muller expression

because x2 is found in all three possible forms: not present, present, and present with

negation. The other two polynomials (2.2) and (2.3) are Reed-Muller expansions. From

the definition, x2 ⊕ x1 x¯2 x¯3 gives us polarity 1 on x1 , 2 on x2 and 0 on x3 , which we

write in short as polarity (1, 2, 0). x1 ⊕ x2 ⊕ x1 x2 ⊕ x1 x3 ⊕ x1 x2 x3 gives us polarity

(1, 1, 1) (so, according to commonly used notations, this is a fixed polarity Reed-Muller

expression, namely positive polarity, which by the definition is the polarity where all

variables appear uncomplemented).

The example below illustrates how a mixed polarity Reed-Muller expression is obtained

given any function.

6
Chapter 2. Background

Example 2. Given the three-variable function with the truth vector [0, 0, 1, 1, 1, 0, 1, 1].

Find the mixed polarity expression with polarity (1, 2, 0). To build it, we construct the

polynomial by the method described above. We have:

x¯1 x2 x¯3 ⊕ x¯1 x2 x3 ⊕ x1 x¯2 x¯3 ⊕ x1 x2 x¯3 ⊕ x1 x2 x3 (2.4)

The polynomial is given with (2, 2, 2)-polarity, since all the variables appear in each

term and can be found complemented as well as not complemented. In general, when

we build this simplest polynomial for a function of n variables (which is also called

Shannon’s complete expansion or perfect exclusive-or normal form) we have a Reed-

Muller expression of polarity (2, 2, ..., 2). Returning to our example we notice that in

order to have a polynomial of polarity (1, 2, 0) we have to change polarity of x1 from 2

to 1 and polarity of x3 from 2 to 0. There’s no need to change polarity of x2 since it is

already correct, so we break the procedure into two parts:

1. Change the polarity of x1 . To do this we use formula x¯1 = x1 ⊕ 1 and apply it to

each x¯1 presented in the expression:

x¯1 x2 x¯3 ⊕ x¯1 x2 x3 ⊕ x1 x¯2 x¯3 ⊕ x1 x2 x¯3 ⊕ x1 x2 x3 =

= (x1 ⊕ 1)x2 x¯3 ⊕ (x1 ⊕ 1)x2 x3 ⊕ x1 x¯2 x¯3 ⊕ x1 x2 x¯3 ⊕ x1 x2 x3 =

= x1 x2 x¯3 ⊕ x2 x¯3 ⊕ x1 x2 x3 ⊕ x2 x3 ⊕ x1 x¯2 x¯3 ⊕ x1 x2 x¯3 ⊕ x1 x2 x3 =

= x2 x¯3 ⊕ x2 x3 ⊕ x1 x¯2 x¯3

7
Chapter 2. Background

2. After simplification the obtained polynomial has polarity (1, 2, 2). Now we come

with the procedure that changes the polarity of x3 . We have to substitute every

x3 with (x¯3 ⊕ 1):

x2 x¯3 ⊕ x2 x3 ⊕ x1 x¯2 x¯3 =

= x2 x¯3 ⊕ x2 (x¯3 ⊕ 1) ⊕ x1 x¯2 x¯3 =

= x2 x¯3 ⊕ x2 x¯3 ⊕ x2 ⊕ x1 x¯2 x¯3 =

= x2 ⊕ x1 x¯2 x¯3 .

The last Reed-Muller expression (x2 ⊕ x1 x¯2 x¯3 ) has polarity (1, 2, 0) .

As we see from the example above, different polarity Reed-Muller expressions have

different number of terms. At this point we are ready to give the definition for the

cost of a representation. In general, there are two common ways to understand the

cost. The first approach is to consider the cost to be the number of literals used

to create the polynomial. This understanding of the cost is widely used when one

considers contact schemes [?]. In this method, every time we use a literal, we add

one contact which adds one to the final cost. The geometry of the net consisting of

these contacts defines the function. The second common understanding of the cost is

a Programmable Logic Array(PLA)-like structure. PLA itself consists of two arrays:

“AND”-array and “EXOR”-array. In the first part of a PLA, “AND”-array, we create

all necessary products that are used in the “EXOR”-array part. Therefore, according to

the theory of PLA design we care more about the number of products, than the number

of literals in each product. In this work we chose the PLA-oriented definition of the

cost, which is formally given below:

8
Chapter 2. Background

Definition 2. The cost of a Reed-Muller expression is the number of all non-zero

coefficients of the corresponding polynomial. I

In case we want to realize the function with some device, two questions are interesting:

is there an efficient algorithm to find the expression with the smallest cost, and what

is the maximum cost for a n-variable function. The main issue of the present thesis

is to find an efficient algorithm to find the best mixed polarity Reed-Muller expansion

and compare its efficiency with the efficiency of previous known algorithms. The second

problem was not forgotten, and one of the hard functions was found. The problem of

finding the hardest functions to represent will be generalized into the case of Cohn’s

inconsistent forms, but this issue refers to future work, which is introduced in Chapter

6.

Several algorithms have been created to solve the problem of finding a minimal mixed

polarity Reed-Muller expression. We comment on the following three.

The first, Green [4]. The method he used is the closest to our approach. Green con-

sidered ternary maps with 3n elements that are interpreted as rectangles. The method

to find the best mixed polarity Reed-Muller expansion is very similar to ours: first, we

fill the map by specially described rules. After filling the map, the author proceeds to

add numbers inside the structure, and then the costs for all 3n polarities are obtained

in all 3n different cells. Finally, Green finds the minimum cost among all 3n costs he

obtained.

The second, Lui and Muzio [5]. The authors used the Kronecker product of elemen-

tary matrices to describe the generalized Boolean matrix transforms for modulo-2 fixed

9
Chapter 2. Background

and mixed polarity Reed-Muller expansions of a Boolean function. A method for fast

Boolean matrix transformations was considered to generate exhaustively all the 2n (3n )

fixed (mixed) polarity Reed-Muller expansions. Then, the expansion with the least

number of terms was selected.

The third, Drechsler, Theobald and Becker’s [3]. The core of the data structure they

consider is the ordered functional decision diagram (OFDD), which is a restricted type of

a decision diagram (decision tree). There exists a one-to-one correspondence between so

called one-paths and terms in fixed polarity Reed-Muller expansions. This allows to say

that a method that minimizes the number of one-ways in OFDD gives the cost for the

shortest fixed polarity Reed-Muller expansion. For the minimization the authors build

an OFDD with only positive Davio-nodes and transform it step by step to an OFDD

with only negative Davio-nodes. Drechsler et al. constructs 2n OFDDs, determining

the number of one-paths and store the best result. To avoid the construction of the

same OFDD twice, they use the Gray code.

10
Chapter 3
Minimization Algorithm

3.1 Transeunt Triangle

Let f (x1 , x2 , ..., xn ) be a switching function of n variables, where xi ∈ {0, 1}. We seek

a mixed polarity Reed-Muller expression for f with minimal cost. A design algorithm

based on the transeunt triangle, previously applied to symmetric functions, [?], [?], [?],

[12], is also useful for arbitrary functions.

Definition 3. The transeunt triangle for f (x1 , x2 , ..., xn ) is a triangle of 0’s and 1’s

where the bottom row is the truth vector of f . The j-th element in the i-th row of

the triangle is denoted by ei,j , where the indices run from top-to-bottom and left-to-

right starting with i = 0 and j = 1, respectively. The truth vector corresponds to

the elements e2n ,0 , e2n ,1 , ..., e2n ,2n −1 . The element e2n ,k corresponds to f (α1 , α2 , ..., αn ),

where k = (α1 , α2 , ..., αn ) is the binary representation of integer k. Other elements are

related by ei,j = ei+1,j ⊕ ei+1,j+1 . I

Example 3. The transeunt triangle for f (x1 , x2 ) = 1 ⊕ x1 ⊕ x2 is shown in Fig. 3.1.

Note that a transeunt triangle for an n-variable function has a width of 2n and a height

of 2n . There are (4n + 2n )/2 elements in total. Besides the defining relation, there are

11
Chapter 3. Minimization Algorithm

1 1

1 0 1

1 0 0 1

Figure 3.1: Transeunt triangle for f (x1 , x2 ) = 1 ⊕ x1 ⊕ x2 .

other relations among elements in the transeunt triangle, as shown below.

Lemma 1. For the transeunt triangle of any function f (x1 , x2 , ..., xn ), ei,j = ei+2k ,j ⊕

ei+2k ,j+2k where k ≥ 0.

Proof. By induction: If k = 0, then ei,j = ei+1,j ⊕ ei+1,j+1 is true by the definition of

transeunt triangle. Assume the hypothesis is true for k = m − 1. Therefore,

ei,j = ei+2m−1 ,j ⊕ ei+2m−1 ,j+2m−1 (3.1)

Similarly,

ei,j+2m−1 = ei+2m−1 ,j+2m−1 ⊕ ei+2m−1 ,j+2m−1 +2m−1 (3.2)

and

ei+2m−1 ,j+2m−1 = ei+2m−1 +2m−1 ,j+2m−1 ⊕ ei+2m−1 +2m−1 ,j+2m−1 +2m−1 (3.3)

Substituting (3.2) and (3.3) into (3.1) yields the hypothesis. ¥

Since the truth vector for functions with one or more variables has an even number of

entries, it can be divided evenly into two equal parts. Each part produces, on its own,

12
Chapter 3. Minimization Algorithm

two subtriangles. Indeed, we can identify three subtriangles, as shown in Fig. 3.2.

 




 

 

Figure 3.2: Decomposition of the transeunt triangle T .

Lemma 2. Let T be transeunt triangle for a switching function f (x1 , x2 , ..., xn ). If we

divide T into 3 triangles T0 , T1 and T2 as shown in Fig. 3.2, then

• T0 is the transeunt triangle for the function f (0, x2 , ..., xn ),

• T1 is the transeunt triangle for the function f (1, x2 , ..., xn ) and

• T2 is the transeunt triangle for the function f (0, x2 , ..., xn ) ⊕ f (1, x2 , ..., xn ).

Proof. First, denote e0i,j to be the (i, j)-th element from T0 , e1i,j to be the (i, j)-th

element from T1 and e2i,j to be the (i, j)-th element from T2 . T0 can be considered as

the transeunt triangle for f (0, x2 , ..., xn ) because it’s bottom row is the truth vector

of f (0, x2 , ..., xn ) and every element e0i,j = e0i+1,j ⊕ e0i+1,j+1 by the construction of T .

Similarly, T1 is the transeunt triangle for f (1, x2 , ..., xn ).

Note, that by Lemma 1 and the statement that the height of transeunt triangle is a

power of two e2i,j = e0i,j ⊕ e1i,j . Therefore, the bottom of T2 will be “exclusive or” of the

elements of the bottom row of transeunt triangles for f (0, x2 , ..., xn ) and f (1, x2 , ..., xn ),

13
Chapter 3. Minimization Algorithm

which is the “exclusive or” of truth vectors of f (0, x2 , ..., xn ) and f (1, x2 , ..., xn ), which

is the truth vector for f (0, x2 , ..., xn ) ⊕ f (1, x2 , ..., xn ). Other (non-bottom) elements of

T2 , by the construction of T , are corresponding sums. So, T2 is the transeunt triangle

for the function f (0, x2 , ..., xn ) ⊕ f (1, x2 , ..., xn ). ¥

The algorithm to find the best, from the point of view of number of terms, mixed

polarity Reed-Muller expansion can be described intuitively, as follows. First, given a

function f (x1 , x2 , ..., xn ) as a truth vector and a polarity P = (ρ1 , ρ2 , ..., ρn ), construct

the corresponding transeunt triangle. To obtain the cost, divide the triangle into parts,

extracting elements. First, divide the transeunt triangle T into the three triangles T0 , T1

and T2 . Consider the variable x1 and the corresponding ρ1 in the polarity P . If ρ1 = 0

retain T1 and T2 . If ρ1 = 1 retain T0 and T2 . And, if ρ1 = 2 retain T0 and T1 . In

other words, if ρ1 = i where i ∈ {0, 1, 2}, then delete Ti . Next, repeat this process

with x2 (and ρ2 ). As a result we have four triangles. Continue this operation for all

variables until each triangle is a single element. Such a one-element triangle is called

an elementary triangle. There will be 2n of them. The sum of all these 2n values is the

cost for the given polarity (view logic values as integers and sum as integer sum).

A formal version of the algorithm is shown in Fig.3.3.

Theorem 1. Given function f (x1 , x2 , ..., xn ), Algorithm 1 finds the cost for a given

polarity P .

Proof. The proof is by induction.

1. If n = 1 write f (x1 ) = x¯1 f (0) ⊕ x1 f (1) which gives us polarity P = (2), or f (x1 ) =

14
Chapter 3. Minimization Algorithm

Algorithm 1

GetCost(T , P )

/* Calculate the cost for polarity P */

/* for a function f given as transeunt triangle T*/

if ( |P | = 0 ) then

return e0,0 /* T is a triangle consisting of one element */

if ( ρ1 = 0) then

return GetCost(T1 , P 0 ) + GetCost(T2 , P 0 )

/* where P 0 is P with ρ1 deleted */

if ( ρ1 = 1) then

return GetCost(T0 , P 0 ) + GetCost(T2 , P 0 )

if ( ρ1 = 2) then

return GetCost(T0 , P 0 ) + GetCost(T1 , P 0 )

Figure 3.3: Recursive algorithm to find the cost for a given polarity.

f (0) ⊕ x1 (f (0) ⊕ f (1)) which gives us polarity P = (1), or f (x1 ) = f (1) ⊕ x¯1 (f (0) ⊕ f (1))

which gives us polarity P = (0). In this simple case the cost of the polarity P = (2) is

f (0) + f (1), the cost of the polarity P = (1) is f (0) + (f (0) ⊕ f (1))and the cost of the

polarity P = (0) is f (1) + (f (0) ⊕ f (1)). The transeunt triangle for the given function

will look like:

f (0) ⊕ f (1)

f (0) f (1)

15
Chapter 3. Minimization Algorithm

Note, that T0 = f (0) is the transeunt triangle for f (0), T1 = f (1) is the transeunt

triangle for f (1) and T2 = f (0) ⊕ f (1) is the transeunt triangle for f (0) ⊕ f (1). By

the algorithm, if ρ1 = 0 we should consider T1 and T2 . These triangles are elementary,

so the sum of their elements is taken. It is equal to the f (1) + (f (0) ⊕ f (1)) which is

actually the cost for the given polarity as it was shown before. If ρ1 = 1 consider T0 and

T2 and conclude that the sum of their elements is equal to the cost of polarity P = (1)

as it was shown. And the same goes for P = (2).

2. Assume the theorem holds for n = k − 1. We can decompose f (x1 , x2 , ..., xk ) as

follows:

f (x1 , x2 , ..., xk ) = x¯1 f (0, x2 , ..., xk ) ⊕ x1 f (1, x2 , ..., xk ) (3.4)

= f (0, x2 , ..., xk ) ⊕ x1 (f (0, x2 , ..., xk ) ⊕ f (1, x2 , ..., xk )) (3.5)

= f (1, x2 , ..., xk ) ⊕ x¯1 (f (0, x2 , ..., xk ) ⊕ f (1, x2 , ..., xk )) (3.6)

From this formula it can be concluded that the final cost for every polarity P =

(2, ρ2 , ..., ρk ) will be the sum of the costs of polarity P 0 = (ρ2 , ρ3 ..., ρk ) for functions

f (0, x2 , ..., xk ) and f (1, x2 , ..., xk ). The algorithm leads one to consider triangles T0 and

T1 , which are transeunt triangles for f (0, x2 , ..., xk ) and f (1, x2 , ..., xk ) correspondingly.

By induction, the algorithm works for functions f (0, x2 , ..., xk ) and f (1, x2 , ..., xk ) as

functions from (k − 1) variables, and the cost for the given polarity P 0 will be the sum

of given by the algorithm elementary triangles inside T0 and T1 . But this sum is equal

to the sum of all given by the algorithm elementary triangles of transeunt triangle for

16
Chapter 3. Minimization Algorithm

f (x1 , x2 , ..., xk ) because the first step takes T0 and T1 due to the algorithm. And, finally,

the number which was obtained can be considered as the sum of costs of polarity P 0

for f (0, x2 , ..., xk ) and f (1, x2 , ..., xk ) which is the cost of polarity P = (2, ρ2 , ..., ρk ) for

f (x1 , x2 , ..., xk ) as it was shown before.

For cases P = (1, ρ2 , ..., ρk ) and P = (0, ρ2 , ..., ρk ) the induction step is similar to the

previous proof. ¥

Example 4. Given the function f (x1 , x2 , x3 ) whose truth vector is (0, 0, 1, 0, 1, 0, 1, 1)

find the cost of polarity P = (1, 2, 0).

Figure 3.4: transeunt triangle for the example

First, build the transeunt triangle, then identify the MPRM coefficients associated with

the given polarity according to Algorithm 1. The coefficients are shown in Fig.3.4 in

black. Finally, the coefficients are summed to obtain the cost 4.

A computer program can be built to find the best mixed polarity Reed-Muller expansion

which runs with the complexity of k ∗n3n , k ≤ 4 and requires 3n memory places for n-bit

naturals (n ∗ 3n bits) of memory. Notice that every time the given algorithm is applied,

17
Chapter 3. Minimization Algorithm

some triangles are divided into the 4 parts and only 3 of them are considered: all,

except the central one which is never used. Therefore, at each step of the algorithm the

number of elements, equal to the number of the elements inside all the central triangles

considered are not used. This number of elements for the first step is 22n−3 − 2n−2 , for

the second - 3 ∗ (22n−5 − 2n−3 ), and so on up to the (n − 1)-th step, where we are not

interested in 3n−2 elementary triangles. In sum it gives us:

(22n−3 − 2n−2 ) + 3 ∗ (22n−5 − 2n−3 ) + ... + 3n−2 =

= (22n−3 + 3 ∗ 22n−5 + ... + 3n−2 ∗ 2) − (2n−2 + 3 ∗ 2n−3 + ... + 3n−2 ) =

= 2 ∗ (22n−4 + 3 ∗ 22n−6 + ... + 3n−2 ) − (2n−2 + 3 ∗ 2n−3 + ... + 3n−2 )

Denote m = n − 2 and continue:

2 ∗ (22n−4 + 3 ∗ 22n−6 + ... + 3n−2 ) − (2n−2 + 3 ∗ 2n−3 + ... + 3n−2 ) =

= 2 ∗ (4m + 3 ∗ 4m−1 + ... + 3m ) − (2m + 3 ∗ 2m−1 + ... + 3m ) =

õ ¶ µ ¶m−1 µ ¶0 ! õ ¶ µ ¶m !
m 4 m 4 4 m 3 0 3 3
=2∗3 + + ... + −2 + + ... + =
3 3 3 2 2 2
¡ 4 ¢m+1 ¡ 3 ¢m+1
m 3 −1 m −1
=2∗3 ∗ 4 +2 ∗ 2 3 =
3 −1 2 −1
õ ¶ ! õ ¶ !
m+1 m+1
4 3
= 2∗3∗3m − 1 +2∗2m − 1 = 2∗4m+1 −2∗3m+1 −3m+1 +2m+1 =
3 2

= 2 ∗ 4n−1 − 3n + 2n−1

Now, the number of useful elements is equal to the number of all elements minus the

number of non-useful elements, that gives us 2∗4n−1 +2n−1 −(2∗4n−1 −3n +2n−1 ) = 3n .

In the computer program implementation of the algorithm, only a transeunt triangle

that has these 3n elements is considered. We call this a restricted transeunt triangle

18
Chapter 3. Minimization Algorithm

(RTT). The construction of a RTT proceeds as follows: enumerate elements ei,j of

transeunt triangle. The ternary number (γ1 , γ2 , ..., γn ) which corresponds to the element

ei,j of the RTT for the function f (x1 , x2 , ..., xn ) is built as follows: first, γ1 is k, if

ei,j ∈ Tk , where k ∈ {0, 1, 2}. Second, γ2 , is zero if ei,j lies in the bottom-left triangle,

one if ei,j lies in the bottom-right triangle and two if ei,j lies in the top triangle inside

the chosen Tk . Continue this operation until all values are obtained. For example,

   




Figure 3.5: The example of building the ternary number

e7,3 in (Fig. 3.5) has the ternary number (0, 1, 2), because it is in the second smallest

triangle, which is inside a bigger triangle with number 1, which in its turn, lies in the

bigger triangle number 0.

Lemma 3. If the element ei,j with the ternary number (γ1 , γ2 , ..., γn ) has γk = 2 for

k ∈ {1, 2, ..., n}, then it is equal to the exclusive or of two elements es,t and eu,v of the

RTT with ternary numbers (γ1 , ..., γk−1 , 0, γk+1 , ..., γn ) and (γ1 , ..., γk−1 , 1, γk+1 , ..., γn )

respectively.

Proof. Notice, that by the construction of a ternary number for ei,j the change of k-th

19
Chapter 3. Minimization Algorithm

position from 2 to 0 gives us element es,t , where s = i + 2n−k and t = j. For the

same reason the change of k-th position of ei,j from 2 to 1 gives us element eu,v , where

u = i + 2n−k and v = j + 2n−k . Now we can apply Lemma 1 to prove the statement. ¥

The fact that all elements with ternary numbers (γ1 , γ2 , ..., γn ) where γi ∈ {0, 1} lie in

lexicographic order in the bottom of the RTT together with the definition of transeunt

triangle gives us the following lemma.

Lemma 4. All elements with ternary numbers (γ1 , γ2 , ..., γn ) where γi ∈ {0, 1} are equal

to f (γ1 , γ2 , ..., γn ).

Given the truth vector of a function (the bottom row) we need 3n − 2n “exclusive or”

operations to build the remaining elements in the RTT. That is, there are 3n elements in

the RTT, of which 2n are the truth vector. Next, to find the best mixed polarity Reed-

Muller expression in our computer program implementation of the algorithm (Figure

3.6), switching variables are interpreted as 0, 1 integers. The resulting costs can be

calculated within the RTT so that the elements in T will contain the costs. First, take

3n−1 3-element triangles of the RTT. Each of them has elements ei,j , ei+1,j , ei+1,j+1 and

we

1. set ei,j to ei+1,j + ei+1,j+1 ,

2. set ei+1,j to ei,j + ei+1,j+1 ,

3. set ei+1,j+1 to ei,j + ei+1,j .

Note: the operations are performed simultaneously. To do this for the single 3-element

triangle requires 3 addition operations. For the first step 3 ∗ 3n−1 = 3n addition op-

20
Chapter 3. Minimization Algorithm

erations are needed. In general, for the k-th step take 3n−k of 3k -element triangles

(decomposition of T into smaller triangles as shown in the Fig. 3.7) and, within each of

them by the same rules, obtain: element-wise sum of Tβ1 ,β2 ,...,βk−1 ,0 and Tβ1 ,β2 ,...,βk−1 ,1

in Tβ1 ,β2 ,...,βk−1 ,2 , element-wise sum of Tβ1 ,β2 ,...,βk−1 ,1 and Tβ1 ,β2 ,...,βk−1 ,2 in Tβ1 ,β2 ,...,βk−1 ,0

and element-wise sum of Tβ1 ,β2 ,...,βk−1 ,2 and Tβ1 ,β2 ,...,βk−1 ,0 in Tβ1 ,β2 ,...,βk−1 ,1 , where βi ∈

{0, 1, 2} for i ∈ {1, 2, ..., k − 1}. To do this 3k ∗ 3n−k = 3k+n−k = 3n addition opera-

tions are required. After all the steps (there will be (n-1) of them) are done, costs of

all 3n different mixed polarities are represented by the elements in the RTT. It is easy

to see, that for polarity P = (ρ1 , ρ2 , ..., ρn ) its cost is in the cell with ternary number

(γ1 , γ2 , ..., γn ). To find the minimal cost any known method which finds the minimal

element of the array may be applied.

The final complexity is:

• 3n − 2n binary additions to build the RTT,

• (n − 1)3n natural addition operations to find all costs,

• 3n − 1 comparisons to find the minimal cost.

Needed memory is:

• 3n integers plus a few integer variables for intermediate assignments (3 were used).

The algorithm is best illustrated with an example.

Example 5. Consider the same function used in the previous example. Build the RTT

first, which already has been done, therefore just use the result as it is shown in Fig.3.8A.

Note, that those elements that are not used are initially colored gray in Fig.3.8A and

21
Chapter 3. Minimization Algorithm

will be eliminated from the future parts of the figure. Then corresponding sums inside

the small 3-element triangles are found and placed in the triangle as follows:

• the sum of bottom elements is stored in the top of the triangle;

• the sum of leftmost bottom and top element is stored in the rightmost bottom

place;

• the sum of rightmost bottom and top element is stored in the leftmost bottom

place.

Assume that these three steps are done in parallel. The procedure is shown by arrows

on the rightmost bottom triangle in Fig.3.8A. The procedure is repeated for each 3-

element triangle colored black. The result of this step is shown in Fig.3.8B. Then take

the 9-element triangles and proceed with element-wise summation of elements of the

3-element triangles inside each of them. The order of this summation is also shown for

one of the triangles in Fig.3.8B, but is done for all 3 triangles that exist at this step.

Fig.3.8C gives us the result of our operation. Now we take the element-wise sum of

sub-triangles T0 , T1 and T2 of the whole triangle T and obtain the final result as shown

in Fig.3.8D. Each cost of the polarity P = (ρ1 , ρ2 , ρ3 ) is given by the element with the

ternary number (ρ1 , ρ2 , ρ3 ). From the figure we see that the minimum cost is 3. The

polarity of the minimal cost circled in Fig.3.8D corresponds to P = (1, 2, 2), which is

not unique. There are 3 other polarities with corresponding polynomials that have the

same cost.

22
Chapter 3. Minimization Algorithm

3.2 Getting coefficients from the RTT

Given a RTT one can find all the elements inside it which are needed to obtain the

cost of any given polarity as it is shown in the previous chapter. The question that

one may ask is: can the whole expansion be obtained and not only its cost from the

transeunt triangle? The answer is “Yes” and in order to obtain the polynomial we need

to enumerate all the needed elementary triangles. The enumeration is as follows: for

a given polarity P = (ρ1 , ρ2 , ..., ρn ) and triangle Tβ1 ,β2 ,...,βn its binary number as the

needed for the given polarity element is (²1 , ²2 , ..., ²n ) where ²i for i = 1, 2, ..., n can be

obtained from the table:

ρi βi ²i ϕ(ρi , ²i , i)

0 1 0 1

0 2 1 x̄i

1 2 0 xi

1 0 1 1

2 0 0 x̄i

2 1 1 xi

Table 3.1: table of meanings for ρi , βi , ²i and ϕ(ρi , ²i , i)

Denote every coefficient of a term as E(²1 , ²2 , ..., ²n ) due to its binary number (²1 , ²2 , ..., ²n ).

Then, the polynomial for a mixed polarity P = (ρ1 , ρ2 , ..., ρn ) Reed-Muller expansion

will look like

M
E(²1 , ²2 , ..., ²n )&ϕ(ρ1 , ²1 , 1)&ϕ(ρ2 , ²2 , 2)&...&ϕ(ρn , ²n , n),
²1 ,²2 ,...,²n ∈{0,1}

23
Chapter 3. Minimization Algorithm

where the meaning of ϕ(ρi , ²i , i) is taken from the Table 3.2. The proof of correctness of

this formula is similar to the proof of Theorem 1 and can be done easily by induction and

usage of formulas (3.4). The formula will now be illustrated by the following example.

Example 6. Take the function and polarity from the previous example. The transeunt

triangle is already built, so the next step is to get all E(²1 , ²2 , ..., ²n ) with their numbers

as shown in Fig.3.9 (identify numbers ²i shown in the figure by the Table 3.2, interpreting

it as the truth table for the function ²i (ρi , βi )). Finally, using the Reed-Muller expansion

polynomial and Fig.3.9 there will be:

M
E(²1 , ²2 , ²3 )&ϕ(ρ1 , ²1 , 1)&ϕ(ρ2 , ²2 , 2)&ϕ(ρ3 , ²3 , 3) =
²1 ,²2 ,²3 ∈{0,1}

= E0,0,0 &ϕ(1, 0, 1)&ϕ(2, 0, 2)&ϕ(0, 0, 3) ⊕ E0,0,1 &ϕ(1, 0, 1)&ϕ(2, 0, 2)&ϕ(0, 1, 3)⊕

⊕E0,1,0 &ϕ(1, 0, 1)&ϕ(2, 1, 2)&ϕ(0, 0, 3) ⊕ E0,1,1 &ϕ(1, 0, 1)&ϕ(2, 1, 2)&ϕ(0, 1, 3)⊕

⊕E1,0,0 &ϕ(1, 1, 1)&ϕ(2, 0, 2)&ϕ(0, 0, 3) ⊕ E1,0,1 &ϕ(1, 1, 1)&ϕ(2, 0, 2)&ϕ(0, 1, 3)⊕

⊕E1,1,0 &ϕ(1, 1, 1)&ϕ(2, 1, 2)&ϕ(0, 0, 3) ⊕ E1,1,1 &ϕ(1, 1, 1)&ϕ(2, 1, 2)&ϕ(0, 1, 3) =

= 0&x1 &x¯2 &1 ⊕ 1&x1 &x¯2 &x¯3 ⊕ 1&x1 &x2 &1 ⊕ 1&x1 &x2 &x¯3 ⊕

⊕0&1&x¯2 &1 ⊕ 0&1&x¯2 &x¯3 ⊕ 0&1&x2 &1 ⊕ 1&1&x2 &x¯3 =

= x1 x¯2 x¯3 ⊕ x1 x2 ⊕ x1 x2 x¯3 ⊕ x2 x¯3 .

24
Chapter 3. Minimization Algorithm

Algorithm 2

CalcCostTriangle(Tcost (f ), f )

/* Returns the cost triangle Tcost (f ) of function f . */

if ( n > 1 ) then

Tcost (f ) = Tcost (f1 ) + Tcost (f0 ⊕ f1 ),

Tcost (f0 ) + Tcost (f0 ⊕ f1 ),

Tcost (f0 ) + Tcost (f1 )

else if ( n = 1 ) then

if f = 0 then Tcost (f ) = 0, 0, 0

if f = x then Tcost (f ) = 2, 1, 1

if f = x̄ then Tcost (f ) = 1, 2, 1

if f = 1 then Tcost (f ) = 1, 1, 2

else Tcost (f ) is undefined.

end CalcCostTriangle

/* Note: Composition of triangles, as in

Tcost = Tcost0 , Tcost1 , Tcost2 , places Tcost0 in the lower

left corner, Tcost1 in the lower right corner, and

Tcost2 in the apex. */

Figure 3.6: Recursive algorithm to find costs for all mixed polarities for a given function.

25
Chapter 3. Minimization Algorithm

   



     


      




 
   
     
  

Figure 3.7: Decomposition of T into smaller triangles

 
 







 
 
 



   


 
   
 


 
   
 



  
    
    

   

 
 

   


   

    

 


 

  
   

 
 

Figure 3.8: Building all polarities

26
Chapter 3. Minimization Algorithm

Figure 3.9: Binary numbers for needed elements

27
Chapter 4
Multiple Output Functions

The method developed in the previous section also works for multiple output functions.

Recall that a multiple output function is nothing more, but a Boolean vector-function

(f1 (x1 , x2 , ..., xn ), f2 (x1 , x2 , ..., xn ), ..., fk (x1 , x2 , ..., xn )) of some dimensionality k. To

build Reed-Muller expansion for this multiple output function we need to build expan-

sions for all functions f1 (x1 , x2 , ..., xn ), f2 (x1 , x2 , ..., xn ), ..., fk (x1 , x2 , ..., xn ). There are

two different approaches to define the cost of this expansion. One is to realize each func-

tion separately as polynomials and add all costs. From the point of view of present work

the cost defined by this rule is easy to find, and the method to find the best mixed polar-

ity Reed-Muller expansion has minimal adaptations, namely, create k transeunt triangles

and, after obtaining all the costs for all functions f1 (x1 , x2 , ..., xn ), f2 (x1 , x2 , ..., xn ), ...,

fk (x1 , x2 , ..., xn ) take element-wise sum of all k triangles.

The more interesting case is if a term that has been used once, can be used again without

increasing the final cost. In this case one needs to minimize the number of distinct terms

used to realize the set of functions f1 (x1 , x2 , ..., xn ), f2 (x1 , x2 , ..., xn ), ..., fk (x1 , x2 , ..., xn ).

This understanding of cost is supported by existence of PLAs, that, in fact, consist of

two arrays: “AND”-array and “EXOR”-array. In the first part of a PLA, “AND”-array,

28
Chapter 4. Multiple Output Functions

we create all necessary terms that are used in the “EXOR”-array part as many times

as it is needed. Therefore, in the theory of PLA design we care about the number of

terms, not the number of times the term is used.

For our algorithm, this means that the multiple output function

F (x1 , x2 , ..., xn ) = (f1 (x1 , x2 , ..., xn ), f2 (x1 , x2 , ..., xn ), ..., fk (x1 , x2 , ..., xn )) the truth vec-

tor is given as a list of words (i.e. is vectors made of ones and zeros of length k) rather

than simple bits. To build the transeunt triangle the words inside the triangle are

element-wise “exclusive or”-ed. Before the cost is calculated, all entries in the transe-

unt triangle are set to 1 if the word contains at least one nonzero bit and are set to 0

otherwise. The cost of the best polarity is calculated as before.

The correctness of the algorithm for the multiple output functions can be explained as

follows. First proceed by setting the numbers inside the triangle structure for the whole

multiple output function, a 1 identifies that the word contains at least one 1. Note that

it doesn’t matter how many ones were in the word. If there is at least one 1 in the word

and the cell was chosen, then the product term must be created. It doesn’t matter how

many times it will be used, since we are interested not in the number of times it is used,

but in the number of terms needed. 0 represents the case when the word consists of

zero’s and if the cell is chosen, then no term should be constructed.

29
Chapter 5
Experimental Results

The C programming language was used to implement the algorithm. The complete

program listing is in the Appendix. The RTT is represented as a flat array of the length

3n (variable int* vec;). This structure helps to work with small triangles inside the

initial big one and simplifies the work with recursive functions. Logically, the algorithm

consists of three parts. In the first, “fill” part, we

• allocate memory for our transeunt triangle,

• set values in the truth vector and

• the recursive function void fill() will set the meanings of the transeunt triangle.

The second part, “normalize”, is needed only for multiple output functions. Here all

non-zero elements are changed to 1 since each term that is used more than once adds only

1 to the overall cost (a term can be reused). The last part, “cost”, takes the transeunt

triangle that was built in the previous part of the program, interprets boolean constants

as integers and recursively calculates costs of all polarities. Numbers for the costs of

polarities are put inside the triangle, so that in some sense the algorithm is destructive,

since the costs were found the initial structure of the transeunt triangle is lost. This

third part is performed by the void calcMixedCost, according to algorithm 2. Note

30
Chapter 5. Experimental Results

that this algorithm is destructive in that at the end of it we don’t have RTT unless

a copy of it is made before the third part of the algorithm is activated. Finally, the

minimal cost is achieved by calling minimum(vec, length) that returns the minimal

polarity cost.

The program was applied to several benchmark functions running on a Sun Enterprise

250 with two 400Mhz Ultra Sparc II processors and 1GB of main memory. The results

are summarized in Table 5. In the first column, name, denotes the name of the function

(from MCNC benchmarks). Note: co14 is a symmetric function where the output is

one if exactly 1 input variable is 1. In general con is an n variable symmetric function

whose output is 1 if exactly one input is 1. Function hardn is explained in the following

section. The number of inputs (outputs) are given in in (out). The minimum number

of terms required for a fixed (mixed) polarity Reed Muller expression are shown in

cost fixed (cost mixed). OFDD time denotes the cpu time in seconds for the OFDD

implementation reported in [3] (run on a HP Apollo series 700 workstation). RTT time

gives the cpu time in seconds for our algorithm. Our results compare favorably with

previous implementations. The program is able to minimize any function with up to 18

variables. Memory requirements make it difficult to minimize functions with more than

18 variables.

The Internet was used to obtain the performances of the Sun Enterprise 250 with two

400Mhz Ultra Sparc II processors and the HP Apollo series 700 workstation for com-

parison purposes. From the official Sun web site it was found that the SPECint95 per-

formance of the Sun machine is 19.7 [?] while the performance of the Hewlett Packard

31
Chapter 5. Experimental Results

CPU 744 SPECint95 is 5.90 [?]. As the result of this comparison one may see that to be

fair the results for OFDD should be factored by 4 ≈ 19.7/5.90, but as we see from the

table results for our method is still significantly better. This comparison of computers

is only an approximation, because of a lack of enough information about the computer

used by Drechsler et al.

Green’s [4] algorithm (which is based on Karnaugh-like maps and has the same com-

plexity) has never been implemented. In the paper there’s no algorithm for getting

coefficients of the corresponding Reed-Muller expansion. Partially symmetric functions

were not discussed. The author also claims that the method designed in this thesis is

easier to program.

Drechsler, Theobald and Becker’s [3] implementation is significantly slower than our

program and their algorithm considers only fixed polarity expressions. Drechsler et al.

do not provide a complexity analysis for their algorithm. However, the execution time

depends on the function as well as on the number of variables, whereas our algorithm

depends only on the number of variables.

Lui and Muzio [5] describe an algorithm based on Boolean matrix transforms. It has

space complexity of Θ(2n ) and time complexity of Θ(6n ).

32
Chapter 5. Experimental Results

name in out cost fixed cost mixed OFDD time (secs.) RTT time (secs.)

rd53 5 3 20 20 0.5 < 0.01

rd73 7 3 63 63 2.3 < 0.01
rd84 8 4 107 107 5.5 < 0.01
root 8 5 118 83 8.8 < 0.01
dist 8 5 185 157 12.5 < 0.01
9sym 9 1 173 173 8.1 < 0.01
sao2 10 4 100 76 8.8 0.02
add6 12 7 132 132 295.1 0.17
co14 14 1 14 14 448.4 1.99
tial 14 8 3683 2438 8480.4 2.04
table3 14 14 1845 407 2.01
misex3 14 14 3536 1421 2.02
co15 15 1 15 15 6.68
gary 15 11 349 242 16216.1 6.44
co16 16 1 16 16 20.41
co17 17 1 17 17 64.51
table5 17 15 2458 559 65.88
co18 18 1 18 18 214.11
hard10 10 1 252 252 0.01
hard12 12 1 924 924 0.16
hard14 14 1 3432 3432 1.95
hard16 16 1 12870 12870 20.05
hard18 18 1 48620 48620 211.37

Table 5.1: Experimental results

33
Chapter 6
Further work

The first part of the proposed work will be to reduce the size of RTT for partially sym-

metric functions. Without loss of generality consider the function f (x1 , x2 , ..., xn ), par-

tially symmetric in its first 2 variables. Build its RTT and consider triangles T0,1 and T1,0

shown on the Fig.6.1. It is known that triangle T0,1 is the RTT for the f (0, 1, x3 , ..., xn )

   



     


   
  



  
   
  
     

Figure 6.1: RTT for the function

and T1,0 is the RTT for the f (1, 0, x3 , ..., xn ). Because of the symmetry of the func-

tion in the first 2 arguments these triangles have the same bottom, therefore they are

equivalent. It is also known that T2,0 is element-wise “exclusive or” of triangles T0,0 and

T1,0 and T0,2 is element-wise “exclusive or” of triangles T0,0 and T0,1 , so they are equal

34
Chapter 6. Further work

because of the identity of T0,1 and T1,0 . The same goes for triangles T1,2 and T2,1 that

are equal to “exclusive or” of T1,0 , T1,1 and T0,1 , T1,1 correspondingly. It can be seen

that there’s no need to hold both T0,1 and T1,0 , T0,2 and T2,0 , T1,2 and T2,1 in memory.

Therefore, only one from each pair can be held, and the storage space for function par-

tially symmetric in two variables is reduced by 6/9 (keep 6 out of 9 triangles). The new

storage space is 6 ∗ 3n−2 .

It should not be too difficult to prove that for partially symmetric functions in k vari-
(k+1)(k+2)
ables one can use a storage space of 2 ∗ 3n−k . The proof of this conjecture is

under investigation right now. The proof can be obtained by combining of the method

suggested by Butler et al. for the symmetric functions and the method for general func-

tions, which is discussed in the given work. The implementation of such an algorithm

must be more difficult.

The symmetry is exploited by Drechsler’s algorithm [3] in terms of storage. This is due

to the fact that OBDDs take advantage of symmetry naturally. However the symmetry

is not exploited during the path enumeration.

Cohn conjectured that any boolean function f (x1 , x2 , ..., xn ) can be realized by a poly-
[n/2]
nomial with not more than Cn terms [1]. Consider a polynomial in the basis of

conjunction, negation and exclusive or which represents Cohn’s inconsistent form. In

other words, one can consider polynomials such that for any set of indices {i1 , i2 , ..., ik },

where i1 , i2 , ..., ik ∈ {1, 2, ..., n} there is at most one term which contains exactly the

variables xi1 , xi2 , ..., xik , each variable appearing either complemented or not. There’s

still no proof or counterexample for this conjecture, although the problem is easy to

35
Chapter 6. Further work

[n/2]
understand. The boundary Cn is achievable for the function hardn of even number

of variables n = 2k that is equal to one iff equally half of its’ inputs are one’s. In other
L
words, hardn = 1≤s1 <s2 <...<sk ≤n xs1 xs2 ...xsk which is a shortest form of polynomial

for our function (from the point of view that no better can be obtained).

To prove this statement one needs the following definitions and lemma.

Definition 4. The degree of the polynomial, deg(p(x1 , x2 , ..., xn )), is the number of

variables in the longest term xσi11 xσi22 ...xσikk ∈ p(x1 , x2 , ..., xn ). I

Definition 5. Two functions (polynomials) are called equal if they have equivalent

truth vectors. I

Lemma 5. Given two equal polynomials p1 (x1 , x2 , ..., xn ) and p2 (x1 , x2 , ..., xn ) which are

both in Cohn’s inconsistent form. One can transform one into the other by applying

the following operations:

1. xi −→ x̄i ⊕ 1;

2. x̄i −→ xi ⊕ 1;

3. xσi11 xσi22 ...xσitt ⊕ xσi11 xσi22 ...xσitt −→ 0;

Proof. First, take all the terms of p1 (x1 , x2 , ..., xn ) that have degree deg(p1 (x1 , x2 , ..., xn )).

Notice that for any xσi11 xσi22 ...xσikk from p1 (x1 , x2 , ..., xn ) xδi11 xδi22 ...xδikk from p2 (x1 , x2 , ..., xn )

- a term of the same degree with the same set of variables in it can be found. Prove this

statement by contradiction. Suppose that it is not so. Then there exist xσi11 xσi22 ...xσikk

36
Chapter 6. Further work

from p1 (x1 , x2 , ..., xn ) such that there’s no pair (in the sense described above) for it.

Create the sum p1 ⊕ p2 , which must be equal zero as the exclusive or of equal things.

Apply operation 2 wherever possible and open all the brackets. After doing this we have

the sum of xi1 xi2 ...xik and other terms of smaller degree and equal degree, but having

other sets of indices. Therefore, after applying operation 3, we find that xi1 xi2 ...xik

remains. This mean that p1 ⊕ p2 6= 0, which is a contradiction. Therefore, knowing

that for each term of highest degree a pair exists (another term with the same set of

variables), apply operations 1 and 2 to change xσi11 xσi22 ...xσikk to xδi11 xδi22 ...xδikk . Some new

terms may appear during this procedure, but they all will be of the smaller degree.

Now, the parts of degree k of two polynomials are equal. After this is done, proceed

with the same operation on all the terms of degree (k − 1), and so on. Finally, transform

p1 (x1 , x2 , ..., xn ) into p2 (x1 , x2 , ..., xn ). ¥

Now, from the proof of previous Lemma we see that if we take hardn as the positive

polarity Reed-Muller expression and that any other Cohn’s inconsistent form polynomial

which represents the same function, the second will be of the same degree and will

contain all the terms of degree k that have the same set of variables as a term from the

first polynomial. Therefore, the number of terms in the second polynomial can not be

smaller than those for the first one. This function is used in our computer program.

This is a good test function, since it is complex, yet the minimal result is known. The

last result can be formulated as the following theorem:

n/2
Theorem 2. The presented function hardn proves that Cn gives the lower boundary

for the number of terms needed to realize a Boolean function of n variables as a Cohn’s

inconsistent form.

37
Chapter 7
Conclusion

A new algorithm to minimize fixed and mixed polarity Reed Muller expressions is pre-

sented in this thesis. The algorithm is easy to understand and to program. One can

apply geometric intuition dealing with RTT. The results compare favorably to previous

algorithms, although the complexity of Θ(3n ) in either storage and execution time have

not been reduced.

Initially, an algorithm involving transeunt triangles has been devised to find the best

polarity for totally symmetric functions in Θ(n3 ) operations and Θ(n2 ) storage space [?].

A dramatic reduction in complexity can be achieved for partially symmetric functions.

This area is currently under investigation.

38
Bibliography
[1] M. Cohn. Inconsistent canonical forms of switching functions. IRE Transactions
of Electronic Computers, EC-11:284–285, 1962.

[2] M. J. Davio, P. Deschamps, and A. Thayse. Discrete and switching functions.

McGraw-Hill Int. Book Co., 1978.

[3] R. Drechsler, M. Theobald, and B. Becker. Fast OFDD-based minimization of fixed

polarity Reed-Muller expressions. IEEE Transactions on Computers, 45:1294–1299,
Nov. 1996.

[4] D. H. Green. Reed-Muller canonical forms with mixed polarity and their manipu-
lations. IEE Proceedings, Part E., 137:103–113, Jan. 1990.

[5] P. K. Lui and J. C. Muzio. Boolean matrix transforms for the minimization of
modulo-2 canonical expressions. IEEE Transactions on Computers, 41:342–347,
Mar. 1992.

[6] A. Mukhopadhyay and G. Schmitz. Minimization of exclusive-or and logical-

equivalence switching circuits. IEEE Trans. on Computers, pages 132–140, 1970.

[7] S. M. Reddy. Easily testable realisations for logic functions. IEEE Trans. on
Computers, pages 1183–1188, 1972.

[8] T. Sasao. Logic Synthesis and Optimization. Kluwer Academic Publisher, 1993.

[9] T. Sasao and Ph. W. Besslich. On the complexity of mod-2 sum pla’s. IEEE Trans.
on Computers, C-29:262–266, Feb. 1990.

[10] J. Saul. Logic synthesis for arithmetic circuits using the Reed-Muller representation.
Proc. Euro. Conf. Design Automation, pages 109–113, 1992.

[11] I. Schafer and M. A. Perkowski. Multiple-valued input generalized Reed-Muller

forms. Proc. of the Inter. Symp. on Multiple-Valued Logic, pages 40–48, 1991.

39
Bibliography

[12] V. P. Suprun. Fixed polarity Reed-Muller expressions of symmetric Boolean func-

tions. Proc. IFIP WG 10.5 Workshop on Application of the Reed-Muller Expansions
in Circuit Design, pages 246–249, 1995.

[13] Chien-Chang Tsai and M. Marek-Sadowska. Boolean Functions Classification via

Fixed Polarity Reed-Muller Forms. IEEE Trans. on Computers, C-46(2):173–186,
Feb. 1997.

[14] T.Sasao. Switching theory for logic synthesis. Kluwer Academic Publishers, Nor-
well, MA, 1999.

40
Appendix A
C code for the program that finds the
best mixed polarity Reed-Muller
expansion

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <sys/time.h>
#include <sys/resource.h>

/**************/
/* prototypes */
/**************/
int minimum(int *arr, int sz);
int index(int *vars);
void setTerm(char *term, int ovalue);
void fill(int *v, int size);
void normalize(int *v, int size);
void calcMixedCost(int *func, int tn);

/********************/
/* global variables */
/********************/
int* vec; /* all values in the triangle */

41
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

int n; /* number of variables */

/* returns elapsed user CPU time in usec. */

long usertime()
{
struct rusage *usage;

usage=malloc(sizeof(struct rusage));
getrusage(RUSAGE_SELF,usage);
return(usage->ru_utime.tv_sec*1000000+usage->ru_utime.tv_usec);
}

/* Display a time value in msec. */

void printtime(long x)
{
printf("%8.3f msec\n",(float)x/1000.0);
}

/*****************************************************************
find the minimum value in an array
******************************************************************/
int minimum(int *arr, int sz){
int res = arr[0], i;
for(i = 1; i < sz; i++)
if(res > arr[i])
res = arr[i];
return res;
}

42
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

/*****************************************************************
convert the triangle index to a flat one
******************************************************************/
int index(int *vars){
int res = 0, i;
for(i = 0; i < n; i++)
res = (res * 3) + vars[i];
return res;
}

/*****************************************************************
Set the truth values for a single term
******************************************************************/
void setTerm(char *term, int ovalue){
int *vars, *dashes, ndash = 0, i, done;
vars = malloc(n*sizeof(int));
dashes = malloc(n*sizeof(int));

for(i = 0; i < n; i++){

vars[i] = term[i] == ’1’ ? 1 : 0;
if(term[i] == ’-’){
dashes[ndash] = i;
ndash++;
}
}

done = 0;
while(!done){
vec[index(vars)] = vec[index(vars)] | ovalue;
i = 0;

43
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

while(i < ndash && vars[dashes[i]] == 1 ){

vars[dashes[i]] = 0;
i++;
}
if(i == ndash)
done = 1;
else
vars[dashes[i]] = 1;
}
free(vars);
free(dashes);
}

/*****************************************************************
fill all values in vec
must be called after the truth values are set
******************************************************************/
void fill(int *v, int size){
int i, s3 = size/3;
if(size > 3){
fill(v, s3);
fill(v+s3, s3);
}
for(i = 0; i < s3; i++)
v[i+2*s3] = v[i] ^ v[i+s3];
}
/*****************************************************************
change all non-zero elements to 1
used for multiple output functions
******************************************************************/
void normalize(int *v, int size){

44
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

int i;
for(i = 0; i < size; i++)
v[i] = v[i] >= 1;
}

/*****************************************************************
calculate the cost for all mixed polarities

destructive ==> the values in func are overwritten

******************************************************************/

void calcMixedCost(int *func, int tn){

register i, t1, t2, t3;
int sz = pow(3,tn-1);
int sz2 = 2 * sz;

if(tn > 1){

calcMixedCost(func,tn-1);
calcMixedCost(func+sz,tn-1);
calcMixedCost(func+sz2,tn-1);
}

for(i = 0; i < sz; i++){

t1 = func[i] + func[i + sz2];
t2 = func[i + sz] + func[i+ sz2];
t3 = func[i] + func[i + sz];
func[i] = t2;
func[i + sz] = t1;
func[i + sz2] = t3;
}

45
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

int main(int argc, char *argv[])

{
long time1, time2;
int o, pos, ch, ovalue;
char parm[12];
char *finputs, *foutputs;
int length, clength, i;
int *cost, bestCost;
FILE *fin;

if( !(fin = fopen(argv[1], "r"))){

printf("Could not open file \n");
exit(1);

fscanf(fin,"%s %d", &parm, &n);

if(strcmp(".i",parm) != 0){
printf("ERROR expecting .i\n");
exit(1);
}

length = pow(3,n);
vec = malloc(length*sizeof(int));
for( i = 0; i < length; i++)
vec[i] = 0;
fscanf(fin,"%s %d", &parm, &o); /* read number of ouputs */
if(strcmp(".o",parm) != 0){
printf("ERROR expecting .o\n");

46
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

exit(1);
}

finputs = malloc(n*sizeof(char) + 1);

foutputs = malloc(o*sizeof(char) + 1);
finputs[n] = 0;
foutputs[o] = 0;

/* read all the terms */

/* very curde: strict input format */
ch = getc(fin);
while(EOF != (ch = getc(fin))){
for(i = 0; i < n ; i++){
finputs[i] = (char) ch;
ch = getc(fin);
}
ch = getc(fin);
ovalue = 0;
for(i = 0; i < o ; i++){
foutputs[i] = (char) ch;
ovalue = ovalue * 2 + (ch == ’1’);
ch = getc(fin);
}
setTerm(finputs, ovalue);
}

time1 = usertime();
fill(vec, length);
normalize(vec, length);
calcMixedCost(vec,n);
bestCost = minimum(vec, length);

47
Appendix A. C code for the program that finds the best mixed polarity Reed-Muller expansion

printf("%s best mixed polarity cost = %d\n ",argv[1], bestCost);

time2 = usertime();
printf("time elapsed = ");
printtime(time2 - time1);
return 0;
}

48