Page 1049 - The Mechatronics Handbook

y y y 1 y y y
1 0
1 0
00 01 11 10 00 01 11 1 10
x x x x
1 0
1 0
00 0000 0000 0000 0000 00
y y 01 0000 0001 0011 0010 01
x 0 1 x 0 x 0
11 0000 0011 1001 0110 11 1
0 0 0 x 1 x 1
10 0000 0010 0110 0100 10
x 1 0 1
(a) (b) y (c)
0 y 0
y y y 1 y y y 1 y y y 1
1 0
1 0
1 0
00 01 11 10 00 01 11 10 x x 00 01 11 10
x x x x 1 0
1 0 1 0
00 00 00
01 01 1 1 01 1 1
x x x
0 0 0
11 1 11 1 1 11 1 1
x 1 x 1 x 1
10 1 1 10 1 1 10
(d) y 0 (e) y 0 (f) y 0
FIGURE 36.17 Examples of K-maps formulated as function tables: (a) K-map for the product of two 1-b numbers
P = x * y; (b) composite K-map for the product of two 2-b numbers, P 3 P 2 P 1 P 0 = x 1 x 0 * y 1 y 0 ; (c) K-map for the
digit P 3 of the product of two 2-b numbers; (d) K-map for the digit P 2 of the product of two 2-b numbers; (e) K-map
for the digit P 1 of the product of two 2-b numbers; (f) K-map for the digit P 0 of the product of two 2-b numbers.
36.18 Minimization with K-Maps
The key feature of K-maps that renders them convenient for minimization is that minterms, which are
spatially adjacent in the horizontal or vertical directions, are logically adjacent. Logically adjacent min-
terms are identical in all variables except one. This allows the two minterms to be combined into a single
terms with one less variable. This is illustrated in Fig. 36.18. Two adjacent minterms combine into a first-
order implicant. A first-order implicant is the combination of all of the independent variables but one.
In this example, the first-order implicant expressed in terms of minterms contains eight literals but the
minimized expression contains only three literals. The circuit realization for the OR combination of the
two minterms has two AND gates and one OR gate, whereas the realization for the equivalent implicant
requires only a single AND gate.
The combination of minterms into first-order implicants can be represented more compactly by using
the single symbol minterm notation with the subscript that identifies the particular minterm expressed
in binary, as illustrated in Fig. 36.18(d).
Two adjacent first-order implicants can be combined into a second-order implicant as illustrated in Fig.
36.19. A second-order implicant contains all of the independent variables except two. In general, an nth-
n
order implicant contains all of the variables except n and requires an appropriately grouped set of 2 minterms.
Minterms that are at opposite edges of the same row or column are logically adjacent since they differ
in only one variable. If the plane space is rolled into a cylinder with opposite edges touching, then the
logically adjacent edge pairs become physically adjacent. For larger numbers of variables using K-maps
with parallel sheets, the corresponding positions on different sheets are logically adjacent. If the sheets
are considered as overlaid, the corresponding squares are physcally adjacent. The minimized expression
is obtained by covering all of the minterms with the fewest number of largest possible implicants. A
minterm is a zero-order implicant. Figure 36.20 illustrates a variety of examples. A don’t care is a value
that never occurs or if it does occur it is not used, and hence, it does not matter what its value is. Don’t
cares are also included to illustrate that they can be used to simplify expressions by taking their values
to maximize the order of the implicants.
Maxterm K-maps can also be utilized to obtain minimized expressions by combining maxterms into
higher order implicants, as illustrated for the example in Fig. 36.21.

©2002 CRC Press LLC