Day 20: K-maps: minimizing logic up to 5 variables
Minimizing logic by hand
Given a truth table, there are many equivalent gate implementations — you want the cheapest. A Karnaugh map (K-map) arranges the truth table so that physically adjacent cells differ in exactly one variable (gray-code ordering). Grouping adjacent 1s into rectangles of size 1, 2, 4, 8… lets you read off a minimal sum-of-products (SOP) expression, each group dropping the variable that changes within it.
F(A,B,C) = 1 for minterms: 1,3,4,5,7
BC=00 BC=01 BC=11 BC=10
A=0 [ 0 1 1 0 ]
A=1 [ 1 1 1 0 ]
Groups: the BC=01/11 column pair (four 1s) -> C is constant 1...
-> term C
the A=1, BC=00/01 pair -> term A * B'
Minimal SOP: F = C + A*B'
(down from up to five product terms in the raw table)Don't-cares are free minimization
When some input combinations can never occur (or you don't care about their output), mark them X. You may include a don't-care in a group if it makes the group *bigger* (cheaper), or exclude it otherwise. Exploiting don't-cares is one of the biggest by-hand wins — and exactly what a synthesis tool does with unreachable states.
Gray code, foreshadowed
K-map cells are ordered so neighbors differ by one bit — that's gray code. The same trick reappears in Stage 2's asynchronous FIFO, where gray-coded pointers cross clock domains safely because only one bit changes at a time. You're meeting a deep idea early.
Key terms
- Karnaugh map
- A gray-code-ordered grid of a truth table where adjacent cells differ in one variable, enabling visual minimization.
- Minterm
- A single input combination for which the function is 1.
- SOP / POS
- Sum-of-products (OR of ANDs) / product-of-sums (AND of ORs) canonical forms.
- Don't-care (X)
- An input combination whose output is unconstrained, usable to enlarge groups for a cheaper result.
- Prime implicant
- A maximal group of 1s that cannot be enlarged; minimal covers are built from these.
Before moving on, you should be able to
In a K-map, why are the rows and columns ordered 00, 01, 11, 10 rather than 00, 01, 10, 11?
