In 1953, the American physicist Maurice Karnaugh invented a form of logic diagram called a Karnaugh map, which provides a graphical technique for representing Boolean functions. In this, the first installment of a two-part mini-series, we introduce Karnaugh Maps and demonstrate how they can be used to minimize logic functions.

The Tree of Porphyry
Diagrams used to represent logical concepts have been around in one form or another for a very long time. For example, Aristotle (384-322 BC) was certainly familiar with the idea of using a stylized tree figure to represent the relationships between (and successive sub-divisions of) such things as different species. Diagrams of this type, which are known as the Tree of Porphyry, are often to be found in medieval pictures. (See also the associated paper on Logic Diagrams and Machines.)

John Venn and his Venn Diagrams
In 1890, in a paper titled "On the Diagrammatic and Mechanical Representation of Propositions and Reasonings," which appeared in the Philosophical Magazine and Journal of Science, the English logician John Venn (1834-1923) proposed a graphical technique to show logical relationships between groups of "things". Venn was heavily influenced by the work of the English mathematician George Boole, and his Venn diagrams very much complemented Boolean Algebra.

Maurice Karnaugh and Kaunaugh Maps
Venn diagrams were strongly based on the interrelationships between overlapping circles or ellipses. Later offerings by folks such as Allan Marquand (1853-1924), a lecturer in logic and ethics at John Hopkins University, and the Reverend Charles Lutwidge Dodgson (1832-1898) were based on squares and rectangles.

In 1953, the American physicist Maurice Karnaugh (pronounced “car-no”, 1924-) invented a form of logic diagram called a Karnaugh map, which provides an alternative technique for representing Boolean functions; for example, consider the Karnaugh map for a 2-input AND function (Figure 1-1).

Figure 1-1. Karnaugh map for a 2-input AND function.

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 binary sequence, 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 with regard to the way in which Karnaugh maps work (see also the corresponding articles on Gray Codes.)

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’s boxes. For reasons of clarity, however, 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. 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, they must be ordered in such a way that the values for adjacent rows vary by only a single bit (Figure 1-2).

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

Minimization Using Karnaugh Maps
Karnaugh maps often prove useful in the simplification and minimization of Boolean functions. Consider an example 3-input function represented as a black box with an associated truth table as illustrated in Figure 1-3 (The values assigned to outputy in the truth table were selected randomly and have no significance beyond the purposes of this example).

Figure 1-3. Example 3-input function.

The equation extracted from the truth table in sum-of-products form contains four minterms, one for each of the 1s assigned to the output. [The concepts of minterms and maxterms are introduced in Chapter 9 of my book, Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) Edition 3]  Algebraic simplification techniques could be employed to minimize this equation, but this would necessitate every minterm being compared to each of the others, which can be somewhat time-consuming.

This is where Karnaugh maps leap onto the stage with a fanfare of trumpets. The 1s assigned to the Karnaugh map’s boxes represent the same minterms as the 1s in the truth table’s output column; however, as the input values associated with each row and column in the map differ by only one bit, any pair of horizontally or vertically adjacent boxes corresponds to minterms that differ by only a single variable. Such pairs of minterms can be grouped together and the variable that differs can be discarded, leaving a much-simplified equation (Figure 1-4).

Figure 1-4. Karnaugh map minimization of example 3-input function.

In the case of the horizontal group, input a is 0 for both boxes, input c is 1 for both boxes, and input b is 0 for one box and 1 for the other. Thus, for this group, changing the value on b does not affect the value of the output. This means that b is redundant and can be discarded this group. Similarly, in the case of the vertical group, input a is 1 for both boxes, input b is 0 for both boxes, and input c is 0 for one box and 1 for the other. Thus, input c is redundant for this group and can be discarded.

In Part 2 we will consider the grouping of minterms in more detail, along with the concepts of incompletely specified functions and populating Karnaugh maps using 0s versus 1s.

 
Author's Note: The material presented here was abstracted from my book Bebop to the Boolean Boogie (An Unconventional Guide to Electronics) 3rd Edition, with the kind permission of my publisher, Newnes (an imprint of Elsevier).