Karnaugh maps
Reading the simplest circuit off a table
A Karnaugh map is a truth table rearranged into a grid where adjacent cells differ in a single input bit. Circling the groups of 1s by eye yields the minimal AND-OR expression, a correct circuit with fewer gates than the raw table.
A truth table tells you a function completely, and the sum-of-products trick turns it straight into gates: one AND term per
1 row, all ORed. But that is often not the simplest circuit. Many terms share inputs and could be merged. A Karnaugh map (K-map) is a way to spot those merges by eye, so you build the same function with fewer gates. It is the practical end of the Gates group: design a gate, then shrink it. The Karnaugh map solver does the merging for you, for 2 to 4 variables.The trick: order the rows so neighbors differ by one bit
Two product terms combine when they differ in exactly one variable:
A·B + A·B' = A (the B cancels, by the identity B + B' = 1). A K-map makes those pairs *visually adjacent*. It is the truth table redrawn as a grid whose rows and columns are labelled in Gray code, an ordering where each step flips only one bit: 00, 01, 11, 10. Because of that ordering, any two cells next to each other (including wrapping around the edges) differ in a single variable, so a block of adjacent 1s is a term with those shared variables and the differing ones cancelled.Gray-code labelling is the whole point, so do not label the axes
00, 01, 10, 11. Use 00, 01, 11, 10, so stepping one cell changes one bit. Adjacency (in the grid and around the wrap-around edges) is what lets you read merged terms straight off the picture.Worked example: the majority function
Take
F(A,B,C) that is 1 when at least two of the three inputs are 1 (the *majority* vote, which is exactly the carry-out of a full adder). Its truth table:| A | B | C | F |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |
F is 1 in the four rows with two or more 1s. The raw sum of products has four 3-input AND terms, one per 1 row.Drawn as a K-map with
A selecting the two rows and BC (Gray-ordered 00,01,11,10) selecting the four columns, the four 1s fall into three overlapping 2-cell groups. A group of two cells cancels its one differing variable and leaves a 2-input AND:- The pair where
B=1, C=1(bothAvalues) cancelsA, leaving the termB·C. - The pair where
A=1, C=1(bothBvalues) cancelsB, leavingA·C. - The pair where
A=1, B=1(bothCvalues) cancelsC, leavingA·B. - OR the three groups:
F = A·B + B·C + A·C. Four 3-input ANDs became three 2-input ANDs.
F = A·B + B·C + A·C (1 exactly when two or more inputs are 1)
That is the carry-out of a full adder: a carry happens precisely when at least two of
A, B, CIN are 1. The K-map just handed you the minimal AND-OR circuit for it. Grouping 1s, not grinding algebra, is the fast way to a small circuit, and bigger maps (four variables, 16 cells) work the same way: find the largest power-of-two blocks of 1s and read off each block's surviving variables.The minimized expression below is built from three AND gates feeding an OR. Open it in the lab and check it against the table: it should be
1 exactly in the rows with two or three 1s.F = A·B + B·C + A·C from a Karnaugh map: three 2-input ANDs ORed together. Open it in the lab and sweep all eight input rows; F is high whenever at least two inputs are high, the full adder's carry logic.Try it
A 2-variable K-map for
F(A,B) has 1s in the cells A=0,B=1 and A=1,B=1 (the whole B=1 column), and 0s elsewhere. Group the 1s into the largest block and read off the minimal expression for F.Answer
Both
1s sit in the B=1 column and differ only in A, so they form one block of two. The differing variable A cancels, leaving just F = B. Sum of products from the table would have given A'B + AB; the K-map collapses it to a single wire, F = B. That is the whole point: fewer gates for the same function.Rules of thumb for grouping: make blocks as large as possible (bigger block = fewer surviving variables = smaller term), blocks must be a power of two in size (1, 2, 4, 8) and rectangular, blocks may overlap and wrap around the map's edges, and you only need enough blocks to cover every
1. Cover the 0s instead and you get the minimal circuit for NOT F.Don't-care conditions: cells you are free to choose
Sometimes a row of the truth table can never happen, or its output genuinely does not matter. When an input combination cannot occur, nothing forces its output to
0 or 1, so you write an X (a don't-care) in that cell of the map instead of a fixed value. The payoff is real: when you circle groups, you may read each X as whichever value, 0 or 1, lets you draw a bigger block. Bigger blocks cancel more variables, so free cells turn straight into a simpler circuit. A common source of impossible inputs is a code that does not use all its bit patterns: binary-coded decimal stores one digit 0 to 9 in four bits, so the six patterns 1010 through 1111 (decimal 10 to 15) are never valid, and whatever a circuit does for them is irrelevant.Worked example: segment e of a seven-segment display
A seven-segment display decoder turns a 4-bit BCD digit into the seven bars
a to g of a numeral. Take segment e, the lower-left bar. Reading how each digit is drawn, e is lit only for 0, 2, 6, and 8 (the numerals whose shape needs that lower-left stroke). Writing the input as the four BCD bits D3 D2 D1 D0 (weights 8 4 2 1, the same labelling as in BCD), the full 16-row table carries real outputs for the ten valid digits and don't-cares for the six impossible codes:| D3 | D2 | D1 | D0 | e |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | X |
| 1 | 0 | 1 | 1 | X |
| 1 | 1 | 0 | 0 | X |
| 1 | 1 | 0 | 1 | X |
| 1 | 1 | 1 | 0 | X |
| 1 | 1 | 1 | 1 | X |
e over all sixteen input patterns. It is 1 for the digits 0, 2, 6, 8 and 0 for the other valid digits. The six rows 1010 to 1111 (decimal 10 to 15) are not valid BCD, so their output is a don't-care, marked X.Lay these out on a four-variable K-map with
D3 D2 choosing the row and D1 D0 choosing the column, both Gray-ordered 00, 01, 11, 10. The four real 1s land in the top half of the map, and the whole bottom block of Xs (all six invalid codes) sits ready to be borrowed. Watch how much the don't-cares are worth by minimizing the map twice.Ignoring the X's: a bulkier circuit
First treat every
X as a plain 0, so only the four real 1s may be grouped. The best you can do is two pairs, and no pair can grow into a block of four (each would need a neighbour that is stuck at 0):- The pair
2(0010) and6(0110) differ only inD2, soD2cancels and the term isD3'·D1·D0'. - The pair
0(0000) and8(1000) differ only inD3, soD3cancels and the term isD2'·D1'·D0'. - Those two pairs already cover all four
1s, so OR them together. The result needs two 3-input ANDs and reads all four input bits.
e = D3'·D1·D0' + D2'·D1'·D0' (X read as 0: two 3-input ANDs, six literals)
Using the X's: a smaller circuit
Now read each don't-care as whatever grows a block. Borrowing the
Xs at 1010 and 1110 lets each pair expand into a full block of four:- The column
D1 = 1, D0 = 0now holds four1s:2,6, and the borrowed don't-cares1010and1110. A block of four cancels bothD3andD2, leaving justD1·D0'. - The block
D2 = 0, D0 = 0holds0,2,8, and the don't-care1010, all1. It cancelsD3andD1, leavingD2'·D0'. - OR the two blocks. The result needs only two 2-input ANDs, and
D3has dropped out of the logic entirely.
e = D1·D0' + D2'·D0' = D0'·(D1 + D2') (X's used: two 2-input ANDs, four literals, no D3)
Same segment, same ten valid digits, two very different circuits. Ignoring the free cells gave two 3-input ANDs over all four inputs; using them gave two 2-input ANDs over just three inputs, and
D3 vanished. Both light e for exactly 0, 2, 6, 8 and leave it dark for the rest (check 6 = 0110: D0' = 1 and D1 = 1, so e = 1; check 9 = 1001: D0' = 0, so e = 0). The don't-cares changed nothing a real BCD digit can observe, and paid off in fewer, smaller gates and one less input wire. That is the whole value of an X: a group you were going to draw anyway gets to grow for free.Common mistakes with don't-cares. An
X is a choice you make per group, not a global setting: you only commit a don't-care cell to 1 when a group you actually draw happens to cover it, and every other X can stay 0. Never draw a block made only of Xs: that spends a gate covering inputs you do not care about and grows the circuit for nothing. And mark a cell X only when the input truly cannot occur or the output genuinely does not matter; if your spec fixes an output for those codes (a real decoder chip might force segment e off for 1010 to 1111), they are ordinary 0s and 1s, not free.e = D1·D0' + D2'·D0', the circuit the don't-cares bought: two ANDs feeding an OR. Because D3 dropped out, only three inputs are wired. Open it in the lab and confirm e is high exactly when D0 = 0 and (D1 = 1 or D2 = 0), which lights it for the valid digits 0, 2, 6, and 8.Try it
In the segment
e map, the cell for input 1010 (decimal 10) is a don't-care. In the minimized answer e = D1·D0' + D2'·D0', is that cell effectively read as 1 or 0, and why is that the right call?Answer
It is read as
1. Cell 1010 has D1 = 1, D0 = 0, so it sits inside the block D1·D0', and it also has D2 = 0, D0 = 0, so it sits inside D2'·D0' too. Both blocks you drew already contain it, and covering it is exactly what let each of them grow from a pair into a group of four (the growth that dropped a literal from each term). Since a BCD digit is never 1010, segment e's value there can never be observed, so reading it as 1 costs nothing and buys the smaller circuit. Read it as 0 instead and both groups shrink back to pairs, forcing the bulkier version with two 3-input ANDs.You now have the full gate-design loop: write a truth table, shrink it with a K-map, and realize it with the CMOS recipe. That is everything the Arithmetic group needs. Next you spend these gates on real computation, starting by adding two bits in the half adder.
Frequently asked
What is a Karnaugh map?
A Karnaugh map (K-map) is a truth table rearranged into a grid where adjacent cells differ in a single input bit. Circling the groups of
1s by eye yields the minimal AND-OR expression, a correct circuit with fewer gates than the raw sum of products.How does a Karnaugh map simplify a boolean expression?
Two product terms combine when they differ in exactly one variable (
A·B + A·B' = A, the differing variable cancels). A K-map labels its axes in Gray code (00, 01, 11, 10) so that adjacent cells differ by one bit, which makes those mergeable pairs visually adjacent. A block of adjacent 1s is then one term with the differing variables already cancelled.Why must Karnaugh map axes use Gray code instead of binary order?
Gray-code labelling (
00, 01, 11, 10) is the whole point: each step flips only one bit, so any two neighboring cells (including the wrap-around edges) differ in a single variable. Label the axes in plain binary order (00, 01, 10, 11) and adjacency no longer means a one-bit difference, so you cannot read merged terms off the picture.What are the rules for grouping 1s in a Karnaugh map?
Make blocks as large as possible (bigger block = fewer surviving variables), each block must be a power of two in size (1, 2, 4, 8) and rectangular, blocks may overlap and wrap around the edges, and you only need enough blocks to cover every
1. Cover the 0s instead and you get the minimal circuit for NOT F.What is a don't-care condition in a Karnaugh map?
A don't-care is an input combination whose output you are free to choose, either because that input can never occur or because nobody cares what the output is for it. You mark it
X on the map and read each X as whichever value, 0 or 1, lets you draw a larger group, since bigger groups cancel more variables and yield fewer, smaller gates. For example, a BCD input never uses the codes 1010 to 1111, so a seven-segment segment's output for those six patterns is a don't-care that helps minimize its logic.Every lesson here builds toward one thing: a working CPU, from the transistor up.
Open the free lab →