minterms.com

Learn Lesson 4 of 8

Karnaugh maps

Minimizing by eye: Gray-code ordering, grouping 1s in powers of two, wrap-around groups and don’t-cares.

A truth table, folded

A Karnaugh map (K-map) is the truth table redrawn as a grid, one cell per row. The trick is in the labels: rows and columns are numbered in Gray code — 00, 01, 11, 10 — so that moving one step in any direction changes exactly one variable.

That matters because of the combining identity from lesson 3, XY + XY = X: two minterms combine when they differ in one variable. On a K-map, those are exactly the cells that touch. You can see what can be combined.

Three variables: the majority function

Here is M = Σm(3, 5, 6, 7). The small number in each cell is its minterm number; notice the column order 0, 1, 3, 2.

ABC00011110010010011101324576
  • BC (3, 7)
  • AC (5, 7)
  • AB (6, 7)

Each loop is one product term. To read a loop, keep the variables that stay the same across it and drop the ones that change. The blue loop covers cells 3 and 7: A changes (0 to 1) so it drops out; B = 1 and C = 1 everywhere in the loop, giving BC.

M = BC + AC + AB

Cell 7 is inside all three loops. That is allowed and often necessary — it is idempotence, X + X = X, at work.

The rules of grouping

  1. A group contains only 1s (and, later, don’t-cares). Never a 0.
  2. A group is a rectangle whose size is a power of two: 1, 2, 4, 8 or 16 cells. A group of 2k cells eliminates k variables.
  3. The map wraps around: the left edge touches the right edge, and the top touches the bottom.
  4. Make every group as large as possible. A group that cannot grow is a prime implicant.
  5. Cover every 1 at least once, using as few groups as possible. Groups may overlap.

Why not a group of three, or six? Because a product term with k variables missing covers exactly 2k cells (lesson 2). No single AND term can cover three cells, so a loop of three would not correspond to any gate.

Four variables, and wrap-around

With four variables the rows are AB and the columns are CD, both in Gray order. This function has 1s in the four corners and in a block in the middle: F = Σm(0, 2, 5, 7, 8, 10, 13, 15).

ABCD000111100001111010010110011010010132457612131514891110
  • BD (0, 2, 8, 10)
  • BD (5, 7, 13, 15)

The four corners are one group of four: the map wraps left-to-right and top-to-bottom, so they are all neighbours. Across the corners, A and C both change; B = 0 and D = 0 stay fixed. That is BD. The loop is drawn in four open pieces that run off the edges of the map.

F = BD + BD

Eight minterms, two terms. (You may recognize it: F is 1 when B and D are equal — an XNOR.)

Don’t-cares: free cells

A BCD digit uses the codes 0–9; the inputs 10–15 never occur. Suppose F must be 1 when the digit is 5 or more: F = Σm(5, 6, 7, 8, 9) + d(10, 11, 12, 13, 14, 15). Mark the impossible inputs X.

ABCD000111100001111000000111XXXX11XX0132457612131514891110
  • A (8, 9, 10, 11, 12, 13, 14, 15)
  • BD (5, 7, 13, 15)
  • BC (6, 7, 14, 15)

An X may be included in a group if it makes the group bigger, and ignored otherwise. Here the don’t-cares let the two 1s at 8 and 9 grow into a group of eight:

F = A + BD + BC

Without the don’t-cares the best you can do is ABD + ABC + ABC — still three terms, but nine literals instead of five.

Two rules for X cells. You never have to cover an X, so do not add a group just for X cells. And once the expression is chosen, each X has quietly become a definite 0 or 1 — here inputs 10–15 all give F = 1.

Try all three maps yourself in the K-map solver: the majority function, the four corners and the BCD example with don’t-cares. Click a cell to change it and watch the groups move.

A procedure that works

  1. Fill in the 1s and Xs. Double-check the 11 and 10 rows and columns — the swapped order is the most common source of mistakes.
  2. Find a 1 that can be covered by only one largest group. That group is essential; draw it. Repeat.
  3. If any 1s are still uncovered, cover them with the fewest, largest groups you can.
  4. Check that no group is redundant: every group should cover at least one 1 that no other chosen group covers.

K-maps are quick and visual up to four variables. With five or six they become awkward, and beyond that you need a method that works on bit patterns rather than pictures: Quine–McCluskey.

Check yourself

  1. Minimize F(A, B, C) = Σm(0, 1, 2, 3, 6, 7).
    Show answer
    Two groups of four: the top row (0, 1, 3, 2) is A, and the block 3, 2, 7, 6 is B. F = A + B.
  2. Minimize F(A, B, C, D) = Σm(1, 3, 5, 7, 9, 11, 13, 15).
    Show answer
    The two middle columns (CD = 01 and 11) are full: a group of eight where only D = 1 is constant. F = D.
  3. Minimize F(A, B, C, D) = Σm(0, 1, 2, 4, 5, 8, 9, 10, 12, 13). Watch the edges.
    Show answer
    The two left columns (CD = 00 and 01) are full: C. The remaining 1s at 2 and 10 join the corners 0 and 8 in a wrap-around group of four: BD. F = C + BD.
  4. Minimize F(A, B, C, D) = Σm(1, 3, 7, 11, 15) + d(0, 2, 5).
    Show answer
    The column CD = 11 (3, 7, 15, 11) is CD and it is essential. Minterm 1 is still uncovered. It can join the top row using the don’t-cares 0 and 2, giving AB, or join 3, 5, 7 using the don’t-care 5, giving AD. Both F = CD + AB and F = CD + AD are minimal. Two correct answers.