Karnaugh or K- maps are useful tool fot boolean function minimization, and for visualization of the boolean function. In brief,
Consider the boolean function
A | B | f | |
0 | 0 | 1 | m_{0} |
0 | 1 | 1 | m_{1} |
1 | 0 | 1 | m_{2} |
1 | 1 | 0 | m_{3} |
The K-map is shown in Figure 26. The essence of the K-map is the two dimensional representation of f, which is equivalent to the truth table but more visual.
To minimize f, we loop out logical adjacencies, Figure 26.
Therefore
Note. Looping out logical adjacencies is a graphical alternative to algebraic calculations.
Unit distance code (Gray code.) For two bits, the Gray code is:
00 | 01 | 11 | 10 |
The K-map method is to loop out groups of 2^{n} logically adjacent minterms. Each looped out group corresponds to a product term in a minimal SOP expression.
Example.
The K-map is shown in Figure 27.
Moving left to right or up to down in the K-map changes only one digit in the minterm code. Note the wrap-around at the ends: because of logical adjacency, the top and bottom are joined, and the left and right are joined.
Therefore the minimal SOP representation is
Example.
The K-map is shown in Figure 28.
Therefore the minimal SOP representation is
Don't cares. In some applications it doesn't matter what the output is for certain input values. These are called don't cares.
For instance, in the Binary Coded Decimal code, not all input values occur:
0 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 0 | 2 |
0 | 0 | 1 | 1 | 3 |
0 | 1 | 0 | 0 | 4 |
0 | 1 | 0 | 1 | 5 |
0 | 1 | 1 | 0 | 6 |
0 | 1 | 1 | 1 | 7 |
1 | 0 | 0 | 0 | 8 |
1 | 0 | 0 | 1 | 9 |
1 | 0 | 1 | 0 | 10 |
1 | 0 | 1 | 1 | 11 |
1 | 1 | 0 | 0 | 12 |
1 | 1 | 0 | 1 | 13 |
1 | 1 | 1 | 0 | 14 |
1 | 1 | 1 | 1 | 15 |
We shall use the symbols or X to denote don't cares.
Don't cares can be exploited to help minimize boolean functions.
Example.
The K-map is shown in Figure 29.
The minimal SOP representation is
Check out the web page kmap.html for more on kmaps and how they work.
ANU Engineering - ENGN3213