Don't-Care Conditions in Karnaugh Maps

TL;DR: A don’t-care is an input combination whose output value either cannot occur or simply does not matter. On a Karnaugh map, mark it with X and include it in any group that helps you build a larger covering rectangle. The same minimisation rules apply, you just have more cells you are allowed to absorb. Don’t-cares are why BCD-only functions ($1010..1111$ never appear) often shrink to a fraction of the gate count required for a full 4-bit function.

The cleanest way to make a Boolean function smaller is to give the synthesis tool more freedom. Don’t-care conditions are a formal way of saying “I will never give you this input, so produce whatever output is convenient.” On a Karnaugh map, that freedom shows up as cells you can choose to treat as 1 or 0 depending on which choice produces a larger group. Use them well and a function over four variables can collapse from a dozen gates to two.

What is a “Don’t Care”?

A don’t-care input combination is one of two things:

1. Cannot occur. The encoding of the input space restricts some bit patterns. A BCD digit, for example, only takes values 0–9. The patterns 1010 through 1111 never appear at the input. Whatever output the circuit produces for those patterns will never be observed because the patterns never arrive.

2. Output is irrelevant. The pattern can occur, but its output is not used downstream. A circuit might compute “result if input valid” alongside a separate “valid” flag, and downstream logic ignores the result when the flag is low. The function can produce any value when invalid without affecting system behaviour.

Both flavours have the same effect on minimisation: the designer is free to pick whichever output value produces the simpler circuit. On the truth table and K-map, both are written as X (or sometimes $d$) instead of 0 or 1.

The technique sits next to ordinary Karnaugh map and sum-of-products minimisation. Same rules, just an expanded group-construction palette.

Notation on a Truth Table

A truth table for a 4-variable function might look like:

This is the classic “BCD digit ≥ 5” function. The four input bits encode a BCD digit (0–9). Inputs 0–4 produce 0; inputs 5–9 produce 1; inputs 10–15 are invalid BCD and marked X. There is no value of $F$ for $ABCD = 1010..1111$ that the rest of the system will ever observe.

Without exploiting don’t-cares, the minimal SOP is just an enumeration:

Five product terms, and four of them are 4-input ANDs. Now use don’t-cares.

K-Map Without and With Don’t-Cares

Plot the function with $AB$ on rows and $CD$ on columns:

              CD
        00   01   11   10
      +----+----+----+----+
   AB=00|  0 |  0 |  0 |  0 |
      +----+----+----+----+
   AB=01|  0 |  1 |  1 |  1 |
      +----+----+----+----+
   AB=11|  X |  X |  X |  X |
      +----+----+----+----+
   AB=10|  1 |  1 |  X |  X |
      +----+----+----+----+

Treating every X as 0 (no don’t-care exploitation), the function reduces to two prime implicants:

Three terms, average size 3. Better than the unminimised SOP, but still substantial.

Now treat each X as a free 1 wherever it helps make a larger group. Three large groups become available:

• $A$ alone covers the entire $AB=10$ and $AB=11$ rows: cells $1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$. Of those, $1000$ and $1001$ are real 1s, and the rest are don’t-cares treated as 1. The group is an octet; the implicant simplifies to $A$.
• $BC$ alone covers $AB=01$ and $AB=11$ at $CD=11$ and $CD=10$: cells $0110, 0111, 1110, 1111$. Real 1s at $0110, 0111$; don’t-cares at $1110, 1111$. Quad implicant: $BC$.
• $BD$ alone covers $AB=01$ and $AB=11$ at $CD=01$ and $CD=11$: cells $0101, 0111, 1101, 1111$. Real 1s at $0101, 0111$; don’t-cares at $1101, 1111$. Quad implicant: $BD$.

Now combine. The minimal SOP is:

Three implicants, total of five literals. Compared to the don’t-care-free version (three implicants, nine literals) it is roughly 45% smaller; compared to the unminimised form it is dramatically smaller. The synthesised circuit is a 3-input OR with two 2-input ANDs feeding it — and you can build it with two AND gates and one OR gate plus the input wire for $A$.

