Finite-State Machine Design

Introduction and Context

Many digital systems must respond differently to the same input depending on what has happened previously. A network controller may accept a packet only after a valid header has been received; a traffic-light controller changes phase according to elapsed time and sensor inputs; a serial receiver interprets a bit according to its position in a frame. Such systems cannot be described adequately by combinational logic alone because their outputs depend on stored history.

A finite-state machine (FSM) is a synchronous sequential model in which the system can occupy one of a finite number of states. At each active clock edge, the next state is determined by the present state and input values. Outputs are generated from the present state, or from both the present state and current inputs, depending on the machine model.

FSM design is central to digital electronics, processor control units, communication interfaces, bus arbitration, vending machines, access-control systems, and protocol implementation. The design process normally includes specification, state modelling, state reduction, state assignment, logic derivation, implementation, and verification.

Learning Objectives

After studying this chapter, you should be able to:

• explain the structure and operation of a finite-state machine;
• distinguish Moore and Mealy machines;
• construct state diagrams and state tables;
• perform state assignment and state reduction;
• derive next-state and output logic;
• implement an FSM using flip-flops and combinational gates;
• identify timing, reset, unused-state, and hazard issues;
• verify an FSM for a controller or communication protocol.

1. The FSM Model

An FSM consists of:

1. a finite set of states;
2. a set of input symbols or input combinations;
3. a set of output symbols or output combinations;
4. a next-state function;
5. an output function;
6. a clock and usually a reset mechanism.

For a synchronous machine, let:

• X be the input vector;
• Q be the present-state vector;
• Q^+ be the next-state vector after the next active clock edge;
• Z be the output vector.

The general model is:

Here, δ is the transition function and λ is the output function. In a Moore machine, output depends only on the present state:

In a Mealy machine, output depends on both present state and input:

These equations describe logical relationships, not propagation delays. In a practical circuit, flip-flops store Q, while combinational logic calculates Q^+ and Z.

Clocked Operation

At time between clock edges, the present state is held by the state registers. The combinational next-state network evaluates the current state and inputs. At the active edge, the flip-flops capture the next-state values. Therefore, a design must satisfy setup time, hold time, and clock-to-output timing requirements.

A simplified timing requirement is:

where t_clk is the clock period, t_cq is flip-flop clock-to-output delay, t_comb is maximum combinational delay, t_setup is receiving-flip-flop setup time, and t_skew represents clock skew. This relation assumes a single synchronous clock domain and excludes additional margins such as jitter and design guard bands.

2. State Diagrams and State Tables

A state diagram represents states as circles and transitions as directed arrows. A transition label specifies the input condition and, where applicable, the output. A state table lists every relevant combination of present state and input and gives the corresponding next state and output.

For a binary input X, a complete machine must define behaviour for both X=0 and X=1 in every reachable state. “Don't-care” entries may be used only when an input combination is genuinely impossible or when a safe implementation has been separately specified.

A diagram is useful for understanding sequencing; a table is usually better for systematic logic derivation and verification.

Figure: Example Mealy state diagram for detecting the bit sequence 101, with output 1 when the final 1 is received.

3. Moore and Mealy Machines

Moore Machines

A Moore machine assigns an output to each state. State labels are commonly written as S_i/Z. Output changes only after a state transition is registered, so Moore outputs are usually easier to synchronize and less vulnerable to input glitches.

Advantages include clear output timing, simpler output interpretation, and reduced sensitivity to combinational input changes. The main disadvantage is that an additional state may be required to represent an output condition, and the output may appear one clock cycle later than in an equivalent Mealy design.

Mealy Machines

A Mealy machine places output values on transitions. A label is commonly written as X/Z. It can respond during the transition associated with an input and often uses fewer states. However, because the output depends directly on inputs, an input transition or hazard can affect the output between clock edges. Registered outputs or carefully constrained synchronous inputs are often used in practical designs.

The two models are computationally equivalent: a Moore machine can represent any Mealy behaviour, although possibly with more states, and vice versa under appropriate state transformation.

4. A Systematic FSM Design Procedure

Step 1: Specify the Behaviour

Describe inputs, outputs, clocking, reset polarity, initial condition, and illegal conditions. State whether outputs must be registered, whether overlapping sequences are permitted, and what happens after reset.

Step 2: Identify Distinct Situations

A state should represent all historical information needed to determine future behaviour. Avoid creating a state merely for a physical component or a verbal phrase; create it because the future response differs.

Step 3: Draw the State Diagram

