Karnaugh map

The Karnaugh map (K-map for short) was invented in 1950 by Maurice Karnaugh, a telecommunications engineer at Bell Labs. It is a very useful tool to facilitate Boolean algebraic expressions. Normally, extensive calculations are required to obtain the minimal expression of a Boolean function, but one can use a Karnaugh map instead. Karnaugh maps make use of the human brain's excellent pattern-matching capability to decide which terms should be combined to get the simplest expression.

A Karnaugh map is an excellent aid for simplification of up to six variables, but with more variables it becomes hard even for our brain to discern optimal patterns. For expressions having more than 4 variables, the Quine-McCluskey algorithm, also called the method of prime implicants, should be used. This algorithm uses a deterministic approach to simplification of boolean expressions. Thus, following the steps of the algorithm ensures that the simplest expression can be found. This is especially useful for creating software programs that simplify any given boolean expression.

Karnaugh maps also help teach about Boolean functions and minimization.

Example

Consider the following function:

f(A, B, C, D) = E(4, 8, 9, 10, 11, 12, 14, 15)

This function has this truth table:

A B C D f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 1 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 1.

The input variables can be combined in 16 different ways, so our Karnaugh map has to have 16 positions. The most convenient way to arrange this is in a 4x4 grid.

The binary digits in the map represent the function's output for any given combination of inputs. We write 0 in the upper leftmost corner of the map because f = 0 when A = 0, B = 0, C = 1, D = 0. Similarly we mark the bottom right corner as 1 because A = 1, B = 0, C = 0, D = 0 gives f = 1.

After the Karnaugh map has been constructed our next task is to find the minimal terms to use in the final expression. These terms are found by encircling the 1's in the map. The encirclings can only encompass 2ⁿ fields, where n is an integer ≥ 0 (1, 2, 4, 8...). They should be as large as possible. The optimal encirclings in this map are marked by the green, red and blue lines.

For each of these encirclings we find those variables that have the same state in each of the fields in the encircling. For the first encircling (the red one) we find that:

The variable A maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
Variable B does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
Similarly D changes but C does not.

The first term becomes AC.

For the green encircling we see that A and B maintains the same state, C and D changes. But B is 0 and has to be negated before it can be included.

The second term becomes AB'.

By working the blue encircling the same way we find the term BC'D' and our final expression for the function is ready: AC + AB' + BC'D'.

The inverse of a function is solved in the same way by encircling the 0's instead.

It is worth mentioning is that the number of product terms for an encircling P is:

P = 2log(n/x)

where n is the number of variables in the Karnaugh map and x the number of fields encircled.

References

Maurice Karnaugh, The Map Method for Synthesis of Combinational Logic Circuits, Trans. AIEE. pt I, 72(9):593-599, November 1953.