This is the entire point of don’t-cares: they buy you cheap circuit area for free, by formalising input combinations the system has already excluded.

The K-Map Rules with Don’t-Cares

The minimisation procedure does not change. Only the inputs to it do:

1. Plot the function. Every cell is 0, 1, or X.
2. Form prime implicants. A prime implicant is the largest rectangle of cells containing only 1s and Xs (no 0s). Every group must be a power-of-two size. Wraparound at edges is allowed as usual.
3. Cover every 1. Pick a minimal subset of prime implicants such that every 1-cell is covered by at least one selected group. You do not have to cover X cells. They are free to leave out if they do not help.
4. Read the implicants. Each chosen group is a product term in the SOP.

The only conceptual change from a no-don’t-care K-map is rule 3: an X may be included in a group to make it larger, but it does not need to be covered.

The dual procedure on a product-of-sums layout is symmetric. Group 0s and Xs to form the largest possible rectangles; cover every 0; X cells need not be covered.

A Second Worked Example: BCD Even Detector

The function “the BCD digit is even” produces 1 for inputs 0, 2, 4, 6, 8 and 0 for inputs 1, 3, 5, 7, 9. Inputs 10–15 are don’t-cares.

Truth table for $F$ with $ABCD = 0000..1111$:

Without don’t-cares:

Wait — already trivial? Yes. The LSB of the input is exactly $D$, and “even” simply means $D = 0$. The function is its own minimal form regardless of don’t-cares. Don’t-cares help most when the function is non-trivial over the limited input space; for “even,” the input encoding already does most of the work.

The example illustrates a useful negative result. Don’t-cares are not always profitable. They expand the implicant search space, but they do not change the minimum if no larger group spans real 1s and don’t-cares together.

A Third Worked Example: Detecting BCD Inputs Greater Than 7

Now consider $F = 1$ when the BCD digit is 8 or 9, and 0 otherwise. Inputs 10–15 are don’t-cares.

              CD
        00   01   11   10
      +----+----+----+----+
   AB=00|  0 |  0 |  0 |  0 |
      +----+----+----+----+
   AB=01|  0 |  0 |  0 |  0 |
      +----+----+----+----+
   AB=11|  X |  X |  X |  X |
      +----+----+----+----+
   AB=10|  1 |  1 |  X |  X |
      +----+----+----+----+

Real 1s at $1000, 1001$. With Xs treated as 1 wherever helpful, the row $AB=10$ extends to a quad ($1000, 1001, 1010, 1011$) which simplifies to $A\overline{B}$. The two rows $AB=10$ and $AB=11$ together form an octet ($1000..1111$) which simplifies to just $A$.

Without don’t-cares, the minimum cover is the quad $A\overline{B}$ over the two real 1s and two free 1s in the bottom two columns of the $AB=10$ row. Cost: 2 literals.

With don’t-cares, the minimum is $A$. Cost: 1 literal. A single wire. The circuit has zero gates.

Both answers are correct over the BCD input space. They differ on inputs 1100, 1101, 1110, 1111: $A\overline{B}$ produces 0 there, $A$ produces 1. Both are acceptable because the inputs never arrive.

The Risk: When a Don’t-Care Actually Occurs

The contract is strict. A don’t-care is an input that will never occur. If the input does occur and the circuit produces an unexpected output, the rest of the system is observing a value the designer promised not to care about — but suddenly does.

The classic failure mode is BCD overflow. A BCD adder produces an invalid pattern (1010–1111) before the +6 correction is applied; see the BCD fundamentals post for the full mechanism. If a downstream “BCD digit ≥ 5” detector was built with don’t-cares, and that detector samples between the raw sum and the correction, it will see 1010..1111 and produce whichever value the synthesiser happened to pick. The detector is not broken; the system is.

The defensive options are:

• Treat don’t-cares as 0 when the function is on a critical path and the input space is not 100% guaranteed. Loses the optimisation.
• Add an input validity check that gates the function’s output. Still get the optimisation; pay one extra gate plus one wire.
• Constrain the upstream stage so the don’t-care cases truly cannot reach this point. Costs nothing if the constraint is naturally satisfied by the upstream design.

The first option is the safest and is the standard choice in safety-critical or formally-verified work. The second is the most common in normal RTL. The third applies when the input encoding itself excludes the don’t-care patterns by construction.

Don’t-Cares in Real Design

The pattern shows up in many places:

• BCD circuits. Every Boolean function of a BCD digit has six don’t-cares. The companion BCD-to-7-segment decoder post shows how each segment driver is dramatically simpler when 1010..1111 is treated as don’t-care, often shrinking from 8+ literals per segment to 3–4. Cumulatively the chip is half the size it would be without don’t-cares.
• Encoded one-hot. A one-hot input has one bit set out of $n$. The remaining $2^n - n$ patterns are don’t-cares. Encoders and priority encoders exploit this; see the decoders and encoders post for the conversion direction this enables.
• State machine encodings. A state machine with five states encoded in three bits has three unused codes, each a don’t-care for the next-state and output logic. State minimisation often produces dramatically simpler combinational logic by exploiting them.
• Pipeline bubbles. A pipeline stage with an “invalid” flag produces don’t-cares for every other field when the flag is low. Downstream logic that masks on the flag treats every datum as a don’t-care in the masked case, simplifying any function of those data.

The technique is one of the cheapest performance levers in classical logic minimisation. It is also one of the few that survives unchanged in modern HDL design: a case statement that does not list every input pattern produces don’t-cares for the unlisted patterns, and the synthesiser exploits them automatically.

Where Don’t-Cares Connect to the Rest of Logic Design

Don’t-cares are minimisation-time optimisation. They do not interact with Boolean algebra identities directly — the algebraic equivalences hold regardless of input restriction — but they expand the set of equivalent functions over the restricted input space. A function $F$ that is 1 on inputs $\{0101, 0111, 1000, 1001\}$ and X on $\{1010..1111\}$ is equivalent over the BCD input space to many different Boolean expressions; the minimisation problem is to pick the cheapest.

The technique pairs naturally with De Morgan’s laws for circuit transformations after minimisation: once you have the minimal SOP, De Morgan often lets you convert it to NAND-only form with the same gate count, which is convenient for CMOS. Don’t-cares run before the algebraic transformations.

Build It in the Simulator

A clean exercise: build the BCD "$\ge 5$" detector both ways and compare gate counts.

1. Without don’t-cares. Use a 4-input truth-table component or build the function $F = \overline{A}BD + \overline{A}BC + A\overline{B}\overline{C}$ from gates: three 3-input ANDs, one 3-input OR, plus inverters. Wire four AND gates and one OR gate for a literal-by-literal build.
2. With don’t-cares. Build the function $F = A + BC + BD$. Two AND gates and one 3-input OR, plus the wire $A$.
3. Sweep inputs $0000..1001$ on both circuits and confirm the outputs agree. Then sweep $1010..1111$ and notice the second circuit produces 1 while the first produces 0. Both are correct over the BCD input range.

The size difference is visible at a glance. That is the don’t-care optimisation buying area for free.

What’s Next

Don’t-cares set up the next two posts directly. BCD (binary-coded decimal) fundamentals covers why patterns 1010–1111 are invalid in the first place, including the +6 decimal-adjust step in BCD addition that produces them transiently. BCD-to-7-segment decoder: from numbers to display is the canonical worked example: each segment driver is a Boolean function with six free don’t-cares, and the resulting circuit fits in a fraction of the area a full 4-bit function would need.

For a hands-on follow-up, the pattern of constrained inputs producing dramatic simplification also appears in priority encoders. Building one with the unused-input combinations marked as don’t-cares is the most direct way to feel the technique before moving on to larger combinational designs.