Karnaugh maps and minimization

Lesson 3 simplified expressions with the laws of Boolean algebra. That works, but it depends on spotting the right step, and it is easy to stop before reaching the simplest form. In 1953 Maurice Karnaugh, an engineer at Bell Labs, published a graphical method that makes simplification almost mechanical for functions of up to four variables, and manageable for five or six. A Karnaugh map, or K-map, rearranges the truth table so that minterms which differ in only one variable sit next to each other, and the adjacencies that algebra would find step by step can be seen at a glance. This lesson covers two-, three- and four-variable maps, prime and essential implicants, don't-care conditions, product-of-sums minimization, and the Quine-McCluskey method that software uses for larger functions.

The idea: adjacency

The key simplification in two-level logic is XY + XȲ = X: two product terms that differ in exactly one variable merge into one term without that variable. In a truth table, rows that differ in one variable can be far apart: rows 0011 and 1011 are eight rows apart. A K-map places each minterm in a cell of a grid and orders the rows and columns in Gray code, so that any two cells next to each other differ in exactly one variable. The edges also wrap around: the leftmost column is adjacent to the rightmost, and the top row to the bottom row, as if the map were drawn on a doughnut.

Simplifying then means circling groups of 1s. A group must be a rectangle whose size is a power of two (1, 2, 4, 8 or 16 cells). A group of two cells eliminates one variable, a group of four eliminates two, and a group of eight eliminates three. The product term for a group contains only the variables that keep the same value across every cell in it.

Two- and three-variable maps

A two-variable map has four cells, one for each minterm of A and B. A three-variable map has eight cells, usually arranged as two rows (A = 0 and A = 1) and four columns for BC in the Gray order 00, 01, 11, 10. The order of the columns is the essential trick: 01 and 11 differ only in B, 11 and 10 differ only in C, and 10 wraps around to 00, which differs only in B.

The example shows that a function can have more than one minimal expression. Both answers use the same number of terms and literals, so either is acceptable; a designer might choose the one that shares a term with another output.

Four-variable maps

A four-variable map is a 4 × 4 grid with AB labeling the rows and CD labeling the columns, both in Gray order. Each cell is adjacent to four others, counting the wrap-around at the edges. The four corner cells are all adjacent to each other, which surprises everyone the first time. The map makes groups of four and eight easy to see: a whole row, a whole column, a 2 × 2 square, the four corners, or two edge columns together.

Implicants, prime implicants and essential prime implicants

A few words make the method precise. An implicant is any product term that is 1 only where the function is 1; on the map, it is any valid group of 1s. A prime implicant is an implicant that cannot be made larger: its group cannot be doubled without including a 0. An essential prime implicant is a prime implicant that covers at least one 1 that no other prime implicant covers. Every minimal sum of products uses only prime implicants, and it must include all the essential ones.

This gives a reliable procedure. First, find all the prime implicants by making every group as large as possible. Second, mark the essential prime implicants and include them. Third, if any 1s are still uncovered, choose the smallest set of the remaining prime implicants that covers them. On a four-variable map the third step is usually easy to do by eye. The common beginner's error is to start with the biggest group and then add groups greedily, which can produce a cover with a redundant term.

Don't-care conditions

In many designs some input combinations can never occur, or the output does not matter when they do. These are don't-care conditions, marked with an X or a dash on the map. A don't-care can be treated as 1 if that makes a group larger, or as 0 if it does not help. Don't-cares often give large savings. The classic example is a circuit that takes a BCD digit as input: the patterns 1010 to 1111 never occur, so they are all don't-cares.

Amara's tachometer shows each digit on a seven-segment display, and each segment needs its own logic function of the four BCD bits D, C, B and A (with D the most significant). Segment a, the top bar, is lit for the digits 0, 2, 3, 5, 6, 7, 8 and 9, and off for 1 and 4.

The design is only correct if the don't-care inputs truly never occur. If a fault could put 1100 on the inputs, the display would show a strange symbol. For a safety function, such as deciding when the walk signal may turn on, Daniel insists that unused input or state codes are assigned a safe output deliberately rather than left as don't-cares.

Product-of-sums minimization

