7. Finite-State Machines and Control Units

Introduction and Context

Digital systems are often described in terms of data transformation: adders compute sums, multiplexers select signals, and arithmetic-logic units perform operations. Yet most useful systems also need to remember where they are in a sequence of operations. A communication interface must distinguish an address phase from a data phase; a processor control unit must issue different signals during instruction fetch, decode, and execution; and a sequence detector must recognize an input pattern while retaining partial progress. These are temporal tasks, and their natural abstraction is the finite-state machine (FSM).

An FSM is a mathematical and hardware model of a sequential circuit whose future behaviour depends on its present state and current inputs. The state represents relevant history in a finite, encoded form. FSMs provide a disciplined bridge between system requirements and hardware implementation. They support formal reasoning, state minimisation, verification, synthesis, and the design of controllers ranging from small embedded interfaces to processor control units and protocol engines.

This chapter develops Moore and Mealy machines, state diagrams, state tables, state assignment, minimisation, implementation using flip-flops and combinational logic, and algorithmic state-machine (ASM) charts. The discussion also considers timing, reset design, hazards, verification, and the engineering trade-offs involved in choosing a model.

Learning Objectives

After studying this chapter, the reader should be able to:

1. Explain the role of state in sequential digital systems and distinguish Moore from Mealy machines.

2. Translate a verbal specification into a state diagram, state table, or ASM chart.

3. Minimise equivalent states and select a suitable state encoding.

4. Derive next-state and output logic for an FSM implementation.

5. Design sequence detectors, controllers, and protocol-oriented machines.

6. Identify timing, reset, safety, verification, and synthesis issues in practical FSMs.

7. Evaluate architectural choices involving latency, state count, encoding, and output behaviour.

The State-Based Model

A finite-state machine may be represented by the five-tuple

M = (S, I, O, δ, λ)

where S is a finite set of states, I is the input alphabet, O is the output alphabet, δ is the next-state function, and λ is the output function. For a synchronous binary machine, state transitions normally occur on an active clock edge. Between clock edges, combinational logic calculates the next state from the present state and inputs. A bank of flip-flops stores the state until the next edge.

The essential decomposition is therefore:

Present state and inputs → next-state logic → state registers → present state

The output logic may depend only on the present state or on both the present state and current inputs. This distinction defines the two classical FSM models.

Moore and Mealy Machines

In a Moore machine, outputs depend only on the present state:

Z(t) = λ[S(t)]

Consequently, an output changes only when the registered state changes, assuming the output decoder is well behaved. Moore outputs are usually easier to time and verify because they are not directly affected by asynchronous input changes. The price is that an additional state may be required to represent an output condition, and the response may appear one clock cycle later.

In a Mealy machine, outputs depend on the present state and inputs:

Z(t) = λ[S(t), I(t)]

A Mealy machine can respond during the current state interval and often uses fewer states. However, input changes can affect outputs immediately through combinational paths. If inputs are not synchronous or stable for the required setup and hold intervals, glitches may occur. Registered outputs or carefully constrained interfaces are often used when Mealy responsiveness is needed without exposing combinational hazards.

The choice is not a matter of one model being universally superior. Moore machines are attractive for clean interfaces and output stability; Mealy machines are useful when early response and compact state representation matter. A design may also use a Moore-like externally registered output interface while deriving internal control decisions from Mealy logic.

Representing Behaviour: Diagrams, Tables, and ASM Charts

A state diagram represents each state as a node and each transition as a directed arc. In a Moore diagram, the output is written inside or beside the state node, commonly in the form state/output. In a Mealy diagram, a transition is labelled input/output. Every relevant input condition must lead to a defined transition, including conditions that are not expected during normal operation.

A state table provides a more implementation-oriented representation. Its columns generally include present state, input combinations, next state, and output. State tables are convenient for deriving Boolean equations and for checking completeness. For n binary inputs, there are 2^n possible input combinations for each state; unspecified combinations should be deliberately treated as don't-care conditions only when the resulting behaviour is safe.

