Page 189 - Engineering Digital Design

160 CHAPTER 4/LOGIC FUNCTION REPRESENTATION AND MINIMIZATION

the expression in Eq. (4.40). The OPI BC is not easily seen in the first-order EV K-map,
but can be found by observing the 1's representing BC in the two submaps shown in
Fig. 4.28c.

Map Key It has already been pointed out that each cell of the compressed nth-order
K-map represents a submap of order (N — n) for an N > n variable function. Thus, each
N n
submap covers 2 ~ possible minterms or maxterms. This leads to the conclusion that any
compressed nth-order K-map, representing a function of N >n variables, has a Map Key
defined by

N n
Map Key = 2 ~ N >n (4.41)

The Map Key has the special property that when multiplied by a cell code number of
the compressed nth-order K-map there results the code number of the first minterm or
maxterm possible for that cell. Furthermore, the Map Key also gives the maximum number
of minterms or maxterms that can be represented by a given cell of the compressed nth-order
K-map. These facts may be summarized as follows:

Conventional K-map: Map Key = 1 (no EVs, 1's and O's only)
First-order compression K-map: Map Key = 2 (one EV)
Second-order compression K-map: Map Key = 4 (two EVs)
Third-order compression K-map: Map Key = 8 (three EVs), etc.

As an example, the first-order compressed K-map in Fig. 4.28b has a Map Key of
3 2
2 ~ = 2. So each of its cells represents two possible minterms (first-order submaps) begin-
ning with minterm code number equal to (Map Key = 2) x (Cell Number). This is evident
from an inspection of the truth table in Fig. 4.28a. Similarly, the second-order compression in
3
Fig. 4.28c has a Map Key of 2 ~' =4. Therefore, each cell represents four possible minterms
represented by the conventional second-order submaps shown to the sides of Fig. 4.28c.
The compressed K-maps in Fig. 4.28 can also be read in maxterm code as indicated by
the shaded loops in Fig. 4.29. In this case the logic 1 in cell 2 must be excluded. The result
for either the first-order or second-order compressed K-maps is

= (A+B + C)(A + C). (4.42)

(A+C)

( A+B+C ) (A+B+C)
FIGURE 4.29
Second- and first-order EV K-maps showing minimum POS cover for function Y extracted in maxterm
code.