What a K-map shows

A Karnaugh map redraws a truth table so cells differing in exactly one variable sit next to each other.

That adjacency is the visual form of x·a + x·a′ = x. Two neighbouring 1s let one variable cancel, so grouping neighbours is simplification.

Row and column labels use Gray code (00, 01, 11, 10). Consecutive labels differ by one bit.

Edges wrap around. The left and right columns are neighbours, and so are the top and bottom rows.

A four-variable example

Let f(a,b,c,d) be 1 for minterms 0, 2, 5, 7, 8, 10, 13 and 15.

Here is the map, with rows labelled by ab and columns by cd:

Follow the outlines rather than the visual distance between cells. The corner group wraps in both directions; neither arrow makes diagonal cells adjacent. It is a two-by-two rectangle across the map's edges.

• The four corners (minterms 0, 2, 8, 10) are all adjacent because the map wraps. Inside the group b = 0 and d = 0 stay fixed while a and c change, so the group is b′d′.

• The centre block (5, 7, 13, 15) has b = 1 and d = 1 fixed: bd.

Keep fixed variables; cancel changing variables

This is not arbitrary deletion. Each rectangle contains every combination of the changing variables. For A, factor the four minterms:

For B the same cancellation leaves the uncomplemented fixed variables:

So f = b′d′ + bd, which is simply XNOR of b and d. Eight 4-input minterms became two 2-literal terms, and a and c turned out not to matter at all.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

module kmap_check;
  logic a, b, c, d;
  logic f_minterms, f_min;

  always_comb begin
    case ({a, b, c, d})
      4'd0, 4'd2, 4'd5, 4'd7, 4'd8, 4'd10, 4'd13, 4'd15: f_minterms = 1'b1;
      default:                                           f_minterms = 1'b0;
    endcase
    f_min = (~b & ~d) | (b & d);        // the K-map result
  end

  int errors = 0;
  initial begin
    for (int i = 0; i < 16; i++) begin
      {a, b, c, d} = i[3:0];
      #1;
      if (f_minterms !== f_min) begin
        $display("FAIL: mismatch at %0d", i);
        errors++;
      end
    end
    if (errors == 0) $display("PASS: K-map result verified for all 16 inputs");
    $finish;
  end
endmodule

Grouping rules

1. Groups contain only 1s (or don't-cares) and have size 1, 2, 4, 8 or 16: always a power of two.

2. Each group must be a rectangle, allowing edge wrapping, with power-of-two height and width. Its cells form a Boolean subcube: every combination of the changing variables is included. An L shape or diagonal is not a group, even if its cell count is a power of two.

3. Make groups as large as possible: a bigger group cancels more variables.

4. Cover every 1 at least once, using as few groups as possible. Overlap is allowed.

5. Edges wrap: treat the map as the surface of a torus.

A group of 2ᵏ cells removes k variables. The corner and centre groups above each have 4 = 2² cells, so each removed two variables.

Four cells are not necessarily a group

The next two maps show a different function, with ones only at minterms 0, 1, 4 and 12. First try enclosing all four ones. Then replace that invalid outline with legal, overlapping pairs.

OR the three terms to obtain a correct cover: f = a′b′c′ + a′c′d′ + bc′d′. Now minimize the cover: the solid pair already covers 0 and 1, and the dotted pair covers 4 and 12. The dashed pair adds no uncovered one, so its term is redundant. The minimal cover is f = a′b′c′ + bc′d′. A valid group need not be necessary; retain enough groups to cover every one, without covering any zero.

Don't-cares

Cells marked X are inputs that never occur. Treat each X as a 1 if that makes a bigger group, and as a 0 otherwise.

In the BCD “is even” example, inputs 10 to 15 are don't-cares. Including them lets the whole function collapse to ~d (the least significant bit is 0).

Try it: group the cells

The map starts on the four-variable example above (1s at minterms 0, 2, 5, 7, 8, 10, 13 and 15), so it shows the corner group b′d′ and the centre group bd. Click a cell to cycle it 0, 1, x; the tool keeps the fewest terms, then the fewest literals.

• Set cell 15 (ab = 11, cd = 11) to 0: the centre square breaks and f = a′bd + b′d′ + bc′d, three terms instead of two.

• Back on the starting map (press Reset), set cells 3, 9 and 11 to 1: f needs four terms. Now click cell 1 twice to make it x: it completes an eight-cell group and f = b′ + d.

• Set Inputs to 3 and make cells 3, 5, 6 and 7 equal to 1: the majority function, f = ab + ac + bc.

Where K-maps stop

• Practical up to 4 variables, awkward at 5, hopeless beyond 6. Real blocks have dozens of inputs.

• Synthesis tools use algorithms (Espresso-style two-level minimization and multi-level restructuring) that do the same job at scale and also consider shared logic and delay.

• The value of the K-map is intuition: you learn to see which inputs a function really depends on, which is what you need when reviewing or reducing RTL.

Related topics

• The identity toolkit — the algebra behind grouping

• Implementation trade-offs