Karnaugh Map Solver

A truth table is a complete description of a logic function and a poor place to think about one. Sixteen rows for four inputs, sixty-four for six, each row an island. The rows that belong together, the ones that could be covered by a single simpler condition, sit far apart, because counting in binary scatters them.

Maurice Karnaugh’s answer, published in 1953 in a paper titled The Map Method for Synthesis of Combinational Logic Circuits, was to fold the table. It refined a chart that Edward Veitch had presented in 1952, and that chart in turn rediscovered a logical diagram drawn by Allan Marquand in 1881. What survived under Karnaugh’s name is one decision about order, and almost everything useful about the map follows from it.

The fold that makes neighbours mean something

On a Karnaugh map the row and column labels do not count 00, 01, 10, 11. They run 00, 01, 11, 10. That sequence is a Gray code, an ordering of binary numbers in which only one bit changes from each entry to the next. The name honours Frank Gray, a Bell Labs researcher whose patent on the code, applied for in 1947, was granted in 1953; George Stibitz had described such a code in a patent application of 1941, and the NIST dictionary traces one back to a telegraph shown by Emile Baudot in 1878.

The consequence is geometric. Step from any cell to the one beside it and exactly one input variable changes. Two neighbouring ones are therefore two input combinations that agree on everything except one variable, and a function that is true for both does not depend on that variable there. The pair collapses into one product term with one literal fewer.

Do it again and a block of four loses two literals, a block of eight loses three. That is why groups must be rectangles whose area is a power of two. A rectangle of that size is a set of inputs that fixes some variables and lets the rest run through every combination. Any other shape would be a claim that cannot be written as a single product.

The fold has no real edges. The last label, 10, differs from the first, 00, in one bit, so the right column is a neighbour of the left and the bottom row of the top. The map is a torus drawn flat. The four corner cells of a four-variable map form a perfectly good group of four, which on paper looks like four separate squares and is the single hardest thing for a beginner to see.

Lay the columns out in ordinary counting order and the whole device stops working. Moving from 01 to 10 changes two variables at once, so cells that touch are no longer related, and a rectangle no longer means anything. The map is the Gray code and little else.

Prime implicants, and the ones that have no rival

The vocabulary comes from the logician W. V. Quine, whose 1952 article The Problem of Simplifying Truth Functions set the question out. A product term is an implicant of a function if the function is true whenever the term is. A prime implicant is an implicant that cannot be made more general: remove any one of its literals and it starts claiming inputs where the function is false. On the map, a prime implicant is a rectangle that cannot be doubled in any direction.

Some prime implicants are forced. If a one is covered by only a single prime implicant, that implicant has to appear in every solution built from primes, and it is called essential. The rest is a choice among overlapping rectangles, and the choice is where the difficulty lives.

Take a function of A, B, C and D that is 1 at cells 4, 8, 10, 11, 12 and 15, numbering the cells with A as the high bit, and that may be anything at cells 9 and 14. It has exactly 4 prime implicants.

The pair at cells 4 and 12 is the term BC’D’. Three blocks of four give AB’, AD’ and AC. Cell 4 is reached only by the first and cell 15 only by the last, so those two are essential. They leave cell 8 uncovered, and either AB’ or AD’ will finish the job. The result is two equally good answers of three terms: BC’D’ + AB’ + AC, or the same with AD’ in the middle.

Edward McCluskey’s 1956 paper, Minimization of Boolean Functions, turned the search for prime implicants into bookkeeping. List the minterms, combine every two that differ in one position, combine the results again, and whatever never combines is prime. Then draw a chart of primes against minterms and choose rows until every column is ticked. The method is described as functionally identical to Karnaugh mapping. The map is the same procedure done by eye, and the table is the same picture done by a clerk who cannot be fooled by a wrapped edge.

That equivalence cuts both ways. Karnaugh’s map trades on the human gift for pattern recognition, which is quick and unreliable. Past four variables the picture becomes a stack of layers, and neighbours sit above and below as well as beside. The tabular form does not care how many variables there are. It also gives a definite way to check that a minimum has been reached, which is something a pair of eyes cannot offer.

Don’t-cares are freedom, and freedom is where the work is

Real specifications are rarely complete. A circuit that reads a decimal digit in binary-coded form will never be shown the bit patterns for ten through fifteen. The designer does not care what the output is for those inputs, and can let each one be 0 or 1, whichever helps. On the map a don’t-care, usually written as a dash or an X, may be swept into a group to make it larger or left out entirely.

The gain can be large. For the lower left bar of a seven-segment digit, treating the six impossible inputs as don’t-cares lets the logic shrink to two terms of two literals each. The price is that the circuit now does something arbitrary on inputs it was promised it would never see, a promise worth writing down.

Choosing the cover is the hard part, and it is hard in a precise sense. The second step of the tabular method is an instance of the set cover problem, and the minimisation problem as a whole is NP-complete. The number of prime implicants can grow as fast as three to the power n divided by the square root of n. Six variables already allow 92 of them, against 13 for four. Stanley Petrick described in 1956 a way to obtain every minimum solution by multiplying out a product of sums over the chart, tedious by hand and straightforward for a machine.

A search can reach the same answer by another road. Branch and bound keeps the best cover found so far and abandons any partial choice that cannot beat it. When such a search runs to its end, its answer is proved. When it is cut short, its answer is merely a cover that works. For four variables there is no excuse for leaving the matter open: there are only 65,536 functions, and each one can be solved outright and compared with a brute-force search.

What minimal does not promise

Minimal needs a criterion, and the usual one is fewest terms, then fewest literals. It is a statement about two-level forms only: one layer of AND gates feeding one OR gate, or the mirror image built from the zeros. Within that frame the answer is exact. Outside it, the word says nothing.

Parity shows the gap. A function that is 1 when an odd number of its inputs are 1 puts its ones on the map like the dark squares of a chessboard. No two are neighbours, so nothing can be grouped. With four inputs that means 8 terms of four literals each, and in general two to the power n minus one terms. Three XOR gates in a row compute the same thing. Multi-level circuits, which factor and share, are a different and harder optimisation problem, and practical tools for large designs use heuristics that do not promise the optimum.

A minimum cover can also leave a fault behind that no truth table will ever show. Take AB + A’C. With B and C both 1 the output should stay at 1 while A changes, but one AND gate is switching off as the other switches on. Real gates are never perfectly matched, and the output can dip to 0 for an instant. This is a static hazard. On the map it is visible as two neighbouring ones that belong to different groups.

The cure, a result credited to David Huffman, is to add the term BC, which bridges the two cells and holds the output up during the change. Algebraically BC is redundant: the consensus theorem says the function is the same with or without it. A minimiser, asked for the fewest terms, will always throw it away.

So the most economical expression and the most trustworthy circuit can be different things. In clocked designs the dip is usually harmless, because outputs are captured in a register after they settle. Where an output drives something directly, the redundant term earns its place.

The map is still worth learning for what it makes obvious. Simplifying logic is a question about which inputs can be told apart by one variable.

The cheapest answer depends on what is being counted. And a result is only as good as the proof that nothing smaller exists.