Karnaugh Map
A Karnaugh map is a pictorial representation of the evaluation of a sum of products Boolean algebra expression. A map for an expression of N variables is a rectangle containing 2N cells. There is one cell for each minterm that would occur in the expression's truth table. These maps are used to manually simplify expressions.
The following are the Karnaugh maps, with cells marked with the corresponding minterms, for two, three, and four variables:
When we compare each cell with its immediate neighbours, we see that the corresponding minterms differ in only one variable: one cell will have the variable negated, the other will not. It is the case than the map's sides wrap around. That is to say, the top row is connected to the bottom row, and the leftmost column is connected to the rightmost column. To give some examples, in the Karnaugh map for four variables, the corner minterms m0 and m2 are neighbours with each other, as are the minterms m1 and m9, and the same can be said of minterms m14 and m12.
Simplification Procedure
The easiest way to simplify an expression with a Karnaugh map is to follow these steps:
- Build the expression's truth table.
- Starting with a blank Karnaugh map, take each row of the truth table where the output is
1and mark the corresponding minterm in the map with a1. - Form rectangular blocks of neighbouring cells where each cell contains a
1. The size of these blocks must be a power of two, e.g. one, two, four, eight, etc. Large blocks will give simpler final equations, so try to make the blocks as large as possible. - Find the equation for each block. Each block will have variables which remain constant and the block's equation is the
and'ing of these variables. Now build anorfunction with the block equations as arguments. You have created the sum or products simplified expression.
Example 1
The truth table for the half adder carry output Carry, with a column showing the minterms,
is as follows:
A |
B |
Carry |
minterm |
|---|---|---|---|
0 | 0 | 0 | m0 |
0 | 1 | 0 | m1 |
1 | 0 | 0 | m2 |
1 | 1 | 1 | m3 |
From this we see that only the minterm m3 leads to Carry being 1.
When we mark this minterm in a blank two by two Karnaugh map we get the following:
We then try to form the largest rectangular blocks we can of sizes one, two, or four. This is an easy example where only one rectangle comprising a single cell can be formed as shown below:
This gives us the equation Carry = A and B which is correct.
Example 2
Consider the truth table for some anonymous function of three input variables A, B, and C, and
output X, which is shown below with a column showing the minterm:
A |
B |
C |
X |
minterm |
|---|---|---|---|---|
0 |
0 |
0 |
0 |
m0 |
0 |
0 |
1 |
0 |
m1 |
0 |
1 |
0 |
0 |
m2 |
0 |
1 |
1 |
1 |
m3 |
1 |
0 |
0 |
0 |
m4 |
1 |
0 |
1 |
1 |
m5 |
1 |
1 |
0 |
1 |
m6 |
1 |
1 |
1 |
1 |
m7 |
From this we see that the minterms m3, m5, m6, and m7 lead to X being 1.
We take a blank two by four Karnaugh map and mark these minterms. This gives us the following:
We then try to form the largest rectangular blocks we can of sizes one, two, four, or eight. We see that we have three blocks shown below:
This gives us the equation X = (A and B) or (A and C) or (B and C) which is correct.
References
Mano, M. Morris, and Kime, Charles R. Logic and Computer Design Fundamentals. 2nd Edition. Prentice Hall, 2000.
Kleitz, W. Digital Microprocessor Fundamentals. 3rd Edition. Prentice Hall, 2000.