Karnaugh maps

Why it exists

Algebraic simplification works only when you can see the pattern. A Karnaugh map (K-map) turns the search for patterns into a picture. The truth table is arranged on a grid so that cells that differ in exactly one variable are physically next to each other. Two adjacent 1-cells then merge into a term with one variable fewer ($xy + xy' = x$), four cells into a term with two fewer, and so on. GATE questions give you a function (as a truth table, minterms or an expression) and ask for the minimal SOP or POS, the number of prime implicants, the number of essential prime implicants, or how don't cares change the answer. Maps are practical for up to 4 variables (5 with some care).

Prerequisites

You need minterm and maxterm numbering from SOP, POS, minterms and maxterms and the combining law $xy + xy' = x$ from Boolean algebra.

Precise definitions

Layout. A map for $n$ variables has $2^n$ cells, one per minterm. The labels along each side are in Gray-code order (00, 01, 11, 10), not in binary order, so that neighbouring labels differ in one bit. The cell in row label $r$ and column label $c$ is the minterm whose binary index is $r$ followed by $c$. For four variables $A, B, C, D$ the rows are $AB$ and the columns $CD$; for three variables the rows are $A$ (0, 1) and the columns $BC$ (00, 01, 11, 10). With a 5th variable use two 4-variable maps (for $E = 0$ and $E = 1$); a cell is also adjacent to the cell in the same position on the other map.

Adjacency. Two cells are adjacent if their minterms differ in exactly one variable. On the map, neighbours across the edges count: the left and right edges are adjacent, the top and bottom edges are adjacent, and so the four corners are all neighbours of each other.

Group (implicant). A rectangle of 1-cells (or don't cares) whose number of cells is a power of two (1, 2, 4, 8, 16) and whose sides are aligned to the Gray-code layout; wrap-around is allowed, diagonals and L-shapes are not. A group of $2^k$ cells is a product term with $n - k$ literals: the $k$ variables that take both values inside the group are dropped, and each variable that is constant is kept (true form if constant 1, complemented if constant 0).

Prime implicant. A group that cannot be enlarged (it is not contained in a larger group). Essential prime implicant. A prime implicant that covers at least one 1-cell no other prime implicant covers; it must be in every minimal SOP. A 1 covered by only one prime implicant is what marks it as essential.

Minimal SOP (as defined on the forms page): the fewest product terms, and among those the fewest literals. Procedure:

1. Fill in the map from the truth table or minterm list.
2. Find all prime implicants (the largest possible groups).
3. Select all the essential prime implicants and mark the cells they cover.
4. Cover the remaining 1s with as few extra prime implicants as possible, preferring the largest.
5. Read each group as a product term and OR them. Groups may overlap.

Don't cares. A cell marked X may be put in a group if it helps make the group larger, and it need not be covered. A don't care is never required in the answer.

Product of sums. Group the 0s (and the don't cares) of $F$ instead. Each group of 0s gives a sum term: a variable that is constant 0 over the group appears in true form, a variable that is constant 1 appears complemented. The AND of the sum terms is the minimal POS of $F$. (Equivalently, minimise $F'$ as an SOP and complement the result with De Morgan.)

Non-uniqueness. A function can have several different minimal SOPs of the same cost. This happens when no prime implicant is essential for some cells, as in the cyclic case below.

Limits. For $n > 5$ or 6 a map becomes unreadable. The tabular method (Quine-McCluskey) does the same job algorithmically.

How it works

Each animation fills in the map, then adds groups one at a time, the essential prime implicants first, and finally reads the expression. The map labels are Gray-coded, the number in the corner of each cell is its minterm index, and the coloured dots show which groups cover a cell. Every group, every cell and every term is produced by an exact minimiser (not typed in), and re-derived in the tests.

Worked examples

#include <stdio.h>
 
static int f3(int m) { return m == 0 || m == 2 || m == 4 || m == 5 || m == 6; }
static int g3(int m) {
    int a = (m >> 2) & 1, b = (m >> 1) & 1, c = m & 1;
    return !c || (a && !b);
}
 
static int corners(int m) { return m == 0 || m == 2 || m == 5 || m == 7 || m == 8 || m == 10 || m == 13 || m == 15; }
static int xnor_bd(int m) {
    int b = (m >> 2) & 1, d = m & 1;
    return b == d;
}
 
static int sop1(int m) {
    int a = (m >> 3) & 1, c = (m >> 1) & 1, d = m & 1;
    return (!a && d) || (c && d);
}
static int sop2(int m) {
    int a = (m >> 3) & 1, b = (m >> 2) & 1, c = (m >> 1) & 1, d = m & 1;
    return (!a && !b) || (c && d);
}
 
int main(void) {
    int bad = 0;
    for (int m = 0; m < 8; m++) bad += f3(m) != g3(m);
    printf("C' + AB' differs from the sum m(0,2,4,5,6) on %d of 8 rows\n", bad);
    bad = 0;
    for (int m = 0; m < 16; m++) bad += corners(m) != xnor_bd(m);
    printf("B'D' + BD differs from the corner function on %d of 16 rows\n", bad);
    printf("A'D + CD and A'B' + CD differ on rows:");
    for (int m = 0; m < 16; m++)
        if (sop1(m) != sop2(m)) printf(" %d", m);
    printf("\n");
    int ones[] = {1, 3, 7, 11, 15};
    int ok = 1;
    for (int i = 0; i < 5; i++) ok = ok && sop1(ones[i]) && sop2(ones[i]);
    printf("both give 1 on every required minterm: %d\n", ok);
    return 0;
}

C' + AB' differs from the sum m(0,2,4,5,6) on 0 of 8 rows
B'D' + BD differs from the corner function on 0 of 16 rows
A'D + CD and A'B' + CD differ on rows: 0 2 5
both give 1 on every required minterm: 1

Cheat box

Traps and GATE patterns

Connections

A K-map starts from the canonical forms in SOP, POS, minterms and maxterms and its answer feeds the gate networks of logic gates and the whole flow in combinational design. Two adjacent prime implicants that are not overlapped can cause a glitch; that is the subject of static hazards. The tabular method is the same idea in a form a program can carry out.

PYQs

Consider a Boolean function F with the following
min-term expression:
F(P, Q, R, S) = Σm(1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal
sum-of-products expression(s) of F?

Consider the following 4-variable Boolean
function
F(A, B, C, D) = Σm(0, 1, 2, 3, 8, 9, 10, 11)

Consider A as MSB, D as LSB. Which one of the
following options represents the minimal sum of
products form for the above function?

Note: + is OR operation, · is AND operation, ' is
NOT operation

The number of min-terms after minimizing the
following Boolean expression is ________.

[D' + AB' + A'C + AC'D + A'C'D]'.

Let f(w,x,y,z) = Σ (0,4,5,7,8,9,13,15). Which of the
following expressions are NOT equivalent to f?

          P: x'y'z' + w'xy' + wy'z + xz

          Q: w'y'z' + wx'y' + xz

          R: w'y'z' + wx'y' + xyz + xy'z

DIGITAL LOGIC
          S: x'y'z' + wx'y' + w'y

The boolean function for a combinational circuit
with four inputs is represented by the following
Karnaugh map.

Which of the product terms given below is an
essential prime implicant of the function?

Self-check

Revision card

References