K-map Simplification
Group the ones and watch variables cancel. Includes the wrap-around groups everybody misses.
Skip to the animationA Karnaugh map is a truth table folded so that physically adjacent cells differ in exactly one variable, which turns algebraic simplification into the visual task of drawing the largest possible rectangles around the ones.
Why the column order is 00, 01, 11, 10
Two product terms combine only when they differ in exactly one variable: A·B + A·B′ = A. So a map is useful only if neighbouring cells differ in one bit — which is what Gray code ordering guarantees.
In counting order, 01 and 10 differ in *two* bits and would not combine. The unusual column order is not a convention to memorise; it is the only arrangement in which adjacency on the page means adjacency in the algebra.
Grouping
- 1Fill the map from the truth table, one cell per row.
- 2Find the largest rectangle of 1s whose size is a power of two — 16, 8, 4, 2, then 1.
- 3Groups may overlap; you are covering the 1s, not partitioning them.
- 4Continue until every 1 is inside at least one group.
- 5Read each group: the variables that stay constant across it form its term; the ones that change cancel.
A group of 2ⁿ cells eliminates n variables, so bigger groups always give shorter terms. A group of eight in a four-variable map leaves a single literal.
The map wraps: because the first and last Gray labels also differ by one bit, the left edge is adjacent to the right and the top to the bottom. The four corners form a legitimate group of four, and missing wrap-around groups is the single most common K-map error.
Don't-cares
An X marks an input combination that cannot occur — BCD inputs 1010 to 1111, for example. You may treat each X as 1 or 0 independently, whichever makes the group larger.
Using don't-cares costs nothing and frequently removes a whole gate, so a design that does not mark them is throwing away free simplification.
Vocabulary, and where the method stops
- Implicant
- Any group of 1s that is a valid product term.
- Prime implicant
- A group that cannot be made larger. Only these are worth using.
- Essential prime implicant
- A prime implicant covering a 1 that no other prime implicant covers. It must appear in the answer.
| Variables | Practicality |
|---|---|
| 2 – 4 | Comfortable — a 4×4 grid |
| 5 – 6 | Possible, using two or four stacked maps |
| 7 or more | Unusable — adjacency stops being visible |
Beyond that, Quine-McCluskey expresses the same combining rule as a table, so it is mechanical and scales. Real synthesis tools use heuristic minimisers such as Espresso, because exact minimisation is NP-hard.
The numbers you will be asked for
- Variables eliminated
a group of 2ⁿ cells removes n variables
So always take the largest group available.
- Map size
2ᵏ cells for k variables
Four variables give sixteen cells.
- Adjacency
neighbours differ in exactly one bit
Which is why Gray ordering is compulsory.
Advantages and disadvantages
Advantages
- Turns algebraic minimisation into pattern-spotting.
- Guaranteed minimal two-level form for up to four variables.
- Don't-cares are exploited naturally rather than as a special case.
- The same map gives an SOP or a POS, depending on whether you group the 1s or the 0s.
Disadvantages
- Visual, so it fails beyond five or six variables.
- Wrap-around adjacency is easy to overlook.
- Only minimises two-level logic; multi-level circuits may be smaller still.
- Says nothing about hazards or delay.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.