ASM charts are especially useful for controllers. An ASM block describes the actions associated with a state, a decision box tests an input or condition, and a conditional output box specifies an output asserted only on a selected path. An ASM chart resembles a flowchart but has clocked semantics: operations in a state box are generally performed during one clock period, and movement to another state occurs at the next active clock edge. This makes sequencing and control-word generation clearer than a large state diagram.

From Specification to State Machine

FSM design is best treated as a structured process rather than an exercise in guessing equations.

1. Define the interface and timing contract

Identify inputs, outputs, clock polarity, reset behaviour, input sampling assumptions, and the required response latency. A statement such as “assert acknowledge when a valid request is accepted” is incomplete unless acceptance, request duration, and acknowledge timing are defined.

2. Identify distinguishable situations

Create a state for each situation in which the future response differs. A state is not simply a step number. It is an equivalence class of histories that produce identical future behaviour for all possible input sequences. For a sequence detector seeking 1011, relevant states may represent that no useful suffix has been observed, that 1 has been observed, that 10 has been observed, or that 101 has been observed.

3. Select Moore or Mealy outputs

If outputs must remain stable throughout a cycle or control an external interface, Moore or registered Mealy outputs are often appropriate. If the specification requires a response on the transition that completes an event, a Mealy formulation may reduce latency.

4. Draw the diagram and construct the table

Start with the reset state and enumerate every legal input condition. Then define recovery behaviour for illegal or unused states. This step frequently reveals ambiguity in the original specification.

5. Minimise and encode states

Remove states that are behaviourally equivalent, then choose a binary, one-hot, Gray, or application-specific encoding. State assignment affects logic size, timing, power, and fault recovery.

6. Derive and implement logic

Let the state register be Q and the encoded next state be D. For D flip-flops, D equals the next-state function. Derive equations using Boolean algebra, Karnaugh maps, or synthesis tools. Implement output logic, state registers, reset circuitry, and any input synchronisation.

7. Verify normal and abnormal behaviour

Test all transitions, reset release, illegal state entry, input changes near clock edges, overlapping sequences, and protocol violations. Assertions and formal equivalence checking are valuable for larger controllers.

State Minimisation and Equivalence

State minimisation reduces hardware and may simplify verification. Two states are equivalent if, for every possible future input sequence, they produce identical output sequences and transition to equivalent states. For a Moore machine, equivalent states must first have identical outputs. For a Mealy machine, their outputs must agree for every input, and their successor states must remain equivalent.

A practical partition-refinement method begins by grouping states according to immediate output behaviour. The groups are then repeatedly divided according to the groups containing each state's successors for every input. When no group changes, the states in each remaining block are equivalent and may be merged.

For example, suppose states A and B of a Moore machine both produce output 0. If, for input x=0, A and B transition into states within the same current partition, and the same is true for x=1, they remain candidates for equivalence. If a later refinement separates one pair of successors, A and B must also be separated. Minimisation should be performed before state assignment, because assigning codes to redundant states wastes registers or logic.

Do not merge states merely because they have the same output at one instant. Their future responses must be identical for every input sequence. Conversely, states that appear different in a particular operating scenario may be equivalent if the supposedly distinguishing input is impossible under a formally defined environment assumption; such assumptions must be documented and verified.

State Encoding and Hardware Realisation

If a machine has N states, binary encoding requires at least ceil(log2 N) flip-flops. It uses the fewest registers but may require relatively complex decoding. One-hot encoding uses N flip-flops, with one state bit asserted at a time. It often produces simple, fast logic in FPGA devices because flip-flops are plentiful and lookup-table inputs are limited. Gray-like assignments can reduce the number of bits changing on adjacent transitions, which may reduce switching activity or transient decoding problems, although arbitrary FSM transitions rarely permit a perfect Gray sequence.

The implementation equations can be written as:

Q(t+1) = F[Q(t), I(t)]

Z(t) = G[Q(t)] for a Moore machine, or Z(t) = G[Q(t), I(t)] for a Mealy machine.

For a synchronous design, input signals should meet setup and hold requirements at the state-register clock edge. An asynchronous external input should first pass through a synchroniser, commonly two flip-flops in series, if metastability risk is acceptable to manage in that manner. A synchroniser does not make an unsafe protocol safe; it only reduces the probability that metastability propagates into logic.