Start with the reset state. Add transitions for every meaningful input condition. Confirm that each state has a defined response to every input combination.

Step 4: Construct the State Table

List present states, input combinations, next states, and outputs. This table becomes the principal reference for implementation and test planning.

Step 5: Reduce Equivalent States

Two states are equivalent if no possible future input sequence can distinguish their output behaviour. Reduction decreases hardware and can simplify verification.

Step 6: Assign Binary Codes

If there are N states, the number of binary state bits required is:

where m is the number of flip-flops. This assumes binary state encoding and enough codes to represent all states. If N is not a power of two, unused codes exist.

Step 7: Derive Logic Equations

Use the selected flip-flop type and state assignments to derive next-state and output equations. Karnaugh maps or Boolean algebra may be used for simplification.

Step 8: Implement and Verify

Implement the state register, next-state logic, output logic, reset, and any input synchronizers. Simulate normal, boundary, reset, illegal, and timing-related cases.

5. State Reduction and Assignment

State Equivalence

For a Moore machine, two states can be candidates for equivalence only if they have identical outputs. Their next states must also lead to equivalent states for every input combination. For a Mealy machine, the transition outputs must match for every input, and the destination states must be equivalent.

A practical partition-refinement method is:

1. partition states according to output values;
2. compare the destination partition for each input combination;
3. split any partition whose states differ;
4. repeat until no further split occurs.

The final partitions identify equivalent states.

State Assignment

Common encodings include:

• Binary encoding: uses approximately the minimum number of flip-flops;
• one-hot encoding: uses one flip-flop per state, often simplifying FPGA logic;
• Gray encoding: adjacent transitions differ by one bit, potentially reducing switching activity;
• output-based encoding: attempts to make output logic simple.

No encoding is universally best. Binary encoding is economical in flip-flops, while one-hot encoding can be fast and easy to decode in programmable logic. The technology, number of states, timing target, power budget, and synthesis tool all influence the choice.

6. Worked Example: Serial Sequence Detector

Design a Mealy machine that produces Z=1 whenever the serial input stream contains the sequence 101. Overlapping sequences are allowed.

Let the input be X. Define:

• S₀: no useful suffix has been received;
• S₁: the most recent useful suffix is 1;
• S₂: the most recent useful suffix is 10.

The transitions are:

The transition from S₂ on input 1 detects 101. It returns to S₁ rather than S₀ because the final 1 may begin another overlapping sequence.

Assign binary codes S₀=00, S₁=01, and S₂=10. Let the state bits be Q₁Q₀. The next-state table gives:

State 11 is unused. A robust implementation should force it to a legal state, usually 00, rather than treating it as an uncontrolled don't-care.

Using D flip-flops, the D inputs equal the next-state functions. From the table, one valid simplified implementation is:

These equations are valid for the specified assignment and the legal-state transitions. The equation for D₁ is asserted only in state 01 with input 0, which moves the machine to 10. The output is asserted only in state 10 with input 1.

A test stream 110101 produces detection outputs as follows, assuming initial state S₀:

The two asserted outputs correctly identify the two overlapping occurrences of 101.

7. Implementation Considerations

Flip-Flop Selection

D flip-flops are often convenient because each D input is directly the desired next-state bit. JK and T flip-flops may be useful when excitation equations simplify toggling behaviour. For a T flip-flop:

where ⊕ denotes exclusive OR. This equation states that the flip-flop toggles exactly when the present and next values differ.

Reset and Initialisation

A reset establishes a known state, commonly the idle or safe state. The design must specify whether reset is synchronous or asynchronous. Synchronous reset is sampled at the clock edge; asynchronous reset can change the state immediately but requires careful release to avoid metastability or recovery/removal violations.

Unused States

With m state bits and N valid states, the number of unused binary codes is:

Unused states should be assigned safe recovery transitions. In a communication controller, recovery may return to idle; in a safety controller, outputs should first enter a nonhazardous condition.

Input Synchronisation

An external asynchronous input must not be connected directly to ordinary synchronous FSM logic. A synchronizer, commonly two cascaded flip-flops, reduces the probability that metastability propagates into the machine. Synchronization adds latency and does not replace protocol-level debouncing or filtering.

Moore versus Mealy Output Hazards

Combinational Mealy outputs can glitch if input and state signals do not change simultaneously. A control signal that drives a register enable, memory write, or bus grant should generally be registered or otherwise designed with explicit timing constraints. Moore outputs are not automatically hazard-free, but their dependence on registered state usually makes timing easier to control.

