# 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.

Group: Gates
URL: https://digiwleea.wleeaf.dev/learn/karnaugh/

A [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/) 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](https://digiwleea.wleeaf.dev/learn/nand/) group: design a gate, then shrink it. The [Karnaugh map solver](https://digiwleea.wleeaf.dev/tools/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](https://digiwleea.wleeaf.dev/learn/boolean-algebra/) `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 `1`s is a term with those shared variables and the differing ones cancelled.

> **TIP:** 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](https://digiwleea.wleeaf.dev/learn/fulladder/)). 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 |

_Majority of three: 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 `1`s fall into three overlapping 2-cell groups. A group of two cells cancels its one differing variable and leaves a 2-input AND:

1. The pair where `B=1, C=1` (both `A` values) cancels `A`, leaving the term `B·C`.
2. The pair where `A=1, C=1` (both `B` values) cancels `B`, leaving `A·C`.
3. The pair where `A=1, B=1` (both `C` values) cancels `C`, leaving `A·B`.
4. 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)
```

> **KEY:** That is the **carry-out** of a [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/): 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 `1`s, 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 `1`s and read off each block's surviving variables.

The minimized expression below is built from three [AND](https://digiwleea.wleeaf.dev/learn/and/) gates feeding an [OR](https://digiwleea.wleeaf.dev/learn/or/). Open it in the lab and check it against the table: it should be `1` exactly in the rows with two or three `1`s.

_Circuit diagram: The minimized majority function 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._

**Q (Try it):** A 2-variable K-map for `F(A,B)` has `1`s in the cells `A=0,B=1` and `A=1,B=1` (the whole `B=1` column), and `0`s elsewhere. Group the `1`s into the largest block and read off the minimal expression for `F`.

**A:** Both `1`s 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.

> **TIP:** 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 `0`s 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](https://digiwleea.wleeaf.dev/learn/truth-tables/) 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](https://digiwleea.wleeaf.dev/learn/bcd/) 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](https://digiwleea.wleeaf.dev/learn/seven-segment/) 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](https://digiwleea.wleeaf.dev/learn/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 |

_Segment 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 `1`s land in the top half of the map, and the whole bottom block of `X`s (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 `1`s 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`):

1. The pair `2` (`0010`) and `6` (`0110`) differ only in `D2`, so `D2` cancels and the term is `D3'·D1·D0'`.
2. The pair `0` (`0000`) and `8` (`1000`) differ only in `D3`, so `D3` cancels and the term is `D2'·D1'·D0'`.
3. Those two pairs already cover all four `1`s, 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 `X`s at `1010` and `1110` lets each pair expand into a full block of four:

1. The column `D1 = 1, D0 = 0` now holds four `1`s: `2`, `6`, and the borrowed don't-cares `1010` and `1110`. A block of four cancels both `D3` and `D2`, leaving just `D1·D0'`.
2. The block `D2 = 0, D0 = 0` holds `0`, `2`, `8`, and the don't-care `1010`, all `1`. It cancels `D3` and `D1`, leaving `D2'·D0'`.
3. OR the two blocks. The result needs only two 2-input ANDs, and `D3` has 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.

> **WARN:** **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 `X`s: 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 `0`s and `1`s, not free.

_Circuit diagram: The minimized segment 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._

**Q (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?

**A:** 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.

> **KEY:** You now have the full gate-design loop: write a [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/), shrink it with a K-map, and realize it with the [CMOS recipe](https://digiwleea.wleeaf.dev/learn/designing-gates/). That is everything the [Arithmetic](https://digiwleea.wleeaf.dev/learn/halfadder/) group needs. Next you spend these gates on real computation, starting by adding two bits in the [half adder](https://digiwleea.wleeaf.dev/learn/halfadder/).

### FAQ

**Q:** What is a Karnaugh map?

**A:** 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 `1`s by eye yields the minimal AND-OR expression, a correct circuit with fewer gates than the raw [sum of products](https://digiwleea.wleeaf.dev/learn/truth-tables/).

**Q:** How does a Karnaugh map simplify a boolean expression?

**A:** 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 `1`s is then one term with the differing variables already cancelled.

**Q:** Why must Karnaugh map axes use Gray code instead of binary order?

**A:** 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.

**Q:** What are the rules for grouping 1s in a Karnaugh map?

**A:** 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 `0`s instead and you get the minimal circuit for `NOT F`.

**Q:** What is a don't-care condition in a Karnaugh map?

**A:** 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](https://digiwleea.wleeaf.dev/learn/bcd/) input never uses the codes `1010` to `1111`, so a [seven-segment](https://digiwleea.wleeaf.dev/learn/seven-segment/) segment's output for those six patterns is a don't-care that helps minimize its logic.