Karnaugh Maps for Two to Four Variables

Draw a Karnaugh map for up to four variables, group its 1s, and read the smallest sum of products from the groups.

You Will Be Able To

  • Fill a map whose rows and columns are in Gray order.
  • Draw groups of 1, 2, 4 or 8 cells, with wrap-around.
  • Read each group as one product term.
  • Tell a prime implicant from an essential one.
Lesson
G3.1
Time
30 min
Runs on
Your browser
Check
5 questions

A vending machine lights a lamp from four sensor bits. The first design used one AND gate for each row of the truth table that holds a 1. It worked, and it used eight wide gates where three small ones are enough.

DesignProduct termsLiterals
One term for each 1 of the table832
Read from the Karnaugh map37

Computed for f = Σm(0, 2, 4, 5, 6, 8, 10, 13). A literal is one variable in one term: one input of that term's AND gate.

A Truth Table Folded so That Neighbours Differ in One Bit

A Karnaugh map (K-map) is a truth table drawn as a grid. Each cell is one row of the table. The cell holds the output for that row.

Two variables: four cells
a / b01
0
1

b

Minimum SOP: 1 term · 1 literal.

Both cells of the column b = 1 hold a 1. In that column `a` takes both values, so f = b.

The labels are in Gray order: 00, 01, 11, 10. Each label differs from the next in one bit. So two cells that touch differ in one variable.

That is the whole trick. Two terms that differ in one variable merge: a'bc + abc = bc. On the map, such terms are neighbours.

Three variables: eight cells
ab / c01
00
01
11
10

c | a & b

Minimum SOP: 2 terms · 3 literals.

  1. A group of four. Every cell with c = 1 holds a 1. Inside the group, `a` and `b` change, so only `c` stays.
  2. A pair. The cell `abc = 110` is left. It pairs with 111, and that pair is the term `ab`.

f = Σm(1, 3, 5, 6, 7) = c + ab. Five terms with three literals each become two terms with three literals in all.

Groups of 1, 2, 4 and 8, with Wrap-Around

A group is a rectangle of 1s whose size is a power of two. Each time a group doubles, one more variable leaves the term.

Four variables: the lamp function
ab / cd00011110
00
01
11
10

~a & ~d | ~b & ~d | b & ~c & d

Minimum SOP: 3 terms · 7 literals.

  1. The four corners. The corners touch through both edges. They form one group of four: `b'd'`.
  2. The left and right columns. Columns `cd = 00` and `cd = 10` are neighbours. Their top two rows form a group of four: `a'd'`.
  3. A pair in the middle. Cells 0101 and 1101 are left. They sit in the same column and form a pair: `bc'd`.

f = Σm(0, 2, 4, 5, 6, 8, 10, 13). Rows are `ab` and columns are `cd`. Three groups cover all eight 1s.

  1. Rectangles only

    A group is 1, 2, 4 or 8 cells in a rectangle. A diagonal or an L shape is two groups.

  2. As large as possible

    A larger group is a shorter term. Grow each group until it would take in a 0.

  3. Edges wrap

    The map is a tube in both directions. The first and last row are neighbours, and so are the first and last column.

  4. Overlap is free

    A cell may sit in several groups. Reusing a 1 never changes the function.

Reading a Group as a Term

Look at each variable inside the group. If it changes, leave it out. If it stays 1, write it. If it stays 0, write its complement.

Group (rows abcd)abcdTerm
0000, 0010, 1000, 1010changesstays 0changesstays 0b'd'
0000, 0010, 0100, 0110stays 0changeschangesstays 0a'd'
0101, 1101changesstays 1stays 0stays 1bc'd

The three groups of the lamp function. Together: f = b'd' + a'd' + bc'd, which is 3 terms and 7 literals.

A group of two cells drops one variable. A group of four drops two. A group of eight drops three.

Implicants, Prime Implicants and Essential Primes

An implicant is any group that holds only 1s. A prime implicant is a group that cannot grow any more. An essential prime implicant is a prime that covers some 1 which no other prime covers.

All four prime implicants of the lamp function
ab / cd00011110
00
01
11
10

~a & ~d | ~b & ~d | b & ~c & d

Minimum SOP: 3 terms · 7 literals.

  1. Essential: the corners. Only `b'd'` covers the cells 1000 and 1010. So it must be in the answer.
  2. Essential: two more. Only `a'd'` covers 0110. Only `bc'd` covers 1101. Both are essential.
  3. Prime, but extra. The pair `a'bc'` cannot grow, so it is prime. Its two cells are already covered, so the answer leaves it out.

Four primes, three of them essential. The essential primes already cover every 1.

Prime implicantCellsEssential?
b'd'0, 2, 8, 10yes
bc'd5, 13yes
a'd'0, 2, 4, 6yes
a'bc'4, 5no: every cell is covered by another prime

Computed by the minimizer for the lamp function.

From a Truth Table to the Smallest Sum of ProductsArrows show the order of the work. Each box turns the result of the box before it into the next form.
  • Neutral
  • Structure
From a truth table to the smallest sum of productsArrows show the order of the work. Each box turns the result of the box before it into the next form. neutral Truth table one row per input neutral K-map rows in Gray order neutral Prime implicants largest groups neutral Essential primes the only cover of a 1 neutral Remaining 1s fewest extra groups neutral Sum of products one AND per group fillgroupmust havethen coverread terms
  1. neutral Truth tableone row per input
    • fill → K-map
  2. neutral K-maprows in Gray order
    • group → Prime implicants
  3. neutral Prime implicantslargest groups
    • must have → Essential primes
  4. neutral Essential primesthe only cover of a 1
    • then cover → Remaining 1s
  5. neutral Remaining 1sfewest extra groups
    • read terms → Sum of products
  6. neutral Sum of productsone AND per group
  1. Fill and group

    Copy each row of the table into its cell. Then find every group that cannot grow.

  2. Take what you must

    Find each 1 that only one prime covers. That prime is essential, so take it.

  3. Cover the rest and read

    If some 1s remain, add the fewest primes that cover them. Then read one term per group.

Read the diagram as text
  • Truth table: one row per input
  • K-map: rows in Gray order
  • Prime implicants: largest groups
  • Essential primes: the only cover of a 1
  • Remaining 1s: fewest extra groups
  • Sum of products: one AND per group
  • Truth table → K-map: fill
  • K-map → Prime implicants: group
  • Prime implicants → Essential primes: must have
  • Essential primes → Remaining 1s: then cover
  • Remaining 1s → Sum of products: read terms

For the lamp function, nothing remains after the essential primes.

Solve One Yourself

Group the 1s of the map below. Select two corners of a rectangle to draw a group. The status line counts your terms and literals.

Your turn: find the minimum cover
ab / cd00011110
00
01
11
10

No groups yet.

