Karnaugh Maps

It may be necessary to read the section on Boolean Algebra in order to understand some of the notation used within this article.

A Karnaugh Map makes simplification of truth tables into functions much easier, but it is quite an involved concept to learn. You get all the minterms, and draw a rectangle around them using the fewest rectangles possible that include all the selected minterms. A rectangle must have 2^N minterms within it (so 1,2,4,8,16 etc.) The size of Karnaugh map depends on the number of variables dealt with.

In order to begin teaching the concepts behind Karnaugh maps, I will start with a 2x1 grid. This would not actually be used, but gives an example of how Karnaugh Maps work. I will use the example of an inverter. If a 1 is put in, a 0 is given out. If a 0 is put in, a 1 is given out. I will use the term xn to describe the letter x followed by a number. xn would normally be replaced by a 0, a 1 or a don't care term, represented by a - as is shown in examples 2.1 and 2.2 below. As you can see, everything below the the A is the value for when A = 1. Everything which doesn't have an A above is the value for when A = 0. This may not make much sense yet, but should start to when we deal with larger maps.

Example 1.1  Truth Table for 2x1 Karnaugh Map  Input  | Output

|

A  | X
0  | X0
1  | X1
Example 1.2  2x1 Karnaugh Map  | A

|

x0  | x1

For the invertor example, this would have the values

Example 2.1  Truth Table for 2x1 Karnaugh Map  Input  | Output

|

A  | X
0  | 1
1  | 0
Example 2.2  2x1 Karnaugh Map  | A

|

1  | 0

Below, I've shown how the output(X) of the truth table (normally 0s or 1s) are mapped onto a 4x4 karnaugh map.

Example 3.1  Truth Table for 4x4 Karnaugh Map  Inputs  | Output

|

A  | B  | C  | D  | X
0  | 0  | 0  | 0  | X0
0  | 0  | 0  | 1  | X1
0  | 0  | 1  | 0  | X2
0  | 0  | 1  | 1  | X3
0  | 1  | 0  | 0  | X4
0  | 1  | 0  | 1  | X5
0  | 1  | 1  | 0  | X6
0  | 1  | 1  | 1  | X7
1  | 0  | 0  | 0  | X8
1  | 0  | 0  | 1  | X9
1  | 0  | 1  | 0  | X10
1  | 0  | 1  | 1  | X11
1  | 1  | 0  | 0  | X12
1  | 1  | 0  | 1  | X13
1  | 1  | 1  | 0  | X14
1  | 1  | 1  | 1  | X15
Example 3.2  4x4 Karnaugh Map  |  |  | A  |

|
|
|
|

|  |  |  | B
|  | x0  | x1  | x3  | x2
C  |  | x4  | x5  | x7  | x6
D  | x12  | x13  | x15  | x14
| x8  | x9  | x11  | x10

In use, each occurrence of X and a number (Xn) would be replaced with a 0, 1 or - (don't care) term.

The letters at the top and sides show where each of the input variables (A,B,C and D) equal 1. For the Karnaugh map to be translated into a function, it is necessary to group similar terms. An example of this is shown below. The function ( ¬ {\displaystyle \lnot } A ∧ {\displaystyle \land } ¬ {\displaystyle \lnot } B ∧ {\displaystyle \land } C ∧ {\displaystyle \land } D) ∨ {\displaystyle \lor } ( ¬ {\displaystyle \lnot } A ∧ {\displaystyle \land } B ∧ {\displaystyle \land } C ∧ {\displaystyle \land } D) ∨ {\displaystyle \lor } (A ∧ {\displaystyle \land } ¬ {\displaystyle \lnot } B ∧ {\displaystyle \land } C ∧ {\displaystyle \land } D) ∨ {\displaystyle \lor } (A ∧ {\displaystyle \land } B ∧ {\displaystyle \land } C ∧ {\displaystyle \land } D) is mapped below. It can be seen that are equal to 1 are shaded. All the shaded cells fall into both C and D. Therefore, the simplified function is C ∧ {\displaystyle \land } D. Don't care terms can be assigned to either a 1 or a 0 depending on which leads to a more simplified solution.

Truth Table for 4x4 Karnaugh Map  Inputs  | Output

|

A  | B  | C  | D  | X
0  | 0  | 0  | 0  | 0
0  | 0  | 0  | 1  | 0
0  | 0  | 1  | 0  | 0
0  | 0  | 1  | 1  | 0
0  | 1  | 0  | 0  | 0
0  | 1  | 0  | 1  | 0
0  | 1  | 1  | 0  | 0
0  | 1  | 1  | 1  | 0
1  | 0  | 0  | 0  | 0
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
4x4 Karnaugh Map  |  |  | A  |

|
|
|
|

|  |  |  | B
|  | 0  | 0  | 0  | 0
C  |  | 0  | 0  | 0  | 0
D  | 1  | 1  | 1  | 1
| 0  | 0  | 0  | 0