A binary encoding with n state bits has 2ⁿ possible patterns. An FSM with fewer than 2ⁿ named states leaves some codes unused in its intended operation. Those unused rows can sometimes be marked as don't-cares in next-state K-maps, allowing larger groups and simpler logic. But “unused” is not automatically the same as “impossible,” and an unsafe X can turn a transient fault or illegal state into uncontrolled behavior.
This guide explains the difference between unreachable, unspecified, and don't-care states; works through a five-state, three-bit example; and shows how the optimization changes when recovery is required. It also gives a practical policy for synchronous and safety-sensitive designs. The goal is to use don't-cares where the specification supports them and preserve explicit behavior where the hardware must recover.
Three meanings often confused
Unreachable means a state cannot be entered from reset under the modeled transitions and input assumptions. That is a property that should be proven, not guessed from a designer's intention. Unspecified means the specification does not say what the circuit should do for that row. This may reflect a true don't-care, or it may reveal a missing requirement. Don't-care means the implementation is allowed to choose either output value for that condition because no required behavior depends on it.
An unused code can be reachable after a power-up condition, a bit upset, a partial reset, a scan operation, a clock glitch, or an error in upstream logic. If the design must recover from such a condition, its next-state value is not a don't-care. For example, an unused code might be required to transition to the reset state on the next clock. Treating it as X could let the minimizer select a transition that remains in an illegal cycle or asserts an output that should be safe.
There are also different kinds of X in digital design. A truth-table don't-care grants freedom to select 0 or 1 for a condition. An unknown simulation value can indicate that the simulator cannot determine a signal. Those concepts are not interchangeable. A map X is an optimization permission; a simulator X is information about uncertainty. Mixing them can conceal a bug.
A five-state machine
Suppose a controller has five symbolic states S0 through S4, encoded as 000, 001, 010, 011, and 100. It uses three state bits A,B,C, leaving codes 101, 110, and 111 unused in the nominal sequence. Assume the specified transitions form a cycle S0→S1→S2→S3→S4→S0. For each next-state bit, the state table therefore supplies a required value for the five legal codes.
| Present state | Code ABC | Next state | Next code |
|---|---|---|---|
| S0 | 000 | S1 | 001 |
| S1 | 001 | S2 | 010 |
| S2 | 010 | S3 | 011 |
| S3 | 011 | S4 | 100 |
| S4 | 100 | S0 | 000 |
| unused | 101 | policy required | not implied by table |
| unused | 110 | policy required | not implied by table |
| unused | 111 | policy required | not implied by table |
If the specification only requires correct operation after a valid reset and under fault-free transitions, and you have proven that the three codes cannot occur in that model, the next-state values for those rows may be treated as don't-cares for logic minimization. A K-map can use them as either 0 or 1 to form larger groups. But if the controller must leave any invalid state safely, the table should say where each code goes, and those values must be entered as 0/1 rather than X.
How X cells affect K-maps
In a K-map, an X can be included in a group when it helps cover required 1s, but it does not have to be included. It cannot be used to justify a term that changes a specified 0 into a required 1. For each next-state output bit, legal-state rows receive the value dictated by the next-state column; an unused row receives X only under an approved don't-care policy. Each bit gets its own map because the next code has several Boolean components.
Adding X cells can create larger implicants and reduce the number of literals. That is a real optimization benefit. However, the minimized equations then assign some definite output to every physical input pattern, including codes marked X. The hardware does not output an abstract X. It outputs 0 or 1 for that combination. The minimizer's choice might be favorable, neutral, or unsafe with respect to recovery, even though it satisfies the on-set and off-set constraints used in the map.
Therefore, after minimization, inspect the equations on all unused codes. Decode each code and compute the next-state bits. If the resulting next state is acceptable, the selected don't-care assignment may happen to provide a recovery behavior. If it is not acceptable, either add required rows and remap, or constrain the synthesis process to preserve a safe transition. Do not assume that an X will resolve toward reset or toward the nearest legal state.
Specify recovery behavior
When recovery is required, define it directly. A common policy sends every unused code to the reset state on the next active clock. In the example, codes 101, 110, and 111 would all map to 000. Then those entries are ordinary specified rows in each next-state bit map. The equations may be larger than the unconstrained don't-care minimum, but they now implement the requested self-recovery behavior.
Another policy might send all invalid encodings to a dedicated error state, assert an error output, or enter a safe shutdown state. The correct choice depends on the system. A motor controller may require outputs to de-energize; a protocol controller may need to restart a transaction; a small toy sequence generator may only need to restart at S0. The safe recovery state should be chosen at the system level, not as an accidental side effect of K-map grouping.
Recovery semantics also interact with synchronous reset and output decoding. If output logic is Moore-style and decoded directly from state bits, an invalid code may assert outputs unexpectedly before the next clock takes the machine to reset. To prevent that, define outputs for invalid states as safe values or gate them with an explicit valid-state condition. A next-state recovery equation alone does not guarantee safe outputs during the invalid-state cycle.
Risks of unsafe don't-cares
The main risk is that the assumptions used to justify X cells do not hold in the physical system. A single-bit upset in a register can move the state into an unused code. An asynchronous reset released near a clock edge can leave flip-flops in different values. Scan chains can load arbitrary bit patterns during test. A bug in a state assignment or clocking path can do the same. If any such event is in scope, treating invalid codes as unconstrained can remove the logic needed to recover.
A second risk is output leakage. Suppose an output is minimized using X state rows and becomes true for an invalid encoding. A fault can then activate a control output for one cycle even if the next-state logic returns to a legal state afterward. This matters for write enables, chip selects, safety interlocks, and any signal that triggers an irreversible action. Decode required outputs conservatively or include validity logic when the interface requires it.
A third risk is overclaiming reachability. It is not enough to say “the FSM never goes there” because the listed transitions do not lead there from reset. The proof needs to include all modeled input sequences, reset behavior, and any environmental assumptions. If inputs are asynchronous, filtered, or constrained only by protocol, state the assumptions and verify them at the appropriate boundary.
Prove the reachability assumption
For a small FSM, reachability can be checked by enumerating states from reset. Start with the reset code, apply every legal input combination to find successor codes, and repeat until no new code appears. If the traversal visits only the named states, the remaining codes are unreachable in that finite-state model. For machines with inputs, include each input combination or a justified constraint; omitting a possible input can make the proof invalid.
For a larger FSM, use formal properties or model checking to establish that the state register remains within the legal set after reset. A typical invariant says “if reset has completed, the state code is one of the legal encodings.” That invariant should be checked against the implemented next-state logic, not only the intended diagram. Separately verify recovery from illegal codes if the product requirements demand it; invariant proof under fault-free behavior does not prove fault recovery.
Simulation can exercise transitions and fault injection, but it usually samples only selected sequences. Formal verification can cover all modeled combinations, subject to the correctness of assumptions and abstraction. Neither method excuses an ambiguous requirement. First specify what should happen from invalid codes; then choose whether those rows are constrained or free.
A safe decision process
- List the unused codes. Do this after fixing state encoding.
- Ask whether each code can occur. Consider reset, fault, scan, asynchronous behavior, and external inputs.
- Define required recovery. Specify the next state and output behavior when recovery is in scope.
- Mark X only for true don't-cares. Document the assumption that permits freedom.
- Minimize each output bit. Use don't-care cells only where they reduce a valid expression.
- Inspect the chosen X assignments. Compute actual next states and outputs for every invalid code.
- Verify the assumption and implementation. Use reachability proof, fault injection, or formal properties as appropriate.
When documenting the map, distinguish the symbols clearly: 1 means required asserted output, 0 means required deasserted output, and X means the specification allows either. A blank cell should not be silently interpreted as X. Record the reason for each X, such as “unreachable after reset under the one-hot transition invariant,” and keep that explanation with the design review.
Design takeaway
Unused state codes are opportunities for simplification only when their behavior truly does not matter. They may be unreachable in the nominal model, yet still be relevant under faults or system startup. A Boolean minimizer will exploit every X it is given; it cannot infer whether a particular implementation choice is safe for the controller.
Use X cells when the specification grants freedom and the reachability assumptions are verified. Define recovery transitions and safe outputs when illegal states must be handled. Then inspect the minimized equations on every code and verify both normal operation and the failure behavior that the system requires. That makes the K-map an optimization tool within a clear design contract.