Welcome to Math Mutation, the podcast where we discuss fun, interesting, or weird corners of mathematics that you would not have heard in school. Recording from our headquarters in the suburbs of Wichita, Kansas, this is Erik Seligman, your host. And now, on to the math.
I was surprised to read about the recent passing of Maurice Karnaugh, a pioneering mathematician and engineer from the early days of computing. Karnaugh originally earned his PhD from Yale, and went on to a distinguished career at Bell Labs and IBM, also becoming an IEEE Fellow in 1976. My surprise came from the fact that he was still alive so recently: he was born in 1924, and his key contributions were in the 1950s and 1960s, so I had assumed he died years ago. In any case, to honor his memory, I thought it might be fun to look at one of his key contributions: the Karnaugh Map, known to generations of engineering students as the K-map for short.
So, what is a K-map? Basically, it’s a way of depicting the definition of a Boolean function, that is a function that takes a bunch of inputs and generates an output, with all inputs and the output being a Boolean value, that is either 0 or 1. As you probably know, such functions are fundamental to the design of computer chips and related devices. When trying to design an electronic circuit schematic that implements such a function, you usually want to try to find a minimum set of basic logic gates, primarily AND, OR, and NOT gates, that defines it.
For example, suppose you have a function that takes 4 inputs, A, B, C, and D, and outputs a 1 only if both A and B are true, or both C and D are true. You can basically implement this with 3 gates: (A AND B) , (C AND D), and an OR gate to look at those two results, outputting a 1 if either succeeded. But often when defining such a function, you’re initially given a truth table, a table that lists every possible combination of inputs and the resulting output. With 4 variables, the truth table would have 2^4, or 16, rows, 7 of which show an output of 1. A naive translation of such a truth table directly to a circuit would result in one or more gates for every row of the table, so by default you would generate a much larger circuit than necessary. The cool thing about a K-map is that even though it’s mathematically trivial— it actually just rewrites the 2^n lines of the truth table in a 2^(n/2) x 2^(n^2) square format— it makes a major difference in enabling humans to draw efficient schematics.
So how did Karnaugh help here? The key insight of the K-map is to define a different shape for the truth table, one that conveys the same information, but in a way that the human eye can easily find a near-minimal set of gates that would implement the desired circuit. First, we make the table two-dimensional, by grouping half the variables for the rows, and half for the columns. So there would be one row for AB = 00, one row for AB = 01, etc, and a column for CD=00, another for CD=01, etc. This doesn’t actually change the amount of information: for each row in the original truth table, there is now a (row, column) pair, leading to a corresponding entry in the two-dimensional K-map. Instead of 16 rows, we now have 4 rows and 4 columns, specifying the outputs for the same 16 input combinations.
The second clever trick is to order each set of rows and columns according to a Gray code— that is, an ordering such that each pair of inputs only differs from the previous pair in one bit. So rather than the conventional numerical ordering of 00, 01, 10, 11, corresponding to our ordinary base-10 of 0, 1, 2, 3 in order, we sort the rows as 00, 01, 11, 10. These are out of order, but the fact that only one bit is changing at a time makes the combinations more convenient to visually analyze.
One you have created this two-dimensional truth table with the gray code ordering, it has the very nice property that if you can spot rectangular patterns, they correspond to boolean expressions, or minterms, that enable an efficient representation of the function in terms of logic gates. In our example, we would see that the row for AB=11 contains a 4x1 rectangle of 1s, and the column of CD=11 contains a 1x4 rectangle of 1s, leading us directly to the (A AND B) OR (C AND D) solution. Of course, the details are a bit messy to convey in an audio podcast, but you can see more involved illustrations in online sources like the Wikipedia page in the show notes. But the most important point is that in this two-dimensional truth table, you can now generate a minimal-gate representation by spotting rectangles of 1s, greatly enhancing the efficiency of your circuit designs.
Over the years, as with many things in computer science, K-maps have faded in significance. This is because the power of our electronic design software has grown exponentially: these days, virtually nobody hand-draws a K-map to minimize a circuit. Circuit synthesis software directly looks at high-level definitions like truth tables, and does a much better job at coming up with minimal gate implementations than any person could do by hand. Some of the techniques used by this software relate to K-maps, but of course many more complex algorithms, most of which could not be effectively executed without a computer, have been developed in the intervening decades. Despite this, Karnaugh’s contribution was a critical enabler in the early days of computer chip design, and the K-map is still remembered by generations of mathematics and computer science students.
And this has been your math mutation for today.
References:
- https://en.wikipedia.org/wiki/Karnaugh_map
- https://en.wikipedia.org/wiki/Maurice_Karnaugh
- https://www.quora.com/What-is-the-practical-use-of-a-Karnaugh-map
- https://www.eetimes.com/karnaugh-maps-101/
