Page 236 - Engineering Digital Design

5.5 THE SOP-TO-EXSOP REED-MULLER TRANSFORMATION 207

easily obtained from that of Fig. 5.3a by introducing the coordinate values for X and Y into
Fig. 5.3b to obtain the subfunctions in terms of W and Z.
For complex functions involving five or more variables, the process of generating a
gate-minimum result by using XOR EV patterns becomes increasingly more a matter of
trial and error as the number of variables increases. Again, the application of the EV XOR
pattern approach to design is left more to the natural occurrence of such patterns than
it is to the hunt-and-choose method. However, if it is known that XOR patterns occur
naturally in some functions and if one is familiar with conventional (1's and O's) K-map
methods for five or more variables, it is possible to deduce a compressed K-map that will
yield XOR/SOP or EQV/POS forms, but that may not necessarily represent gate-minimum
results.
To overcome the obvious problem of dealing with complex K-map XOR patterns in
functions having more the five variables, an algebraic approach can be used, a subject that
is discussed at length in the remaining sections of this chapter.

5.5 THE SOP-TO-EXSOP REED-MULLER TRANSFORMATION

A generalization of Corollary I (Subsection 3.11.1) can be expressed in canonical form as

(/«/ ' fi)
i=0
= (mofo) © (m,/,) © (m 2/ 2) 0 • • • 0 (m 2 -_i/2«-i), (5.16)

where the 2" m/ represent minterms read in minterm code, and the f t represent their
respective coefficients whose values derive from the binary set {0, 1}. The m, symbols
represent minterms that are, by definition, mutually disjoint, since only one minterm can be
active (logic 1) for the same values of inputs. For this reason, it is permissible to interchange
the OR and XOR operators as in Eq. (5.16). Thus, Eq. (5.16) expresses a transformation of
an SOP expression to an EXSOP (Exclusive OR-sum-of-products) expression. Notice that
if all fj are logic 1 , then F n = 1 .
By setting jc/ = jc,- 0 1, all Jt, are eliminated from the EXSOP form of Eq. (5.16) and a
function of positive polarity results. Then after considerable Boolean manipulation involving
multiple applications of the XOR form of the distributive law given by Eqs. (3.19), the
EXSOP expression of Eq. (5.16) is recast as the Reed-Muller expansion in the EXSOP
form

F n(XQ,X\, . ..,*„_!) = go 0 g\X n-\ © g2*n-2 0 £3*n-2*n-l
0 g4*n-3 ' ' ' © g2"-lX 0Xi • • • X n-], (5.17)

where the g, are called the Reed-Muller (R-M) coefficients for a positive polarity