Page 180 - Engineering Digital Design

4.4 KARNAUGH MAP FUNCTION MINIMIZATION 151

B r 00 "'' 03 6 /"' MC) B
'
\BC / >^ 00/01 r-Ti ^-l
C
A\ 00 01 10/
0 0 1 1 $ ~o*) 1 1 <T~
0 1 3 2 0 1 3 2
1 1 ^ ) T( 1 0 1 1 0
f 4 5 \ 7 6 / 4 ^ 5 7 j — '^e
/ \ •^ ^SOP ^'POS
B^ C ^ c (B+C)
(a) (b)

FIGURE 4.19
K-maps for Eq. (4.28) showing EPIs containing don't cares, (a) Minimum SOP cover, (b) Minimum
POS cover.

Notice that the don't cares 02 and 05 are purposely used differently to obtain the minimum
SOP and POS expressions of Eqs. (4.29). The result is that the F SQP and FPQS expressions
are algebraically equal since there is no shared use of don't cares between the two functions
(05 = 1 and 02 = 0 in both cases). Thus, F SOp can be produced by algebraically manipu-
lating FPOS- Had no use been made of the two don't cares in Fig. 4. 19, the results would be
quite different, namely F SOP = ABC + AC + BC and F POS = (A + B + C)(A + B + C),
which are logically equivalent but not algebraically equal.
As a second example consider the four- variable function given in canonical POS form
showing essential and nonessential maxterms:

Y(A,B,C,D)= f~[M(0, 1,2,4,6,9, 11, 15) • 0(3,8, 10, 12).
7 v .. , Nonessential
Essential maxterms
"Wrms (don't cares)
In Fig. 4.20 the O's and 0's of Eq. (4.30) are mapped in maxterm code, and the mini-
mum covers for Y POs and YSOP are shown by the shaded loops in Figs. 4.20a and 4.20b,
respectively. The resulting minimum POS and SOP expressions for Eq. (4.30) are

(4.31)
YSOP = ABD + BCD + AD

Again it is noted that these expressions are logically equivalent. However, they are alge-
braically unequal because of the shared use of don't cares (0g and 0io) in the loop-out
process. Notice also that YSOP contains OPIs BCD and ABC with ABD as an EPI, since
minterm m 13 can be looped out in two ways (with m*, or with 0 )2). Similarly, OPIs ABD
and A CD result if BCD is an EPI, since minterm ra 7 can be looped out in two ways (with
ra 5 and with 03 ). No OPIs exist for Y POs-

The Gate/Input Tally vs Cardinality of a Function Throughout this text use will be
made of the ratio of the gate tally to the input tally (gate/input tally) as a measure of function
complexity in terms of hardware cost. Input tallies include both external and internal inputs