Page 216 - Engineering Digital Design

4.12 WORKED EV K-MAP EXAMPLES 187

o i X? o
0 1 1 0 n 1
0 1 4 5
1 0 1 A^ 0 1 <\ 1 0 1
f
2 3 / .. ^ __ 6 7 / ^ 0 ^
II II
'0 o C + IEJ(6- CD +[CD 1 '1 0 [C * DJ (C+D) [6+D)
\
c\ c 0 1
1 -^ CD 1 [ c + D
0 1 1 JL 3 °1 0 1 © 5) . /
8 9 12 — 12
' ^SOP . ^2 -POS
1 0 n n
10 11 / 14 15 /
(a) ' d (b)
FIGURE 4.58
Second-order EV K-maps and submaps for the function Z in Eq. (4.77) showing (a) minimum SOP
cover and (b) minimum POS cover.
minimum POS cover for the function Z with the results given by

ZSOP = ABCD + ABD + ABD + BC + CD
Zpos = (A + B + C + D)(B + C + D)(B + C + D)(A + B + D)(A + C + D)

Notice how easy it is to read a subfunction when accompanied by a submap. Thus, the
SOP term CD is easily observed to be present in each of the four submaps of Fig. 4.58a.
Similarly, CD, read as a POS term in Fig. 4.58b, is seen to contain both the (C + D) and
(C + D) terms by a cursory inspection of the submaps.
EXAMPLE 4.7 Compress the following six-variable function into a fourth-order EV
K-map and extract minimum SOP and minimum POS cover for it:

W(A,B,C,D,E,F) = Y^™(4,6,&,9, 10, 11, 12, 13, 14, 15,20,22,26,27,30,31,
36, 38, 39, 52, 54, 56, 57, 60, 61). (4.78)

Compressing a six-variable function into a fourth-order K-map requires a Map Key of
6 4
2 ~ = 4, hence four possible minterms per K-map cell. This is a second-order compression
meaning that each cell of the K-map contains subfunctions from a second-order K-map.
Shown in Fig. 4.59 are the fourth-order K-maps for the function W in Eq. (4.78) where the
EVs are E and F. The minimum covers for the SOP and POS functions are indicated by
shaded loops and yield

WSOP = ABCDE + ABCE + CDF + ACE + ABC

WPOS = (A + B + C + E)(C + E + F)(B + C + F)(A + C + F)(A + C + E)
• (A + B + C)(C + D),

which represent gate/input tallies of 6/23 and 8/28, respectively. Note that the loop-out
protocol is applied first to the EVs and then to the 1 's and O's as cleanup operations, a proce-
dure that should always be followed. Observe also that these expressions are algebraically
equal since no don't cares are involved.