Finite state machines and safe control

Explanation

What an FSM describes

A finite state machine, or FSM, separates a controller into:

1. current state stored in flip-flops;
2. next-state logic using current state and inputs;
3. output logic using state and, for a Mealy machine, inputs.

Begin with behavior, not encoding. Give each state a purpose, define every transition condition, and specify what happens if no condition is true.

Moore and Mealy machines

A Moore output depends only on current state. It normally changes after a clock edge and is easier to reason about at an interface.

A Mealy output depends on current state and current inputs. It can respond within a cycle but may form a longer combinational path or glitch if its inputs are not stable and synchronized.

The same requirement can often use either style. Choose using latency, timing, and interface requirements.

Four useful views

• State diagram: visual states and labeled transitions.
• Transition table: current state plus inputs maps to next state.
• Output table: state and relevant inputs map to outputs.
• Timing sketch: shows cycle-level interaction with the environment.

Each view catches different mistakes. The table is particularly good for exposing a missing input combination.

State encoding

Encoding	State bits for N states	Typical trade-off
Binary	ceil(log2(N))	Few flops, more decode logic
One-hot	N	Simple decode, more flops
Gray	ceil(log2(N)) when sequence permits	One bit changes on selected transitions

Synthesis may choose or optimize an encoding. A safety or CDC requirement can justify controlling it, but the behavioral specification must remain clear regardless of encoding.

Reachability and illegal states

A reachable state can occur from reset through legal inputs. An unreachable state has no legal path, but its encoded bit pattern may still arise from reset release, corruption, debug forcing, or an incomplete implementation.

Define an illegal-state policy such as:

• return to IDLE on the next clock;
• enter a safe ERROR state;
• deassert all actions and report a fault.

Do not rely only on a simulation default branch if synthesis treats the illegal encodings as don't-cares. The coding style and tool constraints must implement the intended recovery.

Lockup, defaults, and priority

An FSM locks up when no exit can occur from a state under circumstances where progress is required. Timeout logic can convert an unbounded wait into a defined error or recovery.

Default assignments in combinational next-state logic should normally hold state and deassert pulse outputs. Explicit conditions then override them. When two conditions are true together, priority must be stated rather than inherited accidentally from source order.

Registered and combinational outputs

A registered output changes only at a clock edge, improving timing isolation and preventing combinational glitches. It adds state or a cycle of latency.

A combinational output can respond in the same cycle. Its delay path includes the input and decode logic. For a signal that crosses a module boundary, document when it becomes valid and how the receiver samples it.

Controller specification checklist

• Reset state and reset polarity
• Inputs and their clock domains
• Every state and its purpose
• Transition priority when conditions overlap
• Output behavior in every state
• Response to illegal state and invalid input
• Maximum wait and timeout behavior
• Whether outputs are registered
• Corner cases at simultaneous events

Worked example

Design a controller that accepts a request, starts an operation, waits for completion, and reports a one-cycle done pulse. It must time out after four waiting cycles.

States:

• IDLE: wait for request.
• BUSY: operation is active; count wait cycles.
• DONE: emit a one-cycle completion pulse.
• ERROR: emit an error indication until clear.

Current state	Condition	Next state	Main action
IDLE	request=0	IDLE	none
IDLE	request=1	BUSY	start operation, clear timer
BUSY	complete=1	DONE	stop operation
BUSY	complete=0 and timer<3	BUSY	increment timer
BUSY	complete=0 and timer=3	ERROR	timeout
DONE	always	IDLE	pulse done
ERROR	clear=0	ERROR	hold error
ERROR	clear=1	IDLE	clear error
illegal	always	ERROR	safe recovery

The table gives complete priority over timeout if both appear on the boundary cycle. That decision must match the requirement. Verification should test request held high, completion on every possible wait cycle, the exact timeout boundary, simultaneous completion and timeout, reset from every state, and injected illegal state.

Derive tests from transitions and decisions

Treat every transition guard and priority choice as something to exercise. For the controller above, a compact regression plan could be:

Check ID	Starting condition and stimulus	Expected result
FSM-01	Assert reset while idle.	State returns to IDLE; operation and error outputs are inactive.
FSM-02	Raise request to enter BUSY, then lower it before returning to IDLE.	One operation starts, and the controller does not restart after completion.
FSM-03	Assert complete before the timeout boundary.	Controller enters DONE, then returns to IDLE with one completion pulse.
FSM-04	Keep complete low through the fourth wait cycle.	Controller enters ERROR at the specified limit.
FSM-05	Assert complete on the same cycle the timer reaches its limit.	Completion wins, as stated in the transition table.
FSM-06	Assert reset in BUSY, DONE, and ERROR.	Each state follows the same reset contract and no stale pulse remains.
FSM-07	Force an unused state encoding in a simulation-only test.	The next active edge follows the documented recovery policy.

The tests check behavior at the decision boundaries, not just whether each state can be visited. Keep state forcing inside verification code; it should not become a functional input or a claim that hardware can be forced this way. If the design changes the timeout or completion priority, revise the table, RTL, and expected checks together.

Check yourself

When can a Mealy output respond sooner than a Moore output? Which table entry documents what happens when completion and timeout occur together?