Unused encodings require deliberate treatment. The next-state logic can direct them to the reset or an error state. “Don't-care” assignments may allow synthesis optimisation, but if the machine enters an unused state due to a fault, power disturbance, or upset, arbitrary recovery may be unsafe. Safety-critical controllers generally specify deterministic recovery and may include state-validity monitoring.

Reset design deserves equal attention. An asynchronous assertion can place the system in a known state quickly, but asynchronous deassertion must be synchronised to avoid recovery/removal violations. A synchronous reset is easier to analyse within the clocked design but acts only on a clock edge. The reset state should not merely be convenient; it should correspond to a safe external condition.

Sequence Detectors: A Worked Design Pattern

Consider a detector for the serial pattern 1011. The input is sampled once per clock. An output pulse is required when the final 1 is received, and overlapping occurrences are allowed.

A Mealy design can use states representing the longest suffix of the received sequence that is also a prefix of 1011:

• S0: no useful suffix;
• S1: suffix 1;
• S2: suffix 10;
• S3: suffix 101.

From S0, input 1 leads to S1 and input 0 remains in S0. From S1, input 0 leads to S2; input 1 remains in S1 because the latest 1 may begin a new match. From S2, input 1 leads to S3; input 0 returns to S0. From S3, input 1 produces the detection pulse and moves to S1, because the final 1 can also be the first symbol of an overlapping occurrence. From S3, input 0 returns to S2, since the suffix 10 remains useful.

The output is 1 only on the S3-to-S1 transition caused by input 1. This is a Mealy output and occurs in the cycle in which the pattern is completed. A Moore implementation would add a DETECT state with output 1, entered after the final symbol, and then transition to the appropriate partial-match state. The Moore version is often easier to interface, but its pulse is associated with a separate state and may require an extra clock interval.

The important design principle is preservation of the longest useful suffix. Resetting to S0 after every detection would fail to recognise overlapping patterns. This same principle appears in practical packet parsers, command recognisers, and framing logic.

Control Units and ASM-Based Design

A control unit coordinates datapath operations. The datapath contains registers, arithmetic units, memories, and multiplexers; the controller generates signals such as register enables, multiplexer selections, memory read/write controls, and arithmetic operation codes. An FSM is the controller's temporal skeleton.

Suppose a small processor executes an instruction in fetch, decode, and execute phases. A simplified Moore-style controller may use states FETCH, DECODE, ADD_EXEC, and STORE_EXEC. FETCH asserts the program-counter and memory-address controls. DECODE loads or interprets the instruction. Depending on the opcode, the next state is ADD_EXEC or STORE_EXEC. Each execution state asserts the appropriate datapath controls and then returns to FETCH.

An ASM chart makes the sequencing explicit. In FETCH, the controller may assert memory-read and instruction-register-load signals. A decision in DECODE tests the opcode. Conditional paths select the execution state. If a memory operation requires a wait input, a WAIT state may loop until ready is asserted. This is preferable to embedding a timing assumption in combinational logic.

A controller should not assert mutually incompatible controls, such as two register-write enables targeting different registers without an explicitly supported multiwrite datapath. Control-word definitions, enumerated states, and interface timing should be specified alongside the RTL. For complex processors and bus controllers, microprogrammed control may be used: the state is represented by a microinstruction address, and a control store supplies a wide control word. Hardwired FSMs generally offer speed and compactness for small fixed sequences, while microprogramming offers flexibility and simpler modification of complex control policies.

Protocol Engines and Handshake Behaviour

Protocol engines are FSMs with externally visible timing contracts. A request/acknowledge controller, for example, may contain IDLE, ACCEPT, SERVICE, and RESPOND states. The design must define whether requests are level-sensitive or pulsed, whether a request may arrive while busy, how long acknowledge remains asserted, and what happens after timeout.

A robust protocol FSM explicitly handles back-pressure, retries, timeout, reset during a transaction, and illegal message order. It should not rely on an input remaining asserted indefinitely unless the interface specification guarantees this. If two clock domains are involved, handshake signals require synchronisation or a clock-domain-crossing protocol such as a toggle, pulse-stretching mechanism, or asynchronous FIFO. Directly using a signal from another clock domain as an FSM input can produce metastability and inconsistent event observation.

Detailed Illustrative Case: A Low-Power Sensor Interface Controller

Background

Consider an illustrative battery-powered environmental sensor node. A microcontroller requests a measurement from a sensor connected through a serial interface. The sensor requires a start command, performs conversion for an uncertain number of cycles, and then returns data plus a validity indication. The controller must minimise energy, reject malformed responses, and recover if the sensor fails to respond.

Situation and Problem

A naive design uses one long combinational sequence and assumes that the sensor always responds within a fixed delay. In practice, responses vary, a busy indication may persist, and the sensor may be disconnected. The controller must also prevent a stale data word from being reported as a new measurement.

Analysis

The behaviour contains distinguishable temporal conditions: no request, command transmission, waiting for completion, receiving data, checking validity, reporting success, and reporting failure. Outputs such as sensor-enable and data-valid should be stable and easy for the microcontroller to sample. A Moore-oriented controller is therefore appropriate for externally visible status outputs, while internal combinational conditions determine transitions.

Approach and Solution

The proposed states are IDLE, START, WAIT_BUSY, READ, CHECK, DONE, and TIMEOUT. In IDLE, a new request causes transition to START. START asserts the serial command for one clock-defined transaction. WAIT_BUSY waits for the sensor's busy signal to clear; a counter operates in parallel. If the counter reaches its limit, the controller enters TIMEOUT. When busy clears, READ shifts the specified number of response bits into a register. CHECK tests a parity or checksum flag. Valid data is transferred to the output register before DONE asserts data-valid for one cycle. Invalid data enters an ERROR or TIMEOUT recovery path, depending on the interface policy. All failure states return to IDLE only after sensor-enable has been deasserted and the serial interface has returned to its idle level.

The counter is part of the datapath, but its terminal-count condition is an FSM input. The controller therefore coordinates two synchronous components rather than attempting to represent every counter value as a separate state. Assertions can specify that data-valid implies a valid checksum and that sensor-enable is not active in IDLE. A fault-injection test can force unexpected busy behaviour and verify timeout recovery.

Outcome

The state-based design makes latency, failure handling, and output validity explicit. It prevents stale data from being mistaken for a successful measurement, limits energy consumed during an absent-sensor condition, and provides clear verification points. The example also illustrates a general architectural rule: use states for qualitatively different control situations and counters or datapath registers for numerical repetition.

Learning Points

A useful FSM specification includes normal operation, bounded waiting, invalid responses, reset behaviour, and recovery. Protocol correctness is not established by testing only the successful path. The controller's interface contract must state exactly when commands, enables, status flags, and data are valid.

Challenges, Risks, and Common Design Errors

Several errors recur in FSM work. Incomplete transition descriptions may infer unintended latches in combinational next-state logic. Multiple assignments to the same output in different branches can create simulation-synthesis mismatches. A missing default assignment may leave a signal retaining its previous value, whereas the intended controller requires it to be deasserted.

Another error is confusing state transitions with output timing. A Mealy output can change as soon as an input changes within a cycle, while a Moore output normally changes with state. If a Mealy output drives a handshake or clock-like control, glitches may be interpreted as events. Registering the output, using a Moore state, or imposing a formal timing constraint can resolve the problem.

Designers also sometimes use a state for every count value, producing unnecessarily large machines. Conversely, hiding too much behaviour in a counter can make protocol sequencing opaque. State minimisation, datapath separation, and clear invariants provide a better balance.

Illegal-state recovery, reset release, clock-domain crossings, and simultaneous events deserve explicit analysis. Simulation with ideal zero-delay signals will not reveal all metastability or physical timing problems. Static timing analysis, synchroniser design, linting, assertions, and hardware-oriented verification are complementary necessities.

Professional and Governance Considerations

