Файл: Digital design with CPLD applications and VHDL (R. Dueck, 2000).pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 13.06.2025
Просмотров: 8142
Скачиваний: 6
94 C H A P T E R 3 • Boolean Algebra and Combinational Logic
Loading a K-Map From a Truth Table
N O T E
We don’t need a Boolean expression to fill a Karnaugh map if we have the function’s truth table.
Figures 3.45 and 3.46 show truth table and Karnaugh map forms for threeand four-vari- able Boolean expressions. The numbers in parentheses show the order of terms in binary sequence for both forms.
The Karnaugh map is not laid out in the same order as the truth table. That is, it is not laid out in a binary sequence. This is due to the criterion for cell adjacency: no more than one variable change between rows or columns is permitted.
FIGURE 3.45
Order of Terms (Three-Variable
Function)
FIGURE 3.46
Order of Terms (Four-Variable
Function)
Filling in a Karnaugh map from a truth table is easy when you understand a system for doing it quickly. For the three-variable map, fill row 1, then row 2, skip to row 4, then go back to row 3. By doing this, you trace through the cells in binary order. Use the mnemonic phrase “1, 2, skip, back” to help you remember this.
The system for the four-variable map is similar but must account for the columns as well. The rows get filled in the same order as the three-variable map, but within each row, fill column 1, then column 2, skip to column 4, then go back to column 3. Again, “1, 2, skip, back.”
3.5 • Simplification by the Karnaugh Map Method |
95 |
||||||||
The four-variable map is easier to fill from the truth table if we break up the truth table |
|||||||||
into groups of four lines, as we have done in Figure 3.46. Each group is one row in the Kar- |
|||||||||
naugh map. Following this system will quickly fill the cells in binary order. |
|||||||||
Go back and follow the order of terms on the four-variable map in Figure 3.46, using |
|||||||||
this system. (Remember, for both rows and columns, “1, 2, skip, back.”) |
|||||||||
Multiple Groups |
|||||||||
N O T E |
|||||||||
If there is more than one group of 1s in a K-map simplification, each group is a |
|||||||||
term in the maximum SOP simplification of the mapped Boolean expression. The |
|||||||||
resulting terms are ORed together. |
|||||||||
EXAMPLE 3.17 |
Use the Karnaugh map method to simplify the Boolean function represented by Table 3.13. |
||||||||
Table 3.13 Truth Table for |
|||||||||
Example 4.3 |
|||||||||
A |
B |
C |
D |
Y |
|||||
0 |
0 |
0 |
0 |
1 |
|||||
0 |
0 |
0 |
1 |
0 |
|||||
0 |
0 |
1 |
0 |
1 |
|||||
0 |
0 |
1 |
1 |
0 |
|||||
0 |
1 |
0 |
0 |
0 |
|||||
0 |
1 |
0 |
1 |
1 |
|||||
0 |
1 |
1 |
0 |
0 |
|||||
0 |
1 |
1 |
1 |
1 |
FIGURE 3.47 |
||||
1 |
0 |
0 |
0 |
0 |
|||||
Example 3.17 |
|||||||||
1 |
0 |
0 |
1 |
0 |
|||||
K-Map |
|||||||||
1 |
0 |
1 |
0 |
0 |
|||||
1 |
0 |
1 |
1 |
0 |
|||||
1 |
1 |
0 |
0 |
0 |
|||||
1 |
1 |
0 |
1 |
1 |
|||||
1 |
1 |
1 |
0 |
0 |
|||||
1 |
1 |
1 |
1 |
1 |
|||||
Solution Figure 3.47 shows the Karnaugh map for the truth table in Table 3.14. There are two groups of 1s—a pair and a quad.
Pair:
Variables A, B, and D are coordinates of both cells. (Keep A B D.) C is a coordinate of one cell and C is a coordinate of the other. (Discard C.)
Term: A B D
Quad:
Both A and C are coordinates of two cells in true form and two cells in complement form. (Discard A and C.)
B and D are coordinates of all four cells. (Keep B D.) |
|
Term: B D |
|
Combine the terms in an OR function: |
|
Y A B D B D |
|
96 C H A P T E R 3 • Boolean Algebra and Combinational Logic
Overlapping Groups
N O T E
A cell may be grouped more than once. The only condition is that every group must have at least one cell that does not belong to any other group. Otherwise, redundant terms will result.
EXAMPLE 3.18
Table 3.14 |
Truth Table |
||
for Example 3.18 |
|||
A |
B |
C |
Y |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
Simplify the function represented by Table 3.14.
Solution The Karnaugh map for the function in Table 3.14 is shown in Figure 3.48, with two different groupings of terms.
FIGURE 3.48
Example 3.18
K-Maps
a. The simplified Boolean expression drawn from the first map has three terms.
Y A B A B B C
b. The second map yields an expression with four terms.
Y A B A B B C A C
One of the last two terms is redundant, since neither of the pairs corresponding to these terms has a cell belonging only to that pair. We could retain either pair of cells and its corresponding term, but not both.
We can show algebraically that the last term is redundant and thus make the expression the same as that in part a.
Y A B A B B C A C
A B A B B C A (B B) CA B A B B C A B C A B C
A B (1 C) A B B C (1 A)
A B A B B C
3.5 • Simplification by the Karnaugh Map Method |
97 |
Conditions for Maximum Simplification
N O T E
The maximum simplification of a Boolean expression is achieved only if the circled groups of cells in its K-map are as large as possible and there are as few groups as possible.
EXAMPLE 3.19
FIGURE 3.49
Example 3.19
K-Maps
Table 3.15 Truth Table for Example 3.19
A |
B |
C |
D |
Y |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Find the maximum SOP simplification of the Boolean function represented by Table 3.15.
Solution The values of Table 3.15 are loaded into the three K-maps shown in Figure 3.49. Three different ways of grouping adjacent cells are shown. One results in maximum simplification; the other two do not.
We get the maximum SOP simplification by grouping the two octets shown in Figure 3.49a. The resulting expression is
a. Y B D
Figures 3.49b and c show two simplifications that are less than the maximum because the chosen cell groups are smaller than they could be. The resulting expressions are:
b.Y A B A B D
c.Y B B D
Neither of these expressions is the simplest possible, since both can be reduced by Boolean algebra to the form in Figure 3.49a.
98 C H A P T E R 3 • Boolean Algebra and Combinational Logic
Using K-Maps for Partially Simplified Circuits
Figure 3.50 shows a logic diagram that can be further simplified. If we want to use a Karnaugh map for this process, we must do one of two things:
1.Fill in the K-map from the existing product terms. Each product term that is not a minterm will represent more than one cell in the Karnaugh map. When the map is filled, regroup the cells for maximum simplification.
2.Expand the sum-of-products expression of the circuit to get a sum-of-minterms form. Each minterm represents one cell in the K-map. Group the cells for maximum simplification.
FIGURE 3.50
Logic Diagram That Can Be
Further Simplified
FIGURE 3.51
Further Simplification of Logic Diagram (Figure 3.50)
Figure 3.51 shows the K-map derived from the existing circuit and the regrouped cells that yield the maximum simplification.
The algebraic method requires us to expand the existing Boolean expression to get a sum of minterms. The original expression is:
Y A B C D A B D A C
The theorem (x x) 1 implies that we can AND a variable with a term in true and complement form without changing the term. The expanded expression is:
Y A B C D A B (C C) D A (B B) C (D D)A B C D A B C D A B C D
A B C D A B C D A B C D A B C D
The terms of this expression can be loaded into a K-map and simplified, as shown in
Figure 3.51b. Figure 3.52 shows the logic diagram for the simplified expression.
3.5 • Simplification by the Karnaugh Map Method |
99 |
FIGURE 3.52
Simplified Circuit
EXAMPLE 3.20 |
Use a Karnaugh map to find the maximum SOP simplification of the circuit shown in |
Figure 3.53. |
|
FIGURE 3.53 |
|
Example 3.20 |
|
Circuit to Be Simplified |
Solution Figure 3.54a shows the Karnaugh map of Figure 3.53 with terms grouped as shown in the original circuit. Figure 3.54b shows the terms regrouped for the maximum simplification, which is given by:
Y A D B D A B C
Alternate method: The Boolean expression for the circuit in Figure 3.53 is:
Y A B C A C D B C D A B C D
FIGURE 3.54
Example 3.20
Maximum Simplification of
Figure 3.53
100 C H A P T E R 3 • Boolean Algebra and Combinational Logic
This expands to the following expression:
Y A B C (D D) A (B B) C D (A A) B C D A B C D
A B C D A B C D A B C D A B C D A B C D
A B C D A B C D
This expression can be loaded directly into the K-map and simplified, as shown in Figure 3.54b. The logic diagram for the simplified expression is shown in Figure 3.55.
FIGURE 3.55
Example 3.20
Simplified Circuit
Don’t Care States
K E Y T E R M S
Don’t care state An output state that can be regarded as either HIGH or LOW, as is most convenient. A don’t care state is the output state of a circuit for a combination of inputs that will never occur.
Sometimes a digital circuit will be intended to work only for certain combinations of inputs; any other input values will never be applied to the circuit.
In such a case, it may be to our advantage to use so-called don’t care states to simplify the circuit. A don’t care state is shown in a K-map cell as an “X” and can be either a 0 or a 1, depending on which case will yield the maximum simplification.
A common application of the don’t care state is a digital circuit designed for binarycoded decimal (BCD) inputs. In BCD, a decimal digit (0–9) is encoded as a 4-bit binary number (0000–1001). This leaves six binary states that are never used (1010, 1011, 1100, 1101, 1110, 1111). In any circuit designed for BCD inputs, these states are don’t care
states. |
|
All cells containing 1s must be grouped if we are looking for a maximum SOP simpli- |
|
fication. (If necessary, a group can contain one cell.) The don’t care states can be used to |
|
maximize the size of these groups. We need not group all don’t care states, only those that |
|
actually contribute to a maximum simplification. |
|
EXAMPLE 3.21 |
The circuit in Figure 3.56 is designed to accept binary-coded decimal inputs. The output is |
HIGH when the input is the BCD equivalent of 5, 7, or 9. If the BCD equivalent of the in- |
|
put is not 5, 7 or 9, the output is LOW. The output is not defined for input values greater |
|
than 9. |
|
Find the maximum SOP simplification of the circuit. |
D1
D2
D3
D4
FIGURE 3.56
Example 3.21
Circuit to be Simplified
3.5 • Simplification by the Karnaugh Map Method |
101 |
Solution The Karnaugh map for the circuit is shown in Figure 3.57a.
We can designate three of the don’t care cells as 1s—those corresponding to input states 1011, 1101, and 1111. This allows us to group the 1s into two overlapping quads, which yield the following simplification.
Y D4 D1 D3 D1
The ungrouped don’t care states are treated as 0s. The corresponding circuit is shown in Figure 3.57b.
FIGURE 3.57
Example 3.21
Karnaugh Map and Logic
Diagram
EXAMPLE 3.22
Applications
One type of decimal code is called 2421 code, so called because of the positional weights of its bits. (For example, 1011 in 2421 code is equivalent to 2 2 1 5 in decimal. 1100 is equivalent to decimal 2 4 6.) Table 3.16 shows how this code compares to its equivalent decimal digits and to the BCD code used in Example 3.21.
2421 code is sometimes used because it is “self-complementing,” a property that BCD code does not have, but that is useful in digital decimal arithmetic circuits.
The bits of the BCD code are designated D4 D3 D2 D1. The bits of the 2421 code are
designated Y4 Y3 Y2 Y1.
Use the Karnaugh map method to design a logic circuit that accepts any BCD input and generates an output in 2421 code, as specified by Table 3.16.
Solution The required circuit is called a code converter. Each 4-bit BCD input corresponds to a 4-bit 2421 output. Thus, we must find four Boolean expressions, one for each
Table 3.16 BCD and 2421 Code
Decimal |
BCD Code |
2421 Code |
||||||
Equivalent |
D4 |
D3 |
D2 |
D1 |
Y4 |
Y3 |
Y2 |
Y1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
3 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
4 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
5 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
6 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
7 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
8 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
9 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |