K-map minimization

Also called: K-map simplification, K-map method, Karnaugh map minimization, Karnaugh map simplification, simplifying with a K-map

The step-by-step K-map method for finding a minimal sum of products: fill the map, take the essential prime implicants, then cover the rest with the fewest, largest groups.

K-map minimization is the full procedure for turning a function into its cheapest two-level form by hand. For a minimal sum of products:

Fill the map with the 1s and any don't-care X's (filling a k map).
List the prime implicants: grow each 1's group as far as it will go without touching a 0.
Circle the essentials: any prime implicant that is the only cover for some 1 (essential prime implicant).
Cover what's left with the fewest, largest remaining prime implicants. If there's a tie, any cheapest choice is correct.
Read one product term per group and OR them together.

Then check: could two groups merge into a bigger one? Could any group be removed? If yes, you're not done.

"Minimal" means fewest terms first, then fewest literals. That keeps the gate input count low, which usually means fewer gates, less area and less delay.

For a minimal product of sums, run the same steps on the 0s (grouping zeros). Don't-cares may be used in either form, independently.

The method is reliable up to 4 variables, workable at 5 or 6, and replaced by software beyond that. The software uses the same ideas: prime implicants, essentials and covering.

AB\CD	00	01	11	10
00	1m0	1m1	0m3	1m2
01	1m4	1m5	0m7	1m6
11	0m12	0m13	1m15	0m14
10	0m8	1m9	1m11	0m10

Worked examples

Example

A complete 4-variable example

Minimize F = Σm(0, 1, 2, 4, 5, 6, 9, 11, 15).

1.
Fill: row 00 has m0 m1 m2, row 01 has m4 m5 m6, row 11 has m15, row 10 has m9 m11.
2.
Prime implicants: (m0 m1 m4 m5), (m0 m2 m4 m6, wrapping), (m1 m9), (m9 m11), (m11 m15).
3.
Essentials: m5 is only in ; m2 and m6 are only in ; m15 is only in .
4.
Covered so far: everything except m9.
5.
m9 can go in or , each 3 literals. Pick either.
6.
F = . Swapping in for the last term is equally minimal.

Example

Using don't-cares

Minimize F = Σm(4, 6, 7) with d(5).

A\BC	00	01	11	10
0	0m0	0m1	0m3	0m2
1	1m4	Xm5	1m7	1m6

1.
Treat the X at m5 as a 1: then the whole bottom row, m4 m5 m7 m6, is a group of 4, where A = 1.
2.
F = A, one literal. Without the X it would be .

Common mistakes

Circling the largest group first instead of the essentials. It can add a term you don't need.
Stopping before checking whether any group is redundant or could be enlarged.
Thinking the minimal answer must be unique. Ties are common, and any minimal choice is correct.

Practice K-map minimization

Interactive questions with instant feedback and a worked solution for every wrong answer.

Karnaugh Maps lesson full course

And 2 more in the Karnaugh Maps lesson.

Practice exams

Learn it step by step

K-map minimization is taught in Karnaugh Maps and Boolean Simplification.

Karnaugh Maps →Boolean Simplification →

All terms