In industrial controllers, FSM specifications are often reviewed as safety or compliance artefacts. State diagrams, transition tables, timing assumptions, reset policies, and traceability from requirements to verification tests should be version-controlled. For safety-related applications, fail-safe states, diagnostic outputs, watchdog interaction, and single-fault behaviour may be required by the applicable sector standard. The precise standard depends on the application; the engineering principle is universal: a controller must make unsafe ambiguity visible rather than silently assigning arbitrary behaviour.

Security also has an FSM dimension. Authentication protocols, bus permissions, and packet parsers must reject illegal orderings and avoid states in which privileged controls remain asserted after an error. Formal properties such as “a write enable is never asserted without ownership” can express security-relevant invariants more effectively than example-based testing alone.

Current Developments and Best Practices

Modern HDL synthesis tools infer FSMs from enumerated types and can apply state encoding automatically. FPGA designs often benefit from one-hot or tool-selected encodings, whereas ASIC designs require closer attention to area, clock power, scan test, and transition activity. Formal model checking can prove reachability, deadlock freedom, mutual exclusion of controls, and equivalence between a specification and an RTL implementation.

Practical best practices include:

• Separate state-register, next-state, and output logic clearly.
• Give every state and input condition defined behaviour.
• Synchronise asynchronous inputs and use explicit clock-domain-crossing structures.
• Prefer registered outputs for externally visible pulses and handshakes when glitches are unacceptable.
• Define reset and illegal-state recovery as part of the functional specification.
• Use assertions for safety, liveness, timeout, and protocol properties.
• Minimise states before encoding, but do not sacrifice clarity for a small reduction in gates.
• Verify overlapping events, boundary timing, reset during operation, and environmental violations.

Machine-learning-assisted RTL tools are increasingly used for code generation, optimisation suggestions, and property generation, but their output requires engineering review. An automatically produced FSM is not evidence that the specification is complete; ambiguous requirements can simply be converted into ambiguous hardware more quickly.

Chapter Summary

Finite-state machines model sequential behaviour by combining a finite state register with next-state and output logic. Moore outputs depend only on state and are naturally stable; Mealy outputs also depend on inputs and can respond earlier but require greater care with glitches and timing. State diagrams, tables, and ASM charts provide complementary views of the same behaviour.

A disciplined design begins with interface and timing requirements, identifies distinguishable situations, defines complete transitions, minimises equivalent states, selects an encoding, derives logic, and verifies both normal and abnormal operation. FSMs form the foundation of sequence detectors, processor control units, protocol engines, and embedded controllers. Practical quality depends not only on Boolean correctness but also on synchronisation, reset strategy, illegal-state recovery, formal properties, and a precise external contract.

Key Terms

State: A stored abstraction of the history relevant to future behaviour.

Finite-state machine: A sequential model with finite states, inputs, outputs, transition rules, and output rules.

Moore machine: An FSM whose outputs depend only on the present state.

Mealy machine: An FSM whose outputs depend on the present state and current inputs.

State diagram: A graphical representation of states and transitions.

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

ASM chart: A clock-oriented chart for describing controller states, decisions, and conditional actions.

Next-state function: The logic that determines the state after the next active clock edge.

State encoding: Assignment of binary codes to symbolic FSM states.

One-hot encoding: An encoding in which one state bit is asserted for each active state.

State minimisation: Removal or merging of behaviourally equivalent states.

Equivalent states: States producing identical future behaviour for every allowed input sequence.

Sequence detector: An FSM that recognises a specified pattern in a stream of inputs.

Protocol engine: A controller that enforces the ordering and timing rules of an interface.

Synchroniser: Sequential circuitry used to reduce metastability propagation from an asynchronous input.

Illegal state: An encoded state not assigned to a legitimate symbolic state.

Control unit: Logic that sequences and enables operations in a datapath or digital system.

Microprogrammed control: Control implemented by sequencing stored microinstructions that generate control signals.

Metastability: An indeterminate temporary state of a flip-flop caused by timing violation.

Review Questions

Short Answer Questions

1. What information does the state of an FSM represent?

2. State one principal difference between Moore and Mealy output functions.

3. Why should asynchronous inputs generally be synchronised before entering an FSM?

4. What is the purpose of state minimisation?

