Page 239 - Engineering Digital Design

210 CHAPTER 5 / FUNCTION MINIMIZATION

where, for this example, f 3 = f 4 = f 5 = f 6 = l and /> = f\ = /2 = fi = 0. Therefore,
the gi are found as follows:

go = fo = 0 84 = 0/4(4, 0) = 1
gi - e/id, 0) = o §5 = e/ (5,4, i, o) = o
5
£2 = ®/ 2(2, 0) = 0 g(, = 0/6(6, 4, 2, 0) = 0
83 = 0/3(3, 2, 1, 0) = 1 gl = 0/7(7-0) = 0.

Here, the notation (7-0) means (7, 6, 5, 4, 3, 2, 1, 0). From Eq. (5.17) the result is an exact
minimum given directly as

F 3 = BCg3®Ag 4 = BC® A, (5.23)

which is a much simplified result compared to the original function and has a gate/input
tally of 2/4. This function is said to be a positive polarity R-M expression or PPRME.
The same result is achieved, but with less effort, if the variables of function F 3 are
partitioned into two distinct sets: a disjoint set of bond variables (called the bond set) and
a free set of variables (called the free set), both chosen from the set (A, B, C] and recast
into a contracted (reduced) form for application of Eqs. (5.16) and (5.17). Here, {A, B}
is chosen as the bond set to be coupled with the remaining (orthogonal) free set, {C}. In
this particular case, any combination of bond and free sets would achieve the same desired
result with equal ease. When a function is recast into bond and free sets it is said to be in a
contracted Reed-Muller transformation (CRMT) form. For this example, the CRMT form of
function F^ is

F AB = (AB)C + (AB) + (AB)C = (AB)C © (AB) 0 (AB)C

= (AB)f 0 0 (AB)f { 0 (AB)f 2 0 (AB)/ 3
= go 0 Bgi 0 Ag 2 0 ABg 3, (5.24)

where the subscript in F AB identifies the bond set (A, B}. Notice that use was made of
ABC + ABC = AB and that all terms of the bond set are mutually disjoint. Now, the
/ coefficients are /o = 0, f\ = C, /2 = 1, and f$ = C. Therefore, the resulting CRMT
coefficients become

£0 = /O = 0 g 2 = h 0 /O = 1
g\=fi®fo = C g 3 = h 0 /2 0 / 0 /o = C 0 1 0 C 0 0 = 0.
Introducing these coefficients into the CRMT expression gives the result

F2 = go 0 Bg { 0 Ag 2 0 ABg 3
=00#C0A© 0

= BC 0 A (5.25)

as before.
This simple example has been given to illustrate the application of the CRMT method of
function minimization. The examples that follow are designed to establish the foundation