# Karnaugh Maps

Jump to navigation Jump to search

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
 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
 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
 A B C D x0 x1 x3 x2 x4 x5 x7 x6 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 ($\lnot$ A$\land$ $\lnot$ B$\land$ C$\land$ D)$\lor$ ($\lnot$ A$\land$ B$\land$ C$\land$ D)$\lor$ (A$\land$ $\lnot$ B$\land$ C$\land$ D)$\lor$ (A$\land$ B$\land$ C$\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$\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
 A B C D 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0