Introduction

Karnaugh maps provide an alternative technique for representing Boolean functions. For example, consider the Karnaugh map for a 2-input AND gate (Figure 1).

Figure 1: Karnaugh map for a 2-input AND gate.

The Karnaugh map comprises a box for every line in the truth table; the binary values above the boxes are those associated with the a and b inputs. Unlike a truth table, in which the input values typically follow a standard binary sequence (00, 01, 10, 11), the Karnaugh map's input values must be ordered such that the values for adjacent columns vary by only a single bit, for example, 00, 01, 11, and 10. This ordering is known as a gray code, and it is a key factor in the way in which Karnaugh maps work.

The y column in the truth table shows all the 0 and 1 values associated with the gate's output. Similarly, all of the output values could be entered into the Karnaugh map. However, for reasons of clarity, it is common for only a single set of values to be used, typically the 1s.

Similar maps can be constructed for 3-input and 4-input functions (Figure 2). In the case of a 4-input map, the values associated with the c and d inputs must also be ordered as a gray code; that is, ordered in such a way that the values for adjacent rows vary by only a single bit.

Figure 2: Karnaugh maps for 3-input and 4-input functions.