The short answer: a Karnaugh map (K-map) is a grid that arranges a truth table so that neighbouring cells differ in only one variable. Grouping adjacent 1s in rectangles of 1, 2, 4, 8 or 16 cells removes the variables that change inside the group, giving a minimal sum-of-products expression. K-maps work well up to four variables (five or six with care); beyond that, tools use algorithms such as Quine-McCluskey and Espresso.
K-maps are still a staple of digital design courses and interviews because they make simplification visual. This post combines my older K-map and logic minimisation posts into one practical guide.
- How a K-map is laid out
- A worked 4-variable example
- Grouping rules
- Beyond K-maps
- Common mistakes
Table of Contents
Part 1: How a K-map is laid out
Rows and columns are labelled in Gray code order (00, 01, 11, 10), so moving one cell in any direction changes only one variable. The map also wraps around: the left and right edges are neighbours, and so are the top and bottom.
Part 2: A worked 4-variable example
Take F(A,B,C,D) = Σm(0, 2, 5, 7, 8, 10, 13, 15). The four corners form one group: B and D are 0 in all of them, so that group is B’D’. The centre 2×2 block has B = 1 and D = 1, giving BD. So F = B’D’ + BD, which is simply B XNOR D.
Part 3: Grouping rules
- Groups must be rectangles of 1, 2, 4, 8 or 16 cells.
- Make groups as large as possible; bigger groups mean fewer variables.
- Use as few groups as possible to cover every 1.
- Groups can overlap and can wrap around the edges.
- Don’t-care cells (X) can be included in a group if that makes it bigger, and left out otherwise.
Part 4: Beyond K-maps
For more than four or five variables, K-maps get unwieldy. The Quine-McCluskey method gives an exact tabular minimisation, and heuristic algorithms like Espresso handle large functions efficiently. Synthesis tools use far more advanced multi-level optimisation, so in real design work you mostly use K-maps to reason about small pieces of logic, and in interviews.
Part 5: Common mistakes
- Using binary order (00, 01, 10, 11) instead of Gray order on the axes.
- Forgetting that the corners and edges wrap around.
- Making groups of 3 or 6 cells, which are not allowed.
- Missing a larger group because you started with small ones.
Practise this on VLSI Forge
I built VLSI Forge so you can write RTL in your browser, run it on a real simulator and check every signal in the waveform. Free, nothing to install.
FAQ
Why are K-map rows in Gray code order?
So that adjacent cells differ by exactly one variable, which is what allows grouping to eliminate variables.
What are don’t-care conditions?
Input combinations that can never happen or whose output does not matter. You can treat them as 1 or 0, whichever gives a simpler result.
Can K-maps give a product-of-sums form?
Yes. Group the 0s instead of the 1s to get a minimal POS expression.
Are K-maps used in industry?
Rarely directly; synthesis tools do the optimisation. But they remain very useful for understanding logic and for interviews.
