Page 176 - Engineering Digital Design

4.4 KARNAUGH MAP FUNCTION MINIMIZATION 147

A\ 00 01 / ' 11 10

FIGURE 4.16
K-maps for Eq. (4.23). (a) Minimum SOP cover, (b) Minimum POS cover.

and
= (A + X + Y)(X + Y)(A + Y) (minimum POS cover).

Application of the laws of Boolean algebra shows that the SOP and POS minima are alge-
braically equal:
(A + X + Y)(X + 7)(A + 7) = (A + X + Y)(AX + XY + AY + Y)
= (A + X + Y)(AX + Y)

As a second example, consider the reduced function given in POS form:

Y(A, £, C, D) = (A + # + D)(B + C)(A + C + D)(A + B + C + D). (4.24)
To map this function, one simply maps the O's in maxterm code, as indicated in Fig. 4.17a.
The representation in Fig. 4.17a is not minimum. However, after the maxterms are re-
grouped, a minimum POS representation is shown in Fig. 4.17b. Notice that the dyad
M(5, 13) crosses the A boundary, permitting (AA + B + C + D) = (B + C + D) as the re-
duced s-term. Similarly, the quad M(2, 3, 6, 7) crosses the B and D boundaries to yield
(A + BB + C + DD = (A + C). Also, the quad Af (2, 3, 10, 1 1) crosses the A and D bound-
aries, eliminating these variables to give (B + C) as the reduced s-term.
The minimum SOP cover for the function Y of Eq. (4.24) is shown in Fig. 4.17c and
consists of one dyad and two quads. The dyad m( 14, 15) crosses the D boundary, permitting
ABC(D + D)=ABC, while the quad ra(0, 4, 8, 12) crosses the A and B boundaries, yielding
(A + A)(B + B)CD = CD. Likewise, the quad m(0, 1,8,9) crosses the A and D boundaries
to give BC as the reduced p-term. The minimized results that are extracted from Figs. 4. 17b
and 4.17c are now presented as

Ypos = (B + C + D)(A + C)(B + C) Minimum POS cover
and
Y SOp = ABC + CD + B C, Minimum SOP cover