1.4.3 - Karnaugh maps

Putting truth-table results into Gray order

A Karnaugh map is a rearranged truth table: each cell represents one input combination and contains that combination's output.

For two inputs, put $A=0,1$ along the rows and $B=0,1$ along the columns. The four cells represent 00,01,10,11. For more inputs, combine variables in a row or column label, but use Gray order: $00,01,11,10$. Binary order $00,01,10,11$ would place 01 next to 10, changing both bits and breaking the grouping rule.

For three inputs, use rows $A=0,1$ and columns $BC=00,01,11,10$. For example, consider this truth table:

The corresponding map is:

Notice that the 010 row goes into the final column of the top row, while 011 goes into the preceding column. Copy by the input labels, not by blindly placing the original output sequence from left to right. Four inputs need a 4-by-4 map, usually $AB$ rows and $CD$ columns, both in Gray order. The cell $AB=10,CD=01$ represents $A=1,B=0,C=0,D=1$.

Turning groups of ones into terms

To obtain a sum-of-products expression, group output-1 cells and write one AND term for each group, then OR those terms together.

A valid group is a rectangular block of $1,2,4,8$ or another power-of-two number of cells. Every included cell must be 1. An L-shaped group or a group of three cells cannot cancel variables in the required way.

For each group, inspect every input variable. Keep a variable if it has the same value in every cell: write the ordinary variable if that value is 1, or its negation if that value is 0. Remove any variable that changes. A pair removes one variable; a four-cell group removes two; an eight-cell group removes three.

In the three-input map above, group the top-row ones in columns 01 and 11. Across those cells, $A=0$ and $C=1$ stay fixed while $B$ changes, giving $\neg A\land C$. Group the bottom-row ones in columns 11 and 10. Here $A=1,B=1$ stay fixed while $C$ changes, giving $A\land B$. Hence

The cancellation has an algebraic explanation. The top pair originally represents $(\neg A\land\neg B\land C)\lor(\neg A\land B\land C)$. Factoring gives $\neg A\land C\land(\neg B\lor B)$, which reduces to $\neg A\land C$. The map exposes exactly the complementary-variable pairing used in Boolean algebra.

Using wrapping and overlapping groups

Opposite edges of a Karnaugh map are adjacent because the last and first Gray labels also differ in one bit.