Karnaugh maps

Gray code order, grouping rules for two to four variables, wrap-around groups, and reading off the expression.

A8.6Boolean algebra and logic circuitsA level25 min

Algebra always works, but it needs you to spot which law to use next, and it is easy to stop before the expression is as simple as it can be. A Karnaugh map is a picture of a truth table, arranged so that the terms that can be combined sit next to each other. You find the simplest expression by drawing boxes round the 1s. For up to four inputs it is quicker and more reliable than algebra.

The idea

In lesson A8.5 you used (X ∧ Y) ∨ (X ∧ ¬Y) = X again and again: two terms that differ in only one letter combine, and that letter disappears. A Karnaugh map puts every pair of rows that differ in exactly one input into neighbouring cells. So any two neighbouring 1s can be combined, any block of four neighbouring 1s loses two letters, and so on.

Gray code order

To make neighbours differ in one bit, the rows and columns are labelled in Gray code order, not binary order:

In Gray code order each label differs from the next in exactly one bit, and the last (10) also differs from the first (00) in one bit. That is why a map wraps round: the left edge is next to the right edge, and the top edge next to the bottom.

A two-input map

For A · B + A · B̅ + A̅ · B from lesson A8.5, put a 1 in each cell whose term is in the expression:

Draw the largest groups you can. The bottom row (A = 1, whatever B is) is a group of two: it gives A. The right column (B = 1, whatever A is) is a group of two: it gives B. The two groups overlap in the corner, which is allowed. So the expression is A ∨ B, the same answer as seven lines of algebra.

A three-input map

Here the rows are A and the columns are BC in Gray code order. This is the function with 1s in rows 000, 010, 100, 110 and 111 of its truth table:

• The columns BC = 00 and BC = 10 are neighbours, because the map wraps round. Together they make a group of four. Across that group A changes and B changes, but C is 0 in every cell: the group is ¬C.
• The remaining 1, at A = 1, BC = 11, pairs with its neighbour at BC = 10. Across that pair C changes, but A = 1 and B = 1: the group is A ∧ B.

So Q = ¬C ∨ (A ∧ B). As a sum of products straight from the truth table it had five terms of three literals each.

A four-input map

Rows are AB and columns are CD, both in Gray code order. Here is Q with 1s at AB = 01 and AB = 11 in columns CD = 00, 01 and 11:

• Columns 00 and 01 in rows 01 and 11 make a square of four. B = 1 and C = 0 throughout: B ∧ ¬C.
• Columns 01 and 11 in the same rows make another square of four, overlapping the first. B = 1 and D = 1 throughout: B ∧ D.

So Q = (B ∧ ¬C) ∨ (B ∧ D), which you can factor as B ∧ (¬C ∨ D) if that saves a gate.

In a four-input map the wrapping works both ways, so the four corner cells are neighbours of each other and can form a group of four.

The grouping rules

1. Groups contain only 1s.
2. A group has 1, 2, 4, 8 or 16 cells: a power of two.
3. A group is a rectangle: a row, a column, a square or a larger rectangle. Never a diagonal or an L shape.
4. Make each group as large as possible, even if that means overlapping another group.
5. Use as few groups as possible, but every 1 must be in at least one group.
6. Groups may wrap round the edges of the map.

To read a group, look at each input across all its cells. An input that changes within the group disappears. An input that stays 1 appears as its letter, and one that stays 0 appears with NOT. Then OR the groups together. In a four-input map a group of 2 gives three literals, a group of 4 gives two, and a group of 8 gives one.

Drawing a map by program

A program can lay out the map in Gray code order; the grouping is still up to you.

GRAY2 = ["00", "01", "11", "10"]

def q(a, b, c):
    return 1 if (a, b, c) in [(0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 0), (1, 1, 1)] else 0

print("A\\BC 00 01 11 10")
for a in [0, 1]:
    cells = []
    for bc in GRAY2:
        cells.append(str(q(a, int(bc[0]), int(bc[1]))))
    print(f" {a}    " + "  ".join(cells))

simplified = lambda a, b, c: int((not c) or (a and b))
print("matches:", all(q(a, b, c) == simplified(a, b, c) for a in [0, 1] for b in [0, 1] for c in [0, 1]))

Run this in the simulator

Task: draw the map, read the groups

f(a, b, c, d) takes four bits (each 0 or 1) and returns 1 if the row number 8a + 4b + 2c + d is in the list ONES, otherwise 0.

First print the Karnaugh map of f as four lines, one per value of AB in Gray code order (00, 01, 11, 10), each giving the cells for CD in Gray code order (00, 01, 11, 10), in exactly this form:

AB=00: 1 0 0 1

Then read the groups off your map and write simplified(a, b, c, d) as a single return line using at most five of and, or and not in total. It may not use ONES or call f. Finally, check it on all sixteen combinations, treating any true result as 1 and any false result as 0, and print matches: True if it agrees with f on every one, or matches: False if not.

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

ONES = [0, 2, 8, 10, 11, 14, 15]

def f(a, b, c, d):
    return 1 if 8 * a + 4 * b + 2 * c + d in ONES else 0

def simplified(a, b, c, d):
    return 0

Challenges

1. Draw the map for the sum of products table in lesson A8.2's task, [0, 0, 1, 0, 0, 0, 1, 1], and read off the simplest expression.
2. What goes wrong if you label a map's columns 00, 01, 10, 11? Find a pair of cells that look like neighbours but are not.
3. A map full of 1s except one cell: how many groups do you need, and what is the expression?