Karnaugh Maps

A Karnaugh map (K-map) is a truth table redrawn as a grid, arranged so that any two neighbouring cells differ in exactly one input variable. That arrangement turns Boolean simplification into a visual task: circle neighbouring 1s, and each circle becomes one simplified product term. For functions of up to four variables, a K-map finds the smallest sum-of-products expression in a minute, and every literal it removes is a gate input that never gets built.

18 min read | Beginner Level

What You'll Learn

• How a K-map is laid out, and why its rows and columns follow Gray-code order
• The grouping rules, and how to read a minimal SOP or POS expression from a map
• How don't-care conditions shrink logic, and how synthesis tools use them
• Why maps stop at about four variables, and what Quine-McCluskey and EDA tools do instead

Why a Map Works

Every K-map simplification is one Boolean law applied over and over:

XY + XY' = X(Y + Y') = X . 1 = X

Two product terms that differ in exactly one variable merge into one term,
and that variable disappears.

  A'B'C' + A'B'C  =  A'B'(C' + C)  =  A'B'

In a truth table, rows that differ in one variable are often far apart: row 3 (011) and row 7 (111) are four rows away. A K-map places them side by side, so mergeable terms become neighbouring cells. Each cell holds the output for one row of the truth table, and each cell is labelled with that row's minterm number.

Gray-Code Ordering and Wraparound

The row and column labels of a K-map are written in Gray code order, 00, 01, 11, 10, not in binary order. In Gray code, neighbouring labels differ in exactly one bit, which is what makes neighbouring cells mergeable. Binary order breaks this between 01 and 10, where two bits change at once.

The Gray sequence also wraps around: the last label, 10, differs from the first label, 00, in one bit. So the left and right edges of a K-map are neighbours, and so are the top and bottom edges. Picture the map rolled into a tube in both directions. That is why the four corner cells of a 4-variable map are all neighbours of each other.

2-, 3-, and 4-Variable Map Layouts

A map for n variables has 2ⁿ cells. The variables are split between rows and columns, and the cell numbers follow the variable order, with A as the most significant bit:

Notice how the cell numbers in the 4-variable map run 0, 1, 3, 2 across the top row, and rows run 0, 4, 12, 8 down the first column. Getting this order right when filling in the map is the most common source of K-map errors.

The Grouping Rules

A group is a set of cells that merges into one product term. Groups must follow four rules:

