K-Maps and Minimization

Fewer and smaller terms mean fewer gates. A Karnaugh map (K-map) arranges the truth table so that minterms that differ in one variable sit next to each other, and simplification becomes a matter of drawing rectangles.

The 4-variable K-map

Rows are labelled by AB and columns by CD, both in Gray code order (00, 01, 11, 10), so neighbouring cells differ in exactly one bit. The numbers in the cells are minterm indices (ABCD in binary):

The map wraps around: the left and right columns are adjacent, and so are the top and bottom rows. The four corners (0, 2, 8, 10) form one group.

Grouping rules

1. Group the 1s into rectangles whose sizes are powers of 2: 1, 2, 4, 8 or 16 cells.
2. Make each group as large as possible: a group of 2ᵏ cells eliminates k variables.
3. Use as few groups as possible, so that every 1 is covered. Groups may overlap.
4. Read each group as a product of the variables that stay constant across it (A if it is always 1, A′ if always 0).

Example: F(A, B, C, D) = Σm(1, 3, 4, 5, 9, 11, 12, 13).

• Cells 4, 5, 12, 13 (rows 01 and 11, columns 00 and 01): B = 1, C = 0, so BC′.
• Cells 1, 3, 9, 11 (rows 00 and 10, columns 01 and 11): B = 0, D = 1, so B′D.
• Cells 1, 5, 9, 13 (the whole 01 column) form a group too, C′D, but every one of its cells is already covered.

So F = BC′ + B′D.

Prime and essential prime implicants

• An implicant is a product term that is 1 only where F is 1 (a valid group).
• A prime implicant (PI) is an implicant that cannot be enlarged (a maximal group). Above: BC′, B′D and C′D.
• An essential prime implicant (EPI) is a PI that covers some 1 that no other PI covers. It must appear in every minimal SOP. Above: BC′ (the only PI covering 4 and 12) and B′D (the only PI covering 3 and 11). C′D is not essential.

A minimal SOP = all EPIs + the fewest other PIs needed to cover the remaining 1s. When there are no EPIs (a cyclic map), there may be several equally good answers.

Don't-care conditions

Sometimes some input combinations never occur, or their output does not matter (for example the codes 1010–1111 in a BCD circuit). These don't cares (marked X, written d(…)) can be treated as 1 or 0, whichever gives larger groups. They are never required to be covered.

Minimal POS

Group the 0s instead of the 1s to get F′ as an SOP, then apply De Morgan; equivalently, read each group of 0s as a sum term with complemented sense (a variable that is 1 throughout the group appears as A′). For the example above, the 0s give F = (B + D)(B′ + C′).

The Quine–McCluskey method

K-maps become impractical beyond 5 or 6 variables. The Quine–McCluskey (tabular) method does the same thing systematically, and is easy to program:

1. Write the minterms (and don't cares) in binary.
2. Repeatedly combine pairs of terms that differ in exactly one bit, replacing that bit with "−". Terms that can never be combined are the prime implicants.
3. Build a chart of which PIs cover which minterms; pick the essential ones, then cover the rest with as few PIs as possible.

from itertools import combinations

def prime_implicants(n, ones, dont_cares=()):
    terms = {format(m, f"0{n}b") for m in set(ones) | set(dont_cares)}
    primes = set()
    while terms:
        merged, used = set(), set()
        for a, b in combinations(sorted(terms), 2):
            diff = [i for i in range(n) if a[i] != b[i]]
            if len(diff) == 1:
                merged.add(a[:diff[0]] + "-" + a[diff[0] + 1:])
                used |= {a, b}
        primes |= terms - used
        terms = merged
    return sorted(primes)

def covers(p, m, n):
    return all(c in ("-", b) for c, b in zip(p, format(m, f"0{n}b")))

def essential(primes, ones, n):
    return [p for p in primes
            if any(covers(p, m, n) and sum(covers(q, m, n) for q in primes) == 1 for m in ones)]

def as_term(p, names="ABCD"):
    return "".join(v + ("'" if c == "0" else "") for v, c in zip(names, p) if c != "-")

for ones, dc in [([1, 3, 4, 5, 9, 11, 12, 13], []), ([2, 3, 7, 9, 11, 13], [1, 10, 15])]:
    pis = prime_implicants(4, ones, dc)
    print(f"Σm{tuple(ones)} + d{tuple(dc)}:")
    print("  prime implicants:", [as_term(p) for p in pis])
    print("  essential:       ", [as_term(p) for p in essential(pis, ones, 4)])

Σm(1, 3, 4, 5, 9, 11, 12, 13) + d():
  prime implicants: ["C'D", "B'D", "BC'"]
  essential:        ["B'D", "BC'"]
Σm(2, 3, 7, 9, 11, 13) + d(1, 10, 15):
  prime implicants: ['CD', "B'D", "B'C", 'AD']
  essential:        ['CD', "B'C", 'AD']

In the second function, the don't cares 10 and 15 let CD, B′C and AD grow into groups of four (don't care 1 is simply left out); those three essential PIs already cover every required 1, so F = CD + B′C + AD.

Practice questions