Karnaugh maps

Simplifying with algebra depends on spotting the right steps. A Karnaugh map (K-map) makes the steps visible. It is the truth table drawn as a grid whose rows and columns are in Gray code order (00, 01, 11, 10), so any two neighbouring cells differ in exactly one variable.

Two neighbouring 1s, such as ABC' and ABC, combine: AB(C' + C) = AB. The variable that changes drops out. That is the whole trick, done by eye.

The rules for grouping

1. Circle only 1s (and don't-cares, if they help).
2. Groups are rectangles of 1, 2, 4, 8 or 16 cells: a power of two.
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, and use as few groups as possible. Groups may overlap.
5. Each group becomes one product term: keep only the variables that stay the same in every cell of it.

A group of 2 drops one variable, a group of 4 drops two, a group of 8 drops three.

Click the cells to set your own function, and click a group to see its cells:

This is the majority function from the last lesson: Σm(3, 5, 6, 7) becomes AB + AC + BC. Try vars={4} by choosing 4 variables, and set the four corners: they form one group, B'D', because the map wraps around.

def gray(bits):
    if bits == 1:
        return ["0", "1"]
    smaller = gray(bits - 1)
    return ["0" + g for g in smaller] + ["1" + g for g in reversed(smaller)]

codes = gray(2)
print("Gray code:", codes)
print("AB\\CD", "  ".join(codes))
for ab in codes:
    print(" ", ab, "  ", "   ".join(str(int(ab + cd, 2)).rjust(2) for cd in codes))

Don't-cares

Sometimes some inputs can never happen, such as the codes 10 to 15 on a decimal (BCD) digit. Mark those cells X. An X may be counted as 1 when that makes a group bigger, and ignored otherwise.

from itertools import product

# Majority: Σm(3, 5, 6, 7) simplified with a K-map to AB + AC + BC
for a, b, c in product([0, 1], repeat=3):
    row = a * 4 + b * 2 + c
    table = 1 if row in (3, 5, 6, 7) else 0
    simple = (a & b) | (a & c) | (b & c)
    print(a, b, c, " table:", table, " AB + AC + BC:", simple)

For more than about 5 variables, maps get hard to read. Programs use the same idea in table form (the Quine–McCluskey method, which this page's map runs behind the scenes) or faster approximate tools like Espresso.

Mark lesson complete