1. A group contains only 1s (and optionally don't-cares).
2. A group is a rectangle of 1, 2, 4, 8, or 16 cells: a power of two. Rectangles may wrap around the edges.
3. Make each group as large as possible. Groups may overlap.
4. Use as few groups as possible, while covering every 1 at least once.

The size of a group decides how many variables it eliminates. In a 4-variable map:

To read a group's term, look at each variable across the group's cells. A variable that stays 1 appears as itself, a variable that stays 0 appears complemented, and a variable that changes is dropped.

Worked Example: 3 Variables

Simplify F(A, B, C) = Σm(0, 1, 2), the function from the truth table above. It is 1 for rows 000, 001, and 010.

Group 1 (cells 0, 1):  A = 0, B = 0, C changes   ->  A'B'
Group 2 (cells 0, 2):  A = 0, C = 0, B changes   ->  A'C'    (wraps across the edge)

F = A'B' + A'C'

Check with algebra:
  F = A'B'C' + A'B'C + A'BC'
    = A'B'C' + A'B'C + A'B'C' + A'BC'     idempotent: duplicate cell 0, which both groups use
    = A'B'(C' + C) + A'C'(B' + B)
    = A'B' + A'C'

Cell 0 is used by both groups. Overlap is allowed and expected: in the algebra it is the same as writing a term twice, since X + X = X.

Worked Example: 4 Variables

Simplify F(A, B, C, D) = Σm(0, 2, 3, 5, 7, 8, 10, 11, 13, 15).

Corners (cells 0, 2, 8, 10):   B = 0, D = 0          ->  B'D'
Centre  (cells 5, 7, 13, 15):  B = 1, D = 1          ->  BD
Cells 3 and 11 are still uncovered. Two equal choices:
  cells 2, 3, 10, 11  (top and bottom rows wrap):  B = 0, C = 1  ->  B'C
  cells 3, 7, 11, 15  (the CD = 11 column):        C = 1, D = 1  ->  CD

F = B'D' + BD + B'C      or      F = B'D' + BD + CD      (both 6 literals)

A minimal expression is not always unique. Both answers are equally small; a designer or a tool simply picks one.

Prime and Essential Prime Implicants

Two terms give the grouping rules a precise meaning:

• A prime implicant is a group that cannot be made any larger. This map has four: B'D', BD, B'C, and CD.
• An essential prime implicant is the only prime implicant that covers some 1. B'D' is essential because nothing else covers cells 0 and 8; BD is essential because nothing else covers cells 5 and 13.

Reliable procedure for any map:
  1. Find all prime implicants (largest possible groups).
  2. Take every essential prime implicant.
  3. Cover any remaining 1s with as few extra prime implicants as possible.

Some functions have no essential prime implicants at all. In F(A, B, C) = Σm(0, 1, 2, 5, 6, 7), every 1 is covered by exactly two prime implicants, arranged in a ring. You must choose a starting group, and two different minimal answers result:

Reading a POS Expression: Grouping the 0s

The same map gives a product-of-sums (POS) expression. Group the 0s instead of the 1s; this gives an SOP for F'. Complementing with De Morgan's theorem turns it into a POS for F.

F = Sigma m(0, 1, 2), so the 0s are in cells 3, 4, 5, 6, 7

Group the 0s:   cells 4, 5, 6, 7  ->  A          cells 3, 7  ->  BC
                F' = A + BC
Complement:     F  = (A + BC)' = A' . (BC)' = A'(B' + C')

POS: F = A'(B' + C')     (3 literals, against 4 for the SOP A'B' + A'C')

Reading a sum term directly from a 0-group uses the opposite convention to a 1-group: a variable that stays 0 appears as itself, and a variable that stays 1 appears complemented.

Don't-Care Conditions

A don't-care, written X, is an output value that does not matter, because that input combination never occurs or because nothing uses the output then. In a map, each X can be treated as a 1 when that makes a group bigger, or as a 0 otherwise. Xs never need to be covered.

Example: a circuit takes a BCD digit (0 to 9) on inputs ABCD and outputs 1 when the digit is 5 or more. Codes 10 to 15 never occur in BCD, so they are don't-cares.

Without don't-cares (Xs treated as 0):
  F = AB'C' + A'BD + A'BC             3 terms, 9 literals

With don't-cares:
  rows AB = 11 and 10 (cells 8-15)  ->  A
  cells 5, 7, 13, 15                ->  BD
  cells 6, 7, 14, 15                ->  BC
  F = A + BD + BC                     3 terms, 5 literals

Factored further: F = A + B(C + D)    3 gates

How synthesis tools use don't-cares: a tool receives don't-cares in several ways: input combinations that the designer declares impossible, unused state encodings in a state machine (5 states coded in 3 bits leave 3 unused codes), and outputs that are not observed under some conditions. The tool assigns each don't-care whatever value gives the smallest or fastest logic, exactly as in the map above. The catch is that the hardware's behaviour for those inputs is whatever the tool chose. If an "impossible" input can actually occur, for example after a bit flip or a reset glitch, the circuit's response is unplanned.

Patterns a K-Map Cannot Simplify

Some functions resist grouping completely. The 4-input XOR (odd parity) is 1 when an odd number of inputs are 1, which makes a checkerboard on the map: no two 1s are neighbours.

The minimal SOP is all 8 minterms, 32 literals in total. But the function is just A ⊕ B ⊕ C ⊕ D: three 2-input XOR gates. A checkerboard, or a partial checkerboard, is the signature of an XOR or XNOR function. K-maps only find the best two-level AND-OR form; XOR structures and multi-level factoring are outside what they can see. Synthesis tools recognize XOR patterns and map them to XOR/XNOR library cells.

Five Variables and Beyond

A 5-variable map is drawn as two 4-variable maps, one for A = 0 and one for A = 1. Cells in the same position in the two maps are neighbours, as if the maps were stacked on top of each other. A group that appears in the same place in both maps loses the variable A.

In this example, the centre block appears in both maps, so it becomes CE with A eliminated, while the pair in cells 0 and 2 exists only in the A = 0 map and keeps A': F = CE + A'B'C'E'.

Six variables need four 4-variable maps, stacked in two directions, and spotting groups across them becomes unreliable. Beyond that, maps are impractical. Two systematic approaches take over:

• Quine-McCluskey is a tabular method that does exactly what a K-map does, step by step: it finds all prime implicants by repeatedly merging terms that differ in one bit, then selects a minimal cover. It is exact and easy to program.
• Heuristic minimizers, such as the Espresso algorithm, are what logic synthesis actually uses. The number of prime implicants can grow exponentially with the number of variables, so exact methods become too slow for real logic cones with dozens of inputs. Heuristic methods find a near-minimal cover quickly.

Quine-McCluskey on F = Sigma m(0, 1, 2, 5, 6, 7)

Step 1  Sort minterms by number of 1s
          0 ones: 0 (000)
          1 one : 1 (001), 2 (010)
          2 ones: 5 (101), 6 (110)
          3 ones: 7 (111)

Step 2  Merge pairs in neighbouring groups that differ in one bit (- marks the dropped bit)
          0,1 -> 00-     0,2 -> 0-0
          1,5 -> -01     2,6 -> -10
          5,7 -> 1-1     6,7 -> 11-

Step 3  Try to merge again: no two terms have the same dashes and differ in one bit.
        Prime implicants: A'B', A'C', B'C, BC', AC, AB

Step 4  Prime implicant chart: every minterm is covered by exactly two primes,
        so there are no essential primes. Pick one, then cover the rest:
          A'B' + BC' + AC      or      A'C' + B'C + AB

Real synthesis goes further than two-level minimization. After finding a small SOP, tools factor it into multiple levels (as in A + B(C + D) above), share common sub-expressions between outputs, and map the result to library cells such as NAND, NOR, AOI, OAI, and XOR, guided by timing. K-maps teach the core idea, merging terms that differ in one variable, that all of these methods rely on.

Common Mistakes

1.            CD=00  CD=01  CD=11  CD=10
   AB=00        1      0      1      1       cells 0, 1, 3, 2
   AB=01        0      1      1      1       cells 4, 5, 7, 6
   AB=11        X      X      X      X       cells 12, 13, 15, 14
   AB=10        1      1      X      X       cells 8, 9, 11, 10

2. Groups:
     rows 11 and 10 (cells 8-15)           -> A
     columns 11 and 10 (cells 2,3,6,7,...) -> C
     centre block (cells 5, 7, 13, 15)     -> BD
     four corners (cells 0, 2, 8, 10)      -> B'D'
   a = A + C + BD + B'D'                     4 terms, 6 literals

3. Without don't-cares:
   a = A'C + A'BD + AB'C' + A'B'D'           4 terms, 11 literals
   (A'C + A'BD + AB'C' + B'C'D' is an equally small alternative)

   The don't-cares remove 5 literals. Note that BD + B'D' is B XNOR D,
   so a = A + C + (B XNOR D) with an XNOR cell.