A K-map can also give a minimal product of sums. Group the 0s instead of the 1s, using the same rules. Each group of 0s gives a sum term in which a variable appears uncomplemented if it is 0 throughout the group and complemented if it is 1. The AND of these sum terms is the minimal POS. Equivalently, find the minimal SOP of the complement F̄ from the 0s and apply De Morgan's theorem. Sometimes the POS is cheaper than the SOP; a designer can work out both and pick the smaller.

Multiple outputs and sharing

Real circuits rarely compute just one function. The seven-segment decoder has seven outputs, all functions of the same four inputs. Minimizing each output separately gives a correct design, but a smaller one may share product terms between outputs, even if a shared term is not prime for every output on its own. Lesson 6 shows the complete decoder; the multiple-output optimization is usually left to software.

Five and six variables

A five-variable map can be drawn as two four-variable maps side by side, one for E = 0 and one for E = 1, with cells in the same position on the two maps counting as adjacent. A six-variable map uses four such maps. Beyond that, maps become impractical and designers rely on algorithms. Even at five variables it is easy to miss an adjacency, so the map is best used as a check on a software result or as a teaching tool.

The Quine-McCluskey method

The tabular method developed by Willard Quine and Edward McCluskey in the 1950s does what a K-map does, but in a form a computer can follow for any number of variables. Write the minterms and don't-cares in binary. Repeatedly combine pairs that differ in exactly one bit, replacing that bit with a dash, until no more combinations are possible; the terms that never combine are the prime implicants. Then build a prime implicant chart, select the essential prime implicants, and cover the remaining minterms with as few others as possible. The method finds all prime implicants exactly, but the covering step can grow exponentially, so large practical tools such as the Espresso program use heuristics that give near-minimal results quickly.

# Quine-McCluskey: prime implicants, then a smallest cover (brute force is fine for small problems)
from itertools import combinations

def combine(a, b):
    diff = [i for i in range(len(a)) if a[i] != b[i]]
    if len(diff) == 1 and "-" not in (a[diff[0]], b[diff[0]]):
        i = diff[0]
        return a[:i] + "-" + a[i + 1:]
    return None

def primes(minterms, dontcares, n):
    terms = {format(m, f"0{n}b") for m in minterms + dontcares}
    found = set()
    while terms:
        used, nxt = set(), set()
        for a, b in combinations(sorted(terms), 2):
            c = combine(a, b)
            if c:
                nxt.add(c); used.update((a, b))
        found |= terms - used
        terms = nxt
    return found

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

def minimal_cover(minterms, dontcares, n):
    pis = sorted(primes(minterms, dontcares, n))
    for k in range(1, len(pis) + 1):
        for choice in combinations(pis, k):
            if all(any(covers(t, m, n) for t in choice) for m in minterms):
                return pis, choice

def to_expr(term, names):
    out = ""
    for t, v in zip(term, names):
        if t == "1": out += v
        elif t == "0": out += v + "'"
    return out or "1"

names = "DCBA"
pis, best = minimal_cover([0, 2, 3, 5, 6, 7, 8, 9], [10, 11, 12, 13, 14, 15], 4)
print("prime implicants:", ", ".join(to_expr(t, names) for t in pis))
print("segment a =", " + ".join(to_expr(t, names) for t in best))

prime implicants: B, C'A', CA, D
segment a = B + C'A' + CA + D

The program finds every prime implicant and then searches for the smallest set that covers all the required minterms. For segment a there are only four prime implicants and every one is essential, so the cover uses all of them, exactly as the map showed. For other functions the list of primes is longer than the cover. Amara keeps this script for checking hand minimizations of five- and six-variable functions, where a missed wrap-around adjacency is easy.

Is minimal always best?

Two-level minimization counts terms and literals, which is a good proxy for cost in a programmable logic array or a small gate-level circuit. In a modern chip, synthesis tools optimize for area, delay and power together and use multi-level logic with shared intermediate signals, which can be far smaller than any two-level form. In a programmable chip built from lookup tables (lesson 12), any function of up to four or six inputs costs the same single table, so minimization of small functions hardly matters there. K-maps remain valuable because they build intuition about adjacency and hazards, and because small hand designs and exam questions still use them.