Page 213 - Engineering Digital Design

184 CHAPTER 4/LOGIC FUNCTION REPRESENTATION AND MINIMIZATION

D> CelM
C- D 1

+ C + D
F cv
"-F \°

Cell 2 Cell 3

(a) (b)
FIGURE 4.54
(a) Second-order compressed K-map and its submaps for the four-variable function given in the EV
truth table of Fig. 4.53. (b) EV K-maps showing minimum SOP cover and minimum POS cover.

(a) The simplest means of obtaining the canonical forms from Fig. 4.53 is to use a
second-order K-map. Shown in Fig. 4.54a is the second-order compressed K-map together
4 2
with its submaps for a Map Key of 2 ~ = 4. By reading the submaps directly, the canonical
forms become

F = £] m(3, 6, 9, 10, 1 1) + 0(7, 8)

2 4 5 12 13 14 15 7
' < > ' > < > > ' 0( . 8). (4.74)
(b) The compressed second-order K-maps for the function F are given in Fig. 4.54b.
From these K-maps the minimum SOP and minimum POS expressions are found to be

F SOp = BCD + ABC + AB
FPOS = (A + B + D)(A + C}(A + B),

with gate/input tallies of 4/1 1 and 4/10, respectively, excluding possible inverters. Notice
that the minimum SOP and POS cover results from these K-maps by taking 07 = 1 to give
C(0 7 +D) = C in cell 1 , and by taking 0 g = 1 to give (0 8 + C + D) = 1 in cell 2. Because the
don't cares, 07 and 0 g , are used in the same way (no shared use) in both K-maps of Fig. 4.54b,
the minimum SOP and POS expressions are algebraically equal.
EXAMPLE 4.4 A five-variable function / is given in the canonical form:

/(A, B, C, D, E) = J]fn(3, 9, 10, 12, 13, 16, 17, 24, 25, 26, 27, 29, 31). (4.75)
(a) Use a fourth-order EV K-map to minimize this function in both SOP and POS form.
A compression of one order requires that the Map Key be 2. Therefore, each cell of
the fourth-order EV map represents a first-order submap covering two possible minterm or