Page 235 - Engineering Digital Design

206 CHAPTER 5 / FUNCTION MINIMIZATION

( w w © Tl

[ w w) + X

(b)

/• —
]zj© w W +£

w w
v_

(c)
FIGURE 5.3
Compressed K-maps for extraction of gate-minimum XOR forms, (a) Conventional K-map for func-
tion / in Eq. (5.13). Second-order compression K-map deduced from K-map in (a) showing XOR
patterns, (c) Alternative second-order K-map.

and

fxoR/sor = ((Y © W)] 0 (XZ) + WY, (5.15)

which have gate/input tallies of 6/19 and 5/10, respectively. The second-order K-map in
Fig. 5.3b is deduced from the K-map in Fig. 5.3a by observing that W O X exists in the
YZ = 01 column, with W and W located in adjacent YZ columns. Thus, by taking Y and Z
as the axis variables and W and X as the EVs for the compressed K-map, the XOR patterns
appear, allowing one to easily extract gate-minimum results.
Notice that the W in the EV K-map of Fig. 5.3b must be looped out a second time to
give the WY term in Eq. (5.15). This is necessary because cover remains in W + X after
the associative pattern involving W and X in cell 1 has been extracted. That is, only W © X
has been looped out of W + X, making it necessary to cover either W or X a second time.
This is easily verified by introducing the coordinates of the cell 3 (7 = 1, Z = 1) into
Eq. (5.15). Without the term W Y the subfunction W + X cannot be generated. The residual
cover in W + X can also be looped out of cell 3 by extracting XYZ and using it in place
of W Fin Eq. (5.15).
Only in one other compressed K-map are the gate-minimum XOR patterns and Eq. (5.15)
results obvious, and that is shown in Fig. 5.3c. In all four other compressed K-map possibil-
ities, those having axes W/X, X/Z, W/Z, and W/ Y, the XOR patterns shown in Figs. 5.3b
and 5.3c disappear, making a gate-minimum extraction without extensive Boolean manip-
ulation very difficult if not impossible. Notice that the compressed K-map in Fig. 5.3c is