See it move
The idea
A Karnaugh map redraws a so that neighbouring cells differ by exactly one variable. When two neighbouring cells are both 1, the variable that differs doesn't matter, and it drops out. Simplifying becomes a matter of drawing rectangles.
Rules for grouping
- Rows and columns run in Gray order: 00, 01, 11, 10. This is what makes neighbours differ by one bit.
- Groups must be rectangles of 1, 2, 4, 8 or 16 cells.
- Make each group as large as possible, since larger groups mean fewer literals.
- Groups may overlap, and they may wrap around the edges of the map.
- Every 1 must be covered, using as few groups as you can.
Don't-cares
An X marks an input combination that can't occur, or whose output doesn't matter. Use an X if it lets a group grow, and ignore it otherwise. For example, a BCD circuit never sees the values 10 to 15, and that freedom can shrink the logic considerably.
Reading a group
A variable stays in the term only if it has the same value across the whole group. Suppose a group of four has A = 1 throughout, D = 1 throughout, and B and C taking both values. Its term is AD.
Common mistake
Using the ordinary order 00, 01, 10, 11 on the axes. Cells for 01 and 10 differ by two bits, so they aren't true neighbours, and any group across them gives a wrong answer. Another frequent slip is forgetting that the top and bottom edges touch, as do the left and right.
Where this stops
K-maps work well up to about four inputs, so treat them as a way to build intuition and to answer interview questions. Synthesis tools use other algorithms for real designs. The animation above does use an exact method behind the scenes, so you can compare your own grouping against the minimal answer.
Key ideas
- Rows and columns follow Gray order, so neighbours differ by one bit.
- Group in powers of two, as large as possible, and wrap around edges.
- Don't-cares can join a group whenever that helps.
Your exercise
Interview questions
coreWhy Gray order on the axes?
Adjacent cells differ in one variable, so that variable cancels when grouped.
basicA 4-variable K-map has how many cells, and how many literals does a group of four cells give?
It has 2^4 = 16 cells. Each doubling of a group removes one variable, so a group of four removes two, leaving a 2-literal term. A group of eight gives one literal, and a single cell keeps all four.
basicWhy can't a K-map group contain three cells?
A group must be one product term, and a product term covers a power-of-two number of cells, because each missing variable doubles the cells it matches. Three cells cannot be described by one term. Cover them with two overlapping groups of two instead.
coreMinimise F(A, B, C) = sum of minterms 0, 2, 4 and 6.
Those minterms are 000, 010, 100 and 110: every pattern where C is 0. A and B take all four combinations, so they drop out, and F = C'. On the map it is a group of four that wraps from the first column to the last.
coreOn a 4-variable map with A, B down the side and C, D across the top, only the four corner cells are 1. What is the minimal expression?
The corners are 0000, 0010, 1000 and 1010. Because the left and right edges touch, and so do the top and bottom, the four corners form one group of four. B and D are 0 throughout while A and C vary, so F = B'D'. Treating them as four separate cells would give four 4-literal terms.
coreF(A, B, C) is 1 for minterms 1, 3 and 7, and minterm 5 is a don't-care. Minimise it with and without the don't-care.
Without it, the best cover is two pairs: 1 with 3 gives A'C, and 3 with 7 gives BC, so F = A'C + BC. Treating 5 as a 1 lets 1, 3, 5 and 7 form a group of four in which only C is constant, so F = C. The don't-care turns two terms and four literals into one literal.
coreYou fill a 4-variable map and get a perfect checkerboard of 1s. What does that tell you?
No two 1s are neighbours, so nothing groups and the sum of products needs all eight minterms: 8 terms and 32 literals. A checkerboard is the signature of parity, since every move to a neighbour flips one input and therefore flips the output. The right circuit is an XOR (or XNOR) of the four inputs, not two-level logic.
advancedA colleague labels the BC columns of a 3-variable map 00, 01, 10, 11. Row A = 0 has 1s in the two middle columns, and they circle them as one pair. What is wrong, and what is the correct expression?
With plain counting order, the middle columns are 01 and 10, which differ in both B and C, so they are not true neighbours and no single term covers them. The two 1s are minterms 1 and 2, giving A'B'C + A'BC', which is A'(B XOR C). In Gray order (00, 01, 11, 10) these cells are not adjacent, and the map would not tempt you to group them.
advancedA flag for 'BCD digit is 5 or more' was minimised with codes 10 to 15 as don't-cares, giving F = A + BD + BC. A reset fault leaves 1100 on the bus. What does the flag show, and what is the lesson?
1100 has A = 1, so F = 1. The minimised logic outputs 1 for every code from 10 to 15, because those don't-cares were absorbed into the A group. A don't-care is a promise that the code never arrives. If an illegal code can appear, through reset, corruption or another block, either remove the don't-care or make sure nothing downstream trusts the flag in that state.