Karnaugh maps and the conditions for don't-cares

Connect a truth table to implementation cost

A truth table^{iTruth table A table listing every possible input combination and its output. Changes over time are checked separately with waveforms. Learn more} defines the function; logic minimization chooses an expression to implement it. For three inputs, define minterm numbers by the binary value ABC, with A as the most significant bit.

For example, minterm 4 is ABC=100. The unlisted rows 0, 2 and 6 have output 0. Instead of always implementing five product terms, group terms that differ in only one bit.

A Karnaugh map is a truth table in a different order

Arrange the columns as BC=00, 01, 11, 10. This Gray-code order changes only one bit between adjacent columns. The leftmost and rightmost columns are adjacent too.

Groups must be rectangular and contain $1,2,4,8,\ldots$ cells. Including a 0 cell changes the function. A 1 cell may belong to multiple groups.

1. Group the four cells in the two C=1 columns. The output is 1 regardless of A and B, leaving the term C.
2. Group BC=00 and 01 in the A=1 row. Only C varies, leaving $A\overline B$.
3. OR the two groups: every 1 is covered and every 0 is avoided.

Compare the original definition and simplified expression for all eight inputs. Check separately that the expression is shorter and that its function is unchanged.

The flow below converts the map's two groups into terms. A and B vary in the C group, and C varies in the two-cell group, so those variables are eliminated from the respective terms.

A don't-care grants optimization freedom and assumes an input constraint

Suppose the system contract guarantees ABC=000 never occurs. Marking that cell X allows it to be used as either 0 or 1. Group the four B=0 cells to obtain

The new expression outputs 1 for ABC=000, unlike the original complete truth table. Calling the circuits equivalent therefore requires the condition that the input is never 000. If 000 can occur during initialization or error recovery, this optimization can violate system requirements.

Minimizing an expression is not the same as minimizing a chip

Fewer literals do not always give optimal area, delay and power in a particular standard-cell library. Load, fan-out, available complex gates, wiring and glitches affect the result. At this stage, establish functional equivalence and input assumptions; judge physical cost from synthesis and timing results.

Further reading: MIT OpenCourseWare — Combinational Logic

Lab · Check overlapping groups and don't-care conditions

1. Select the C group. A and B both vary across its four cells, leaving only C.
2. Select A·¬B. It covers m4 and m5, and m5 overlaps the C group. Overlap is allowed; including a 0 cell is not.
3. Press m0 twice, changing 0 → 1 → X. Once it is X, the specification is incomplete and includes d(0). The B=0 group expands, giving $C+\overline B$.
4. Press m0 once more to restore 0. Restoring the original requirement should remove the larger group.

Selecting a group does not change values. The complete expression still covers every 1; the border highlights only the term currently being examined. Here “minimum” first refers to product-term count, then literal count. When several solutions exist, the display shows one of them.