ic
Section 8.3 Minimization
669
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.29
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.30
To avoid the redundancy illustrated by Example 23, we analyze the map as
follows. First, we form terms for those marked squares that cannot be combined
with anything. Then we use the remaining marked squares to find those that can be
combined only into two-square blocks and in only one way. Then among the unused marked squares—that is, those not already assigned to a block—we find those
that can be combined only into four-square blocks and in only one way; then we
look for any unused squares that go uniquely into eight-square blocks. At each step,
if an unused marked square can go into more than one block, we do nothing with
it. Finally, we take any unused marked squares that are left (for which there was a
choice of blocks) and select blocks that include them in the most efficient manner.
Table 8.12 shows the steps involved. Note, however, that this procedure for
handling Karnaugh maps is not, strictly speaking, an algorithm because it doesn’t
always produce the correct result. If there are many 1s in the map, thus allowing
many different blockings, even this procedure may not lead to a minimal form
(see Example 28).
Table 8.12
Steps in Using Karnaugh Maps
1. Set up the grid, using correct labeling for the number of Boolean variables.
2. Insert 1s in the table for the terms in the canonical sum-of-products expression.
3. Form terms for any isolated marked squares.
4. Combine squares uniquely into two-square blocks, if possible.
5. Combine squares uniquely into four-square blocks, if possible.
6. Combine squares uniquely into eight-square blocks, if possible.
7. Combine any remaining unused marked squares into blocks as efficiently as possible.
exaMple 24
In Figure 8.31a we show the only square that cannot be combined into a larger
block. In Figure 8.31b, we have formed the unique two-square block for the x 1 x 2 ′x 3 ′
square and the unique two-square block for the x 1 ′x 2 ′x 3 square. All marked squares
are covered. The minimal sum-of-products expression is
x 1 x 2 x 3 + x 2 ′x 3 ′ + x 1 ′x 2 ′
Section 8.3 Minimization
669
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.29
1
1
1
1
1
1
1
1
x 1 x 2
x 3 x 4
x 1 xЈ 2
x 3 xЈ 4
xЈ 1 xЈ 2
xЈ 3 xЈ 4
xЈ 1 x 2
xЈ 3 x 4
Figure 8.30
To avoid the redundancy illustrated by Example 23, we analyze the map as
follows. First, we form terms for those marked squares that cannot be combined
with anything. Then we use the remaining marked squares to find those that can be
combined only into two-square blocks and in only one way. Then among the unused marked squares—that is, those not already assigned to a block—we find those
that can be combined only into four-square blocks and in only one way; then we
look for any unused squares that go uniquely into eight-square blocks. At each step,
if an unused marked square can go into more than one block, we do nothing with
it. Finally, we take any unused marked squares that are left (for which there was a
choice of blocks) and select blocks that include them in the most efficient manner.
Table 8.12 shows the steps involved. Note, however, that this procedure for
handling Karnaugh maps is not, strictly speaking, an algorithm because it doesn’t
always produce the correct result. If there are many 1s in the map, thus allowing
many different blockings, even this procedure may not lead to a minimal form
(see Example 28).
Table 8.12
Steps in Using Karnaugh Maps
1. Set up the grid, using correct labeling for the number of Boolean variables.
2. Insert 1s in the table for the terms in the canonical sum-of-products expression.
3. Form terms for any isolated marked squares.
4. Combine squares uniquely into two-square blocks, if possible.
5. Combine squares uniquely into four-square blocks, if possible.
6. Combine squares uniquely into eight-square blocks, if possible.
7. Combine any remaining unused marked squares into blocks as efficiently as possible.
exaMple 24
In Figure 8.31a we show the only square that cannot be combined into a larger
block. In Figure 8.31b, we have formed the unique two-square block for the x 1 x 2 ′x 3 ′
square and the unique two-square block for the x 1 ′x 2 ′x 3 square. All marked squares
are covered. The minimal sum-of-products expression is
x 1 x 2 x 3 + x 2 ′x 3 ′ + x 1 ′x 2 ′