Page 190 - Engineering Digital Design

4.6 ENTERED VARIABLE K-MAP MINIMIZATION 161

\BC
A\ 00 01

C

(a) (b)
FIGURE 4.30
(a) Conventional K-map for function Y of Eq. (4.39). (b) Second-order EV K-map with entered
variable A showing minimum cover for Y as extracted in minterm code.

That YPOS in Eq. (4.40) and Y SOp in Eq. (4.42) are algebraically equal is made evident by
carrying out the following Boolean manipulation:
(A + B + C)(A + O = AC + AC + [AB + BC],

where the two p-terms in brackets are OPIs, thereby rendering one to be redundant.
In the second-order K-maps of Figs. 4.28 and 4.29, C is taken to be the EV. However,
any of the three variables could have been chosen as the EV in the first-order compres-
sion K-maps. As an example, variable A is the EV in Fig. 4.30, where the columns in
the conventional K-map of (a) form the submaps of the cells in the compressed K-map
of Fig. 4.30b. Minimum cover extracted in minterm code then yields the same result as
Eq. (4.40). Or, if extracted in maxterm code, Eq. (4.42) would result. Thus, one concludes
that the choice of EVs in a compressed K-map does not affect the extracted minimum result.
Reduced but nonminimum functions can be easily compressed into EV K-maps. This is
demonstrated by mapping the four- variable function

X = BCD+AB+ACD+ABCD + ABC (4.43)

into the third-order EV K-maps shown in Fig. 4.31, where the Map Key is 2. Here, D is
the EV and 1 = (D + D). Figure 4.3 la shows the p-terms (loops) exactly as presented in
Eq. (4.43). However, regrouping of the logic adjacencies permits minimum SOP and POS
cover to be extracted. This is done in Figs. 4.3 Ib and 4.3 Ic, yielding

(4.44)

where the expressions for XSOP and X POs represent gate/input tallies of 4/9 and 3/7, res-
pectively, excluding possible inverters.
The four- variable function X in Eq. (4.43) can also be minimized in a second-order EV
K-map. Shown in Fig. 4.32 is the second-order compression and minimum SOP and POS
cover for this function, giving the same results as in Eqs. (4.44). Notice that after covering
the D in cell 1 of Fig. 4.32a, it is necessary to cover all that remains in cell 0 by looping
out the 1 as an island to give AB. In this case the 1 has the value 1 — C + C = D + D.
Clearly, the 1 in cell 0 cannot be used in extracting minimum cover in maxterm code.