8. Verification of FSMs

Verification should compare implementation behaviour with the specification, not merely check that simulation completes.

Important techniques include:

• State-transition coverage: every state and transition is exercised;
• input-condition coverage: each relevant input combination is tested;
• reset testing: reset is applied at startup and, where permitted, during operation;
• boundary testing: inputs change near transitions and protocol limits;
• illegal-state testing: unused encodings are forced or reached in simulation;
• assertions: properties such as “a grant is never given to two requesters simultaneously” are checked;
• formal equivalence: an optimized implementation is compared with a reference model.

For a protocol controller, useful properties include eventual response to a valid request, rejection of malformed sequences, mutual exclusion, bounded waiting time, and safe behaviour after timeout.

9. Applied Case: Ethernet-Style Frame Reception Controller

Background

Consider an illustrative receiver that accepts a simplified frame consisting of a start marker, a fixed payload of four bytes, and an end marker. The controller must ignore noise while idle, collect exactly four payload bytes, report success only when the end marker is valid, and report an error if the marker is incorrect.

Problem

A direct collection of independent control signals can produce contradictory actions—for example, incrementing the byte counter after an error or accepting a frame without a start marker. An FSM makes the permitted sequence explicit.

Analysis and Approach

Use the following Moore states:

• IDLE: waiting for a start marker;
• RECEIVE: accepting payload bytes and incrementing a counter;
• CHECK: examining the end marker;
• DONE: issuing a one-cycle successful-frame indication;
• ERROR: issuing a one-cycle error indication.

The transition policy is:

• IDLE + valid start → RECEIVE;
• IDLE + anything else → IDLE;
• RECEIVE + fewer than four bytes → RECEIVE;
• RECEIVE + fourth byte → CHECK;
• CHECK + valid end marker → DONE;
• CHECK + invalid end marker → ERROR;
• DONE or ERROR → IDLE.

The byte counter is datapath logic controlled by the FSM. Separating the control FSM from the payload register and counter improves modularity: the FSM determines when actions occur, while the datapath stores and counts data.

Outcome

The controller guarantees that success can occur only after a complete four-byte payload and a valid end marker. A malformed frame returns to IDLE through ERROR, preventing stale data from being reported as a valid frame.

Learning Points

1. State definitions should capture protocol history, not merely physical signals.
2. Counters and registers often belong to a datapath controlled by the FSM.
3. Error and timeout transitions must be specified explicitly.
4. One-cycle DONE and ERROR states make output timing unambiguous.
5. Verification should include truncated frames, extra bytes, noise, and reset during reception.

10. Challenges, Limitations, and Best Practices

FSMs are excellent for finite control behaviour, but very large machines can become difficult to read, verify, and maintain. A controller with many independent counters, data fields, and exceptions may be better represented as a hierarchical FSM, a microprogrammed controller, or a processor executing firmware.

Best practices include:

• write the behavioural specification before coding;
• use meaningful state names;
• define reset and illegal-state recovery;
• separate control logic from datapath logic;
• avoid unintended latches by assigning every combinational output and next-state signal;
• register outputs that require clean synchronous timing;
• synchronize external inputs;
• use enumerated state types in HDL where supported;
• review synthesized logic rather than trusting only the source description;
• verify both normal operation and fault recovery.

Hardware-description-language synthesis tools can automatically minimize logic and select implementation resources. However, synthesis optimization does not correct an incomplete specification. AI-assisted HDL generation may help draft state tables or test cases, but engineers must review state completeness, reset semantics, clock-domain crossings, security properties, and safety consequences.

Chapter Summary

A finite-state machine models sequential behaviour using a finite set of states, inputs, outputs, a transition function, and an output function. Moore outputs depend only on state, whereas Mealy outputs depend on state and input. State diagrams provide an intuitive behavioural view, while state tables support systematic implementation.

A reliable FSM design process begins with an unambiguous specification, identifies states that preserve relevant history, defines complete transitions, reduces equivalent states, assigns codes, derives next-state and output logic, and verifies normal and abnormal behaviour. Binary, one-hot, and Gray encodings offer different trade-offs. Practical designs must address reset, unused states, metastability, timing, glitches, and verification coverage. FSMs are especially effective for controllers and communication protocols when combined with counters, registers, and datapath logic.

Key Terms

Finite-state machine: A sequential model with a finite number of states.

State: A stored representation of relevant system history.

Present state: The state currently held by the state register.

Next state: The state captured at the next active clock edge.

Transition: A change from one state to another under an input condition.

State diagram: A graphical representation of states and transitions.

State table: A tabular representation of present state, inputs, next state, and outputs.

Moore machine: An FSM whose output depends only on present state.

Mealy machine: An FSM whose output depends on present state and input.

State assignment: The process of assigning binary codes to symbolic states.

State reduction: Removal or merging of equivalent states.

One-hot encoding: An encoding using one flip-flop for each state.

Unused state: A binary state code not assigned to a valid symbolic state.

Next-state logic: Combinational logic that calculates the state to be captured.

Output logic: Logic that generates FSM outputs.

Metastability: An uncertain temporary flip-flop condition caused by setup or hold violation.

Synchronizer: Circuitry used to safely transfer an asynchronous signal into a clock domain.

State recovery: Defined behaviour that returns an FSM from an illegal state to a legal state.

Protocol controller: An FSM that enforces the permitted sequence of communication events.

Review Questions

Short Answer Questions

1. What information is represented by the state register in an FSM?
2. State one fundamental difference between Moore and Mealy machines.
3. Why is a state table useful during FSM implementation?
4. What is the purpose of a reset state?
5. Why should asynchronous external inputs be synchronized before entering an FSM?

Long Answer Questions

1. Explain the complete FSM design procedure from behavioural specification to verification.
2. Compare binary, one-hot, and Gray state assignments, including their practical trade-offs.
3. Explain state equivalence and describe a partition-refinement method for state reduction.
4. Discuss timing and hazard considerations in Moore and Mealy output implementations.
5. Describe how an FSM and datapath cooperate in a communication-frame receiver.

Analytical / Application Questions

1. Design a Mealy FSM that detects the overlapping sequence 1101. Define the states, transitions, and output condition.
2. An FSM has 13 valid states. Determine the minimum number of binary state flip-flops and the number of unused binary codes. Explain how unused states should be handled.
3. A protocol controller sometimes asserts a write signal for less than one clock period when an input changes. Identify the likely design problem and propose two corrective measures.

Multiple Choice Questions with Answers

Question 1

Which expression correctly describes the next state of a synchronous FSM?

A. Q⁺ = δ(Q, X)

B. Q⁺ = λ(Q)

C. X = δ(Q⁺, Z)

D. Z = δ(X, Q⁺)

Correct Answer: A. Q⁺ = δ(Q, X)

Question 2

In a Moore machine, the output depends on:

A. Input only

B. Present state only

C. Next state and clock frequency only

D. Present state and input

Correct Answer: B. Present state only

Question 3

How many binary flip-flops are required to encode 13 states using ordinary binary encoding?

A. 2

B. 3

C. 4

D. 13

Correct Answer: C. 4

Question 4

What is the principal advantage of one-hot state assignment in many FPGA implementations?

A. It always uses the fewest flip-flops

B. It can simplify state decoding and produce fast logic

C. It eliminates the need for reset

D. It prevents all metastability

Correct Answer: B. It can simplify state decoding and produce fast logic

Question 5

For a Mealy sequence detector, outputs are conventionally placed on:

A. State circles only

B. Clock inputs

C. Transitions

D. Reset circuits only

Correct Answer: C. Transitions

Question 6

In the 101 detector example, why does detection return to the state representing a received 1?

A. To disable overlapping detection

B. Because the final 1 can begin another overlapping sequence

C. Because reset is automatically asserted

D. To create an unused state

Correct Answer: B. Because the final 1 can begin another overlapping sequence

Question 7

What is the main purpose of a synchronizer for an asynchronous input?

A. To increase the number of FSM states

B. To reduce the probability of metastability propagating

C. To eliminate propagation delay

D. To encode the input in one-hot form

Correct Answer: B. To reduce the probability of metastability propagating

Question 8

For a T flip-flop, which relation gives the required excitation?

A. T = Q + Q⁺

B. T = Q · Q⁺

C. T = Q ⊕ Q⁺

D. T = ¬Q⁺

Correct Answer: C. T = Q ⊕ Q⁺

Question 9

Which verification activity checks that every defined transition has been exercised?

A. State-transition coverage

B. Clock gating

C. State encoding

D. Logic minimization

Correct Answer: A. State-transition coverage

Question 10

A robust FSM design should do what when an unused state is reached?

A. Leave all outputs undefined

B. Force recovery to a specified safe legal state

C. Disable the clock permanently

D. Convert the state into an analog value

Correct Answer: B. Force recovery to a specified safe legal state