Karnaugh maps

Two rows that share a reason

In the last lesson, rows 6 and 7 of a truth table were both 1, and both for the same reason: a and b were 1 and c did not matter. Their minterms, a·b·c̅ and a·b·c, differ only in c. ORed together they say "a and b, with c either way", which is just a·b. This is the one rule that every method in this stage relies on: two terms that differ in exactly one input merge into one term without that input. Finding such pairs in a truth table is hard, because the rows that differ in one bit are scattered. Row 3 (011) and row 4 (100) sit next to each other and differ in every bit; row 1 (001) and row 5 (101) differ in one bit and sit four lines apart.

Fold the table so neighbours touch

A Karnaugh map, named after Maurice Karnaugh who published it in 1953, is the truth table rearranged into a grid so that any two cells that are side by side differ in exactly one input. For two inputs that is a 2 by 2 grid: a picks the row, b picks the column. For three inputs the grid is 2 rows by 4 columns: a picks the row and the pair bc picks the column. The trick is the order of the column headings. Counting order would be 00, 01, 10, 11, but going from 01 to 10 changes both bits, so those two columns would not be neighbours. Instead the headings run 00, 01, 11, 10, where each step changes one bit.

Here is the two-input map. The cell numbers are the row numbers from the truth table. Click the cells: with two 1s side by side the widget draws a group and writes the term it stands for.

Circling groups

Once the 1s are on the map, minimising becomes pattern spotting. Draw a loop round any rectangle of 1s whose size is 1, 2 or 4 cells (or 8 or 16 on bigger maps: always a power of two). Each loop is one product term. To write it, look at the inputs: any input that has the same value in every cell of the loop stays in the term, plain if that value is 1 and barred if it is 0. Any input that changes inside the loop drops out. A loop of two drops one input, a loop of four drops two, so bigger loops give shorter terms. Then OR the terms of all the loops together.

The rules for the loops, all of which follow from that:

• Every 1 must be inside at least one loop, or the expression would miss a row.
• A loop may contain only 1s. One 0 inside it would make the term fire on a row that should be 0.
• Loops may overlap. Using a 1 twice costs nothing, and it often lets both loops be bigger.
• Make each loop as big as you can, and use as few loops as you can.
• The map wraps: the left column is next to the right column, because 00 and 10 differ in one bit.

The map below starts with that function. Click cells to add and remove 1s and watch the loops move.

Reading the result

The expression from a map is a sum of products, the same shape as the canonical one from the last lesson, but with fewer and shorter terms. Each loop is one AND gate, or no gate at all if only one input is left, and one OR gate collects them. The Karnaugh map solver on this site draws the loops for up to six inputs, and the widget above uses the same engine, so its loops are the solver's loops.

What to remember

• Two terms that differ in exactly one input merge into one term without that input.
• A Karnaugh map is the truth table laid out with headings in Gray order, so neighbouring cells differ in one bit.
• Loop rectangles of 1s of size 1, 2, 4 or 8; each loop is one term, and inputs that change inside it drop out.
• Bigger loops mean shorter terms; overlapping is free; the map wraps round its edges.
• OR the terms of the loops together for the minimal sum of products.