10 1s uncovered · 0 groups · 0 literals used. Target: 3 terms · 6 literals.

    f = Σm(1, 3, 4, 5, 9, 11, 12, 13, 14, 15). The target is 3 terms and 6 literals.

    Asked in interviews
    1. Why does a K-map use Gray order?

      Two product terms merge when they differ in one variable. Gray order puts every such pair in cells that touch, so a merge shows as a rectangle.

    2. What is an essential prime implicant?

      A prime implicant is a group that cannot grow. It is essential when it covers a 1 that no other prime covers. Every minimum cover holds all essential primes.

    3. Is the minimum cover always unique?

      No. After the essential primes, several choices may cover the remaining 1s at the same cost. The lamp function has one minimum; lesson G3.6 shows a function with two.

    Try It

    The table is the answer format of this module. Each term is a group of four bits in the order a b c d. CARE marks the variables the term uses. VALUE gives the value each must have.

    The table starts with one term for each 1 of the lamp map. The bench finds no wrong row, and reports 8 terms and 32 literals.

    Replace it with the three groups: set N = 3, CARE = {4'b0111, 4'b1001, 4'b0101} and VALUE = {4'b0101, 4'b0000, 4'b0000}. The bench then prints minimum is 3 terms, 7 literals: reached.

    Now grow the pair to four cells: change its CARE to 4'b0101. The bench prints first wrong row: abcd = 0111 (f is 0, the table gives 1). The group took in a 0.

    RUNIcarus Verilog · in your browser
    Edit the code, then run it
    Expected: 0 of 16 rows wrong 8 terms, 32 literals minimum is 3 terms, 7 literals: not reached
    Read included file: tb.sv
    // tb.sv: the bench (read-only). It builds the sum of products from the table in module answer,
    // compares it with f on every row that is not a don't-care, and counts terms and literals.
    module tb;
      // Bit m of F is f on row m, where m is the binary value of abcd. DC marks the don't-care rows.
      localparam logic [15:0] F  = 16'b0010010101110101;
      localparam logic [15:0] DC = 16'b0000000000000000;
      wire [7:0]  n;
      wire [31:0] care, value;
      answer ans (.n(n), .care(care), .value(value));
    
      // The sum of products on one row: 1 when some term of the table holds the row.
      function automatic logic table_at(input logic [3:0] row);
        logic hit;
        hit = 1'b0;
        for (int t = 0; t < 8; t++)
          if (t < n && ((row ^ value[4*t +: 4]) & care[4*t +: 4]) == '0) hit = 1'b1;
        return hit;
      endfunction
    
      initial begin
        int wrong, lits;
        logic [3:0] row, used;
        #1;                                  // let the table reach the wires
        wrong = 0;
        lits = 0;
        for (int m = 0; m < 16; m++) begin
          row = m[3:0];
          if (!DC[m] && table_at(row) !== F[m]) begin
            if (wrong == 0) $display("first wrong row: abcd = %b (f is %b, the table gives %b)", row, F[m], table_at(row));
            wrong++;
          end
        end
        for (int t = 0; t < 8; t++) if (t < n) begin
          used = care[4*t +: 4];   // one group's CARE bits
          lits += $countones(used);
        end
        $display("%0d of 16 rows wrong", wrong);
        $display("%0d terms, %0d literals", n, lits);
        if (wrong == 0 && n == 3 && lits == 7) $display("minimum is 3 terms, 7 literals: reached");
        else if (wrong == 0) $display("minimum is 3 terms, 7 literals: not reached");
      end
    endmodule
    

    Check Yourself

    Predict the outputThe program prints the four column labels of a map in order. Predict the exact line.
    module tb;
      function automatic logic [1:0] label(input int i);
        return 2'(i ^ (i >> 1));
      endfunction
      initial $display("%b %b %b %b", label(0), label(1), label(2), label(3));
    endmodule
    Spot the bugEach option is an expression for the lamp function f = Σm(0, 2, 4, 5, 6, 8, 10, 13). The bench compares it with f on all 16 rows. Which one fails?
    ConceptA group on a four-variable map holds eight cells. How many literals does its term have?
    ConceptWhich set of cells on a four-variable map (rows ab, columns cd) is one legal group?
    ConceptA 1 on the map is covered by exactly one prime implicant. What does that tell you?

    Common Mistakes

    Wrong Label the columns 00, 01, 10, 11.

    Then columns 01 and 10 are neighbours, but they differ in two bits, so their cells do not merge.

    Fix Use Gray order: 00, 01, 11, 10. Each step changes one bit.

    Wrong Draw a group of three or six cells, or a diagonal pair.

    Only a rectangle of 1, 2, 4 or 8 cells is one product term.

    Fix Split the shape into rectangles whose sizes are powers of two. They may overlap.

    Wrong Stop at the edge of the map.

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

    Fix Look for groups that wrap. The four corners form one group of four.

    Wrong Keep every large group you can find.

    A group whose cells are all inside other chosen groups adds a gate and covers nothing new.

    Fix Take the essential groups first. Add another group only for a 1 that is still uncovered.

    Remember

    • A K-map is a truth table in Gray order, so cells that touch differ in one variable.
    • A group is a rectangle of 1, 2, 4 or 8 cells; it may wrap around the edges and overlap others.
    • Read a group by keeping the variables that stay the same inside it.
    • A prime implicant cannot grow; an essential prime is the only cover of some 1.
    • Take the essential primes first, then the fewest groups for the 1s that remain.

    Practice

    Report a problem with this page