2.5: Karnaugh Maps (K-maps)
- Page ID
- 26950
Karnaugh Maps (K-maps) are a mechanism for creating minimum Boolean expressions from a truth table. K-maps rely on Gray Codes to create the mapping space, so this chapter will first cover Gray Codes. The chapter will continue with how to set up a K-map, how to solve a K-map, and how to solve a K-map with don't care conditions.
\(\PageIndex{1}\) Gray Codes
Gray codes are simply binary codes where the numbers adjacent numbers differ by a single digit. A single digit number only has a single digit, so it is trivial. Now consider the Gray Code for a two digit numbers. It would be:
|
00 01 11 10 |
In this Gray Code, each number differs from its neighbor by 1 digit. 00->01->11->10->00 (note that the Gray code is circular or wraps around from the bottom to the top). A 3 digit Gray Code can be created by reflecting (like a mirror) the 2 digit Gray Code through a plane, and prepending a 0 to the numbers at the top of the table, and a 1 to the numbers at the bottom of the table.
|
000 001 011 \(\ \underline{010}\) 110 111 101 100 |
Once again that all values in this table differ from the adjacent values by 1 digit, but in addition the table has been grouped into collections of 2-bit groupings. For example, the rows 0 and 1 both contain 00x, rows 1 and 2 contain 0x1, rows 2 and 3 contain 10x, rows 3 and 4 contain x10, etc (where x is 0,1). Note that once again the table wraps, so rows 7 and 0 both contain x00.
Gray Codes are useful in partitioning a space to group like elements together, and this property will be used in the next section on K-maps.
\(\PageIndex{2}\) 2-Variable Karnaugh Maps
A Karnaugh map (or simply K-map) is a mapping of a truth table that partitions the truth table so that elements that have the same values are placed adjacent to each other. It is then easier to see what terms are in common, and to reduce the Boolean expression. For example a 2-variable K-map for a function F(A,B) would be represented as follows, with the values of A in rows and the values of B in the columns.
| A/B |
0 |
1 |
|
0 |
A'B' |
A'B |
|
1 |
AB' |
AB |
In this table, the rows correspond to A and not-A, and the columns correspond to B and not-B.
Table \(\PageIndex{4}\): A/A' for 2-variable K-map
Table \(\PageIndex{5}\): B/B' for a 2-variable K-map
Since the K-map has grouped the terms together, it is easier to find a minimum Boolean equation. For example, consider the following truth table:
|
Input |
Output |
|
|
A |
B |
AND |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
This truth table maps to the following K-map. In this K-map groups of 2n adjacent items are found, which for a 2-variable K-map can only be groups of 4, 2 and 1. In this map there are 2 groups of 2, as shown below.
Table \(\PageIndex{7}\): Solving a 2-variable K-map
The two grouping found correspond to A' and B', so the final equation for this K-map is A'+B'.
Two variable K-maps are trivial, and so not very interesting. The next two sections will show how to solve the K-maps for more 3 and 4 variables.
\(\PageIndex{3}\) 3-Variable Karnaugh Maps
3-variable K-maps correspond to Boolean functions of the form f(A, B, C). The K-maps again allow a truth table to be mapped so that rows that differ by 1 or 2 values are placed next to each other. To do this, the Gray Codes that were introduced earlier are used. Note how the values for variables B and C are numbered as Gray Codes in the 3-variable K-map table.
| A/BC |
00 |
01 |
11 |
10 |
|
0 |
A'B'C' |
A'B'C |
A'BC |
A'BC' |
|
1 |
AB'C' |
AB'C |
ABC |
A'BC' |
Note that once again this number has resulted in regions in the K-map where the variables differ by 1 digit, as shown below. Note that the region C' wraps around the table.
Table \(\PageIndex{9}\): A/A' region of a 3-variable K-map
Table \(\PageIndex{10}\): B/B' region of a 3-variable K-map
Table \(\PageIndex{11}\): C/C' region of a 3-variable K-map
To use the K-map to solve 3 variable functions, once again groupings of 2n are found, which for a 3-variable K-map are 8, 4, 2, and 1. The larger the grouping, the fewer the terms, so groupings of 8 are chosen over groupings of 4, groupings of 4 are chosen over groupings of 2, and groupings of 2 are chosen over groupings of 1.
The following is an example of how to use a K-map to solve a Boolean expression. Consider a function f(A,B,C) has the following truth table:
|
Input |
f(A,B,C) |
||
|
A |
B |
C |
AND |
| 0 | 0 | 0 | 1 |
| 0 | 1 | 0 | 0 |
|
0 |
1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
This expression can be represented as the following sum of products.
f(A,B,C) = Σ(0, 4, 5, 6, 7)
The minimum function for this K-map consists of one group of 4 and one group of 2, and corresponds to the equation f(A,B,C) = A+B'C'. Note the cell AB'C' is used in both equations, which is rule 5 from the Boolean relationship table, X+X = X, and means that any term in the summation can be used more than once in minimizing the circuit.
To show that the final equation corresponds to the initial truth table, algebra will be used to reduce the expression from DNF to the final form.
\[\begin{aligned}
\mathrm{f(A,B,C)}
&= Σ(0,\: 4,\: 5,\: 6,\: 7)\\
&= \mathrm{A'B'C' + AB'C' + AB'C + ABC' + ABC}\\
&= \mathrm{A'B'C' + AB'C' + AB'C' + AB'C + ABC' + ABC \:(rule\: 5)}\\
&= \mathrm{(A+A')\: B'C' + (AB' + AB)(C+C') \:(rule\: 13)}\\
&= \mathrm{(1)\: (B'C') + (AB' + AB)\: (1) \:(rule\: 7)}\\
&= \mathrm{B'C' + AB'+ AB \:(rule\: 4)}\\
&= \mathrm{(B'C') + A(B'+B) \:(rule\: 13)}\\
&= \mathrm{(B'C') + A(1) \:(rule\: 7)}\\
&= \mathrm{(B'C') + A \:(rule\: 4)}
\end{aligned} \nonumber \]
\(\PageIndex{4}\) 4-Variable Karnaugh Maps
While K-maps larger than 4 variables exist, they require more than 2 dimensions and are thus hard to solve by hand, though there are algorithmic ways to do this and there are many programs online that can solve them. This text is only interested in presenting the concept of K-maps and how they are solved, so it will end with presenting 4-Variable K-maps.
4-Variable K-maps correspond to Boolean functions of the form f(A, B, C, D). The K-maps again allow a truth table to be mapped so that rows and columns that differ by 1 or 2 values are placed next to each other. To do this, the Gray Codes that were introduced earlier are used. Note how the values for variables A,B and C,D are numbered as Gray Codes in the 3-variable K-map table.
|
AB/CD |
00 |
01 |
11 |
10 |
|
00 |
A'B'C'D’ |
A'B'C’D |
A'B’CD |
A'B’CD’ |
|
01 |
A’BC’D’ |
A’BC’D |
A’BCD |
A'BC'D’ |
|
11 |
ABC’D’ |
ABC’D |
ABCD |
ABCD’ |
|
10 |
AB’C’D’ |
AB’C’D |
AB’CD |
AB’CD’ |
Note that once again this number has resulted in regions in the K-map where the variables differ by 1 digit, as shown below. Note that the regions B' and D’ wrap around the table.
To use the K-map to solve 3 variable functions, once again groupings of 2n are found, which for a 4-Variable K-map are 16., 8, 4, 2, and 1. The larger the grouping, the fewer the terms, so groupings of 16 are chosen over groupings of 8, groupings of 8 are chosen over groupings of 4, groupings of 4 are chosen over groupings of 2, and groupings of 2 are chosen over groupings of 1.
The following is an example of how to use a K-map to solve a Boolean expression. Consider a function f(A,B,C) has the following truth table:
|
Input |
f(A,B,C) |
|||
|
A |
B |
C |
D |
AND |
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 1 | 0 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
This expression can be represented as the following sum of products.
f(A,B,C) = Σ(0, 4, 5, 6, 7, 8, 12, 13, 14, 15)
The minimum function for this K-map consists of one group of 8 and one group of 4, and corresponds to the equation f(A,B,C) = B + C’D’. Note the cells A’BC'D’ and ABC’D’ are used in both equations, which is rule 5 from the Boolean relationship table, X+X = X, and means that any term in the summation can be used more than once in minimizing the circuit.
To show that the final equation corresponds to the initial truth table, Boolean algebra can be used. The derivation of the final equation from the DNF is left as an exercise.
\(\PageIndex{5}\) Don’t care conditions
Sometimes when specifying an equation there are a number of situations where the input is not used. If the input is not used, then any value (0 or 1) can be used, and these are called don’t care conditions. For example, consider a 7-segment display which is used for many time clocks for sporting events. The display consists of 7 segments that are used to display the 10 decimal numbers 0..9. A 7-segment display along with the names for each segment (A..G) is shown below.
Each digit 0-9 will light 1 or more segments to create the number. For example the digit 0 would light segments A,B,C,D,E,F; the number 1 would light segments B,C; the number 2 would light segments A,B,D,E,G; etc. Therefore, there will be 7 Boolean functions, one for each segment.
Next, knowing that 10 digits can be represented using a minimum of 4 bits, a truth table can be created where the input 4 digits represent the decimal number, and a truth table developed for each of the 7 segments making up the number. When doing this, note that input values for the truth table must always be between 0-9, so there are 6 values (10-15) that are not used, so those rows in the table are never accessed. The values for the segments for those rows are don’t cares because they are never used; the component does not use those values, so it does not care how they are set. This gives the result for the 7-segment display truth table, where X=don’t care, which is shown below.
|
Input |
Output |
||||||||||
| A | B | C | D | A | B | C | D | E | F | G | |
| 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | |
| 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | |
| 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | |
| 0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | |
| 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | |
| 1 | 0 | 1 | 0 | X | X | X | X | X | X | X | |
| 1 | 0 | 1 | 1 | X | X | X | X | X | X | X | |
| 1 | 1 | 0 | 0 | X | X | X | X | X | X | X | |
| 1 | 1 | 0 | 1 | X | X | X | X | X | X | X | |
| 1 | 1 | 1 | 0 | X | X | X | X | X | X | X | |
| 1 | 1 | 1 | 1 | X | X | X | X | X | X | X |
The K-map for each segment now can be evaluated to give the corresponding minimum Boolean expression. The don’t cares (Xs) in the map are important because we can assume they are 1 when they help us minimize an expression, and assume they are 0 otherwise. In short, we can use them to create larger groupings, but they do not have to be used.
The K-map for segment A is the following:
The result is two groups of 8 (in red and purple) corresponding to A and B, and two groups of 4, one (in black) corresponding to BD, and one (in yellow, crossing the 4 corners of the map) corresponding to B'C', resulting in the following equation for segment A,
fA(A,B,C,D) = A + C + BD + B'D'