Page 188 - Engineering Digital Design

4.6 ENTERED VARIABLE K-MAP MINIMIZATION 159

A B

/Cell 0
AC + AB

FIGURE 4.28
(a) Truth table for function Y in Eq. (4.39) showing subfunctions for a first-order map compression,
(b), (c) Second and first-order EV K-maps showing submaps and minimum SOP cover extracted in
minterm code.

each cell of the nth-order K-map becomes a submap of order (N — n), hence K-maps within
K-maps.
To illustrate, consider the three-variable function

y(A,fi,C) = ^m(l,3,4,5,6), (4.39)

which has been placed in a truth table and mapped into a second-order EV K-map, as shown
in Figs. 4.28a and 4.28b. The subfunctions indicated to the right of the truth table are also
represented as first-order submaps corresponding to the cells 0, 1,2, and 3 in the EV K-map
of Fig. 4.28b. The minimum cover is then obtained by looping out the cell entries, as shown
by the shaded loops, giving the minimum result

Y SOP = AC + AC + AB. (4.40)

Notice that the term AC covers only the C in the 1 = C + C of cell 2. This requires that
the C in the 1 be covered by one of the two OPIs, AB or BC, and the former is chosen.
The same result can be obtained from a second-order compression if the expression of
Eq. (4.39) is compressed into a first-order K-map. This is done in Fig. 4.28c, where B
and C are now the EVs. The minimum cover is indicated by the shaded loops, yielding