5. Why are ASM charts useful in controller design?

Long Answer Questions

1. Explain the complete workflow for converting a verbal controller specification into an implemented FSM.

2. Compare Moore and Mealy machines with respect to latency, state count, output stability, and verification.

3. Describe partition-refinement minimisation and explain how equivalence is determined for Moore machines.

4. Discuss binary, one-hot, and Gray-like state encoding, including their hardware trade-offs.

5. Explain how an FSM coordinates a datapath in a processor or peripheral controller.

Analytical / Application Questions

1. Design a Mealy sequence detector for 1011 that permits overlapping matches. Specify states, transitions, and the detection transition.

2. A controller waits for a peripheral-ready signal but may not wait indefinitely. Propose states, timeout handling, and reset recovery, explaining which functions belong in the FSM and which belong in a counter.

3. An externally visible acknowledge signal glitches when an input changes during a state. Analyse whether the design is Moore or Mealy, and propose two technically sound remedies with their trade-offs.

22. Multiple Choice Questions with Answers

Question 1

Which statement correctly characterises a Moore machine?

A. Its outputs depend only on the present state.

B. Its outputs depend only on the current inputs.

C. Its state changes asynchronously whenever an input changes.

D. It always requires more states than a Mealy machine.

Correct Answer: A. Its outputs depend only on the present state.

Question 2

For a Mealy machine, what may cause an output to change before the next active clock edge?

A. Only a reset assertion

B. A change in the present state or current input

C. Only a change in the state encoding

D. A change in an unrelated datapath register

Correct Answer: B. A change in the present state or current input

Question 3

In a sequence detector for 1011 with overlapping matches, where should the machine go after detecting 1011?

A. Always to the no-match state

B. To a state representing suffix 10

C. To a state representing suffix 1

D. To a permanent detection state

Correct Answer: C. To a state representing suffix 1

Question 4

What is the principal criterion for merging two FSM states during minimisation?

A. They have adjacent binary encodings.

B. They have the same name prefix.

C. They produce identical future behaviour for every input sequence.

D. They are reached by the same input only once.

Correct Answer: C. They produce identical future behaviour for every input sequence.

Question 5

Which state encoding generally uses one flip-flop per state?

A. Binary encoding

B. One-hot encoding

C. Parity encoding

D. Compressed Gray encoding

Correct Answer: B. One-hot encoding

Question 6

Why is a counter often preferable to separate FSM states for a long waiting interval?

A. A counter eliminates the need for a clock.

B. A counter represents numerical repetition without creating a state for every count value.

C. A counter guarantees that asynchronous inputs are safe.

D. A counter makes all outputs Moore outputs.

Correct Answer: B. A counter represents numerical repetition without creating a state for every count value.

Question 7

Which practice best addresses an input arriving from another clock domain?

A. Connect it directly to all next-state equations.

B. Use a suitable synchroniser or clock-domain-crossing protocol.

C. Increase the number of FSM states only.

D. Replace the input with a constant during simulation.

Correct Answer: B. Use a suitable synchroniser or clock-domain-crossing protocol.

Question 8

In an ASM chart, what is the usual timing meaning of a state box?

A. Its operations are associated with one clock period.

B. Its operations occur only during reset.

C. It represents an analogue voltage range.

D. It must contain exactly one Boolean equation.

Correct Answer: A. Its operations are associated with one clock period.

Question 9

Which design choice most directly reduces the risk of glitches on an externally visible control pulse?

A. Use an unregistered Mealy output driven by an asynchronous input.

B. Use a registered output or an appropriately designed Moore state.

C. Leave unused states unspecified.

D. Remove the reset state.

Correct Answer: B. Use a registered output or an appropriately designed Moore state.

Question 10

A protocol controller enters an undefined encoded state because of a fault. Which design practice provides deliberate recovery?

A. Treat every unused state as an unconstrained don't-care in all applications.

B. Direct illegal encodings to a safe recovery or reset state.

C. Increase the clock frequency until the state disappears.

D. Allow the output decoder to retain its previous value.

Correct Answer: B. Direct illegal encodings to a safe recovery or reset state.