6 1. INTRODUCTION
e Reed–Muller expansion of a function f of the Boolean numbers A, B, and C looks like
f .A; B; C / D c
000
˚ c
100
A ˚ c
010
B ˚ c
001
C ˚
c
110
AB ˚ c
101
AC ˚ c
011
BC ˚ c
111
ABC :
ere are three main differences.
• e Reed–Muller coefficients c
ijk
can have only two possible values: either 0 or 1.
• e exponents i , j , and k in the monomial (a.k.a. term or piterm) A
i
B
j
C
k
each can have
only two different values: either 0 or 1. As a result:
• ere are only a finite number of Reed–Muller terms.
We denote by R.n/ the maximum number of terms in the Reed–Muller expansion of an arbitrary
Boolean function of n variables:
R.n/ D 2
n
: (1.3)
1.4.3 THE MINIMAL ESOP EXPANSION
In the Reed–Muller expansion, NOT functions are not allowed.
2
If we do allow NOT operations,
the “XOR of ANDs” expansion can be made shorter. e shortest expansion (i.e., the one with the
minimum number of terms) is called the minimal ESOP expansion.
e minimal ESOP expansion is quite different from the two above expansions (i.e., the
minterm expansion and the Reed–Muller expansion) in two respects:
• it is not unique: there may exist two or even more minimal ESOP expansions of a same
Boolean function, and
• there is no straightforward algorithm to find the minimal ESOP expansion(s) (except, of
course, exhaustive search).
e last fact explains why minimal ESOPs are only known for the Boolean functions with n D 6
or less [4, 5].
Our example function (Table 1.4) has two different minimal ESOPs:
f .A; B; C / D A ˚ C ˚ A B
D B ˚ C ˚ A B :
Whereas the Reed–Muller expansion (1.2) needs four terms, these minimal ESOPs contain only
three terms; whereas the Reed–Muller expansion (1.2) needs five literals, these minimal ESOPs
contain only four literals.
2
In the present book we limit ourselves to so-called “positive-polarity Reed–Muller expansions.” We thus ignore here
“negative-polarity Reed–Muller expansions” and “mixed-polarity Reed–Muller expansions” [3].
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.