Don't-Care Conditions in Karnaugh Maps

TL;DR: A don’t-care is permission to choose an output value where the system contract does not constrain it. In a K-map, include X cells only when they enlarge a useful group; never cover a required zero in SOP or a required one in POS. The optimization is valid only if the care-set assumption is true at the point of use. An HDL X, an unknown simulation value, and a synthesis don’t-care are not automatically the same thing.

Logic minimization normally preserves a function on every possible input. Don’t-care conditions relax that requirement: selected input/output cases may be assigned either 0 or 1, allowing a smaller implementation over the cases that actually matter.

That freedom can remove literals and gates. It can also remove reset recovery, expose an invalid display pattern, or create a simulation/silicon mismatch if its assumption is wrong. A professional design records three things together:

1. the required on-set, where the output must be 1;
2. the required off-set, where the output must be 0;
3. the don’t-care set, where either result satisfies the system contract.

Two Reasons an Output May Be Unconstrained

1. The input is unreachable

The environment guarantees that a particular input vector cannot reach this logic at a relevant observation time.

A valid BCD digit is in the set 0–9, so 10–15 can be unreachable if:

• the source always produces valid BCD;
• reset and power-up cannot expose another value;
• intermediate transitions are not sampled as digits;
• faults that corrupt the code are outside the design’s required fault model.

“The algorithm never asks for 12” is not sufficient if a four-bit bus can briefly become 1100 while changing between two valid registered values.

2. The input can occur, but this output is unobserved

A pipeline stage may carry arbitrary data while valid=0. If every consumer qualifies the data with that same valid state, the data output is irrelevant during invalid cycles.

This is an observability condition rather than an unreachable input. It remains safe only while no consumer logs, compares, forwards, or otherwise uses the nominally irrelevant field.

Both cases become X cells in a two-valued minimization problem. Their proofs are different, so preserve the reason in the specification.

X Does Not Mean One Universal Thing

The symbol X is overloaded:

• On a K-map, X means “the implementation may choose 0 or 1.”
• In a four-state HDL simulation, X often means “unknown, conflicting, or uninitialized.”
• In a truth-table document, X can mean an input value is irrelevant to that row.
• In a synthesis directive, a tool-specific construct may authorize optimization.

These meanings are not interchangeable.

Assigning 'x in RTL can improve optimization in some flows, propagate unknowns in simulation, be ignored or transformed in another flow, and obscure a real initialization bug. An incomplete combinational assignment may infer a latch instead of a don’t-care. Tool directives such as full_case can also make synthesized behavior differ from simulation; Intel’s documentation explicitly warns about this possibility.

Express intent in a way supported by the target language, simulator, synthesis tool, lint rules, and formal flow. Then verify the synthesized result under the same environmental assumptions.

K-Map Rules

For a minimized sum of products:

1. Plot each cell as required 0, required 1, or X.
2. Form power-of-two rectangles containing only 1s and Xs.
3. Cover every required 1.
4. Never include a required 0.
5. Leave any X unused when it does not improve the cover.
6. Choose a cover according to the actual cost goal: literals, cells, depth, shared terms, or another implementation metric.

For product of sums, apply the dual:

• group required 0s with optional Xs;
• cover every required 0;
• never include a required 1.

Each output may use an X differently. One segment function might choose a given invalid BCD cell as 1 while another chooses it as 0. There is no requirement to assign one global invalid pattern unless the interface specification imposes one.

Worked Example: Valid BCD Digit Is at Least 5

Let A be the BCD MSB and D the LSB. The required behavior is:

• F=0 for digits 0–4;
• F=1 for digits 5–9;
• X for codes 10–15.

Using Gray-code row and column order:

              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

The X cells allow three useful groups:

• both rows with A=1 form an octet, giving A;
• 0110, 0111, 1110, and 1111 give BC;
• 0101, 0111, 1101, and 1111 give BD.

Therefore:

or, factored:

Check the care set:

• digits 0–4 produce 0;
• digits 5–7 satisfy $B(C+D)$;
• digits 8–9 satisfy A.

The expression happens to produce 1 for every invalid code 10–15. That is acceptable only because those rows were explicitly unconstrained.

If invalid codes must produce 0

They are no longer don’t-cares. With F=0 for 10–15, one valid SOP is:

This version preserves the required zero on invalid codes. It is larger because the interface contract is stronger.

A Case Where Don’t-Cares Do Not Help

For a valid BCD digit, “is even” is:

The LSB already encodes parity. Allowing codes 10–15 to be X cannot remove the only literal without changing required values, so the minimum stays the same.

Don’t-cares expand the optimization space; they do not guarantee an improvement.

A Case Where One Literal Disappears

Define F=1 for valid BCD digits 8 and 9 and F=0 for valid digits 0–7.

If invalid codes 10–15 must also produce zero:

Only 1000 and 1001 satisfy the expression.

If 10–15 are don’t-cares, the required ones can be grouped with all six X cells:

Both implementations agree on valid BCD. They intentionally disagree on some invalid inputs.

This correct comparison is important: a design cannot claim “without don’t-cares” while silently using invalid cells to expand a group.

Transient Inputs and Sampling Boundaries

Even if the source and destination registers contain valid codes, combinational bits do not switch simultaneously. A transition from BCD 7 (0111) to 8 (1000) changes four bits and can pass through other electrical combinations.

Whether that matters depends on the boundary:

• A destination register that samples only after the decoder settles may never capture the intermediate result.
• An asynchronous output-enable, write strobe, or clock derived from the minimized logic can react to a transient.
• A multiplexed display may show a short ghost pattern.
• A logic analyzer may reveal values that software never observes.

The unreachable-set proof must therefore state when the output matters, not just which steady-state values software intends.

Registering inputs or outputs, constraining timing, designing hazard-free control, or adding blanking can make the assumption true. Declaring X on a K-map does not.

Invalid States in State Machines

Suppose five states are encoded in three bits. Three codes are unused during normal operation. Optimizing next-state and output logic with those codes as don’t-cares may be reasonable if reset is guaranteed and state corruption is outside scope.

If single-event upset, CDC error, partial reset, or fault injection is in scope, those codes are not irrelevant. The design may need to:

• detect an illegal state;
• suppress hazardous outputs immediately;
• return to reset or another safe state;
• report the fault;
• use an encoding with a required Hamming distance.

FPGA tools offer explicit safe-state mechanisms. AMD Vivado’s FSM_SAFE_STATE, for example, adds invalid-state detection and recovery logic, with an area/performance trade-off. Intel Quartus documentation likewise distinguishes ordinary synthesis from safe-state-machine options.

Do not both optimize illegal states away and claim guaranteed recovery from them. Those are different specifications.

One-Hot and Priority Inputs

An exactly-one-hot $n$-bit interface has n legal vectors and $2^n-n$ other vectors. The zero vector is also legal if the protocol is one-hot-or-zero.

A plain encoder may treat multiple asserted bits as don’t-cares if upstream logic guarantees exact one-hot input. A priority encoder deliberately defines the many-hot rows and therefore cannot treat them as unconstrained. It may still define the code as irrelevant when no request is active, provided a valid output qualifies the code.

That distinction is one reason to document input assumptions at module boundaries rather than infer them from a name such as “encoder.”

Output-Irrelevant Data

Consider:

valid = 0
data  = anything

It is safe to optimize data-dependent downstream logic only when every observable effect is gated:

write_enable = valid AND condition(data)

But even here, physical switching of condition(data) may consume power, create side-channel leakage, or affect timing. “Functionally unobserved” does not necessarily mean “electrically irrelevant.”

For simulation clarity, many teams still assign a deterministic value to invalid data while letting synthesis optimize through explicit constraints or surrounding enables. The best choice depends on the verification and implementation flow.

HDL Guidance

Avoid translating K-map notation directly into casual HDL X assignments.

A conservative combinational pattern defines every output:

always_comb begin
  valid = (bcd <= 4'd9);
  ge_five = 1'b0;
  if (valid)
    ge_five = (bcd >= 4'd5);
end

This specifies invalid behavior as zero. If the project wants invalid inputs to be synthesis don’t-cares, encode that intent with a reviewed, tool-supported mechanism and an accompanying assumption. Examples may include formal input constraints, synthesis attributes, constrained module interfaces, or a technology-specific primitive.

Whichever method is chosen:

• lint for incomplete assignments and unintended latches;
• compare RTL and gate-level behavior where the flow requires it;
• prove equivalence on the care set;
• verify that environmental assumptions hold;
• inspect warnings about unreachable states and case coverage;
• avoid casex or wildcard matching that can hide unknown control bits unless that behavior is specifically intended.

Verification Plan

A don’t-care optimization needs two complementary checks.

Functional equivalence on the care set

For every required input:

At four variables, enumerate the complete truth table. For larger logic, use assertions or formal equivalence with an explicit care-set constraint.

Assumption validation

Prove or test that:

• invalid encodings cannot be sampled when the output matters;
• reset and power-up respect the assumption;
• CDC paths cannot create unsupported combinations;
• fault requirements do not include the “unreachable” set;
• downstream valid gating covers every side effect;
• test and debug modes do not bypass the qualifier.

Testing only the minimized Boolean equation verifies the wrong half of the contract if the environment is what makes X legal.

Build the BCD Example in DigiSim

Construct two digit ≥ 5 detectors:

1. Defined-invalid version: implement $F=\overline A BC+\overline A BD+A\overline B\overline C$.
2. Don’t-care-optimized version: implement $F=A+BC+BD$.
3. Sweep all sixteen inputs.
4. Confirm both match for 0–9.
5. Record their intentional differences for 10–15.
6. Add valid = NOT(A AND (B OR C)) for BCD 0–9 and gate an observable output.
7. Change several input bits together and inspect whether the simulator models intermediate transitions; do not infer analog hazard behavior if it uses ideal simultaneous updates.

The exercise shows the correct bargain: smaller logic in exchange for a narrower behavioral promise.

Review Checklist

Before marking any cell X, ask:

• Why is this output unconstrained: unreachable input or unobserved output?
• At what sampling or observation boundary is that statement true?
• Does reset, CDC, test mode, or fault behavior violate it?
• Is X a K-map permission, an HDL unknown, or a tool directive?
• Must illegal states recover?
• Is the optimized implementation verified on every care-set input?
• Is the assumption itself asserted or proven?

Don’t-cares are not “free gates.” They exchange behavior outside a defined care set for implementation freedom. When the care set is explicit and verified, that is disciplined optimization. When it is merely assumed, it is hidden functionality.

Continue with BCD fundamentals for the encoding contract, BCD-to-seven-segment decoding for a seven-output application, and static and dynamic hazards for transition-time behavior.

References

• AMD Vivado Synthesis: FSM_SAFE_STATE
• Intel Quartus state-machine HDL guidelines
• Intel Quartus full_case synthesis attribute and simulation mismatch warning