Finite-State Machines

Introduction

A finite-state machine (FSM) is a sequential computational model whose behavior depends on both current inputs and stored information about the past. Unlike a combinational circuit, whose outputs depend only on present inputs, an FSM contains memory. That memory is represented by a finite set of states and implemented physically with flip-flops.

FSMs provide a systematic method for designing controllers, communication protocols, vending machines, traffic-light systems, digital locks, bus arbiters, and many embedded-system functions. The central design task is to translate behavioral requirements into states, transitions, outputs, logic equations, and a clocked hardware implementation.

This chapter develops Moore and Mealy machines, state diagrams and tables, state assignment, minimization, implementation, simulation, verification, and architectural trade-offs.

Learning Objectives

After studying this chapter, you should be able to:

• distinguish combinational circuits from finite-state machines;
• explain Moore and Mealy output models;
• derive state diagrams and state tables from behavioral requirements;
• assign binary codes to symbolic states;
• minimize equivalent states;
• derive next-state and output logic;
• implement an FSM using flip-flops and combinational gates;
• simulate and verify an FSM, including reset behavior;
• select an appropriate architecture for practical systems.

1. Sequential Behavior and the FSM Model

An FSM consists of five conceptual elements:

1. a finite set of states;
2. an input alphabet or set of input combinations;
3. an output alphabet or set of output combinations;
4. a next-state function;
5. an output function.

Let Q denote the current state, X the input vector, Q^+ the next state, and Y the output vector. A synchronous FSM is described generally by

and

where δ is the transition function and λ is the output function. The next state is loaded into storage, normally flip-flops, on an active clock edge.

For a Moore machine, output depends only on the current state:

For a Mealy machine, output depends on the current state and current input:

These definitions describe synchronous operation. Between clock edges, combinational signals may change, but the registered state changes only at the specified clock edge, assuming appropriate setup and hold conditions.

A common hardware decomposition is:

• state register: stores Q;
• next-state logic: computes Q^+;
• output logic: computes Y.

The number of flip-flops required for N states is generally

where n is the number of state bits. This is the minimum number of binary storage elements for an unrestricted binary encoding. If N is not a power of two, some binary codes are unused and must be handled safely.

2. Moore and Mealy Machines

Moore machines

In a Moore machine, each state has an associated output. A state diagram labels transitions with inputs and states with outputs, for example, S₁/0. The output changes only after the state register changes, although combinational propagation delay can still affect the exact timing.

Advantages include:

• outputs are less directly exposed to input glitches;
• output behavior is often easier to specify and verify;
• state-based timing is predictable;
• outputs can be registered naturally.

Disadvantages include:

• additional states may be required to represent output timing;
• responses may occur one clock cycle later than in an equivalent Mealy design.

Mealy machines

In a Mealy machine, transitions are labeled with input/output pairs, such as 1/0. An output can respond during the current state interval to an input change.

Advantages include:

• rapid response to inputs;
• potentially fewer states;
• reduced state-storage requirements in some designs.

Disadvantages include:

• outputs may glitch if inputs change asynchronously or near a clock edge;
• output timing is more difficult to constrain;
• careless designs can create undesirable pulses.

A Mealy output is not automatically asynchronous in the broad system sense: the state is still clocked, but the combinational output may vary whenever its input changes. For externally visible control signals, designers often register the output or use a Moore-style interface.

Comparison

The two models are computationally equivalent: a Mealy machine can be converted to a Moore machine by splitting states where necessary, and a Moore machine can be represented as a Mealy machine by placing each state's output on outgoing transitions. Equivalence does not imply identical latency, state count, or hazard behavior.

3. From Requirements to a State Model

FSM design should begin with an unambiguous behavioral specification rather than with gates. A reliable process is:

1. identify inputs, outputs, clock, and reset;
2. describe the required behavior in time order;
3. identify situations in which the controller must remember different histories;
4. name the states according to those situations;
5. define transitions for every relevant input combination;
6. define outputs for every state or transition;
7. choose Moore or Mealy behavior;
8. encode states and derive logic;
9. simulate normal, boundary, illegal, and reset cases;
10. implement and verify against the original requirements.

A state represents information from the past that is relevant to future behavior. It should not represent every event that has ever occurred; it should represent only distinctions that affect future outputs or transitions.

State diagrams and state tables

A state diagram uses circles for states and directed arrows for transitions. A state table provides an exhaustive representation:

For multiple input bits, each row should cover a complete input combination or a clearly justified condition. “Don't care” entries are acceptable only when all omitted combinations genuinely have the same behavior and the resulting simplification is safe.

Reset

Reset establishes a known initial state. A synchronous reset is sampled at the active clock edge; an asynchronous reset can change the state independently of the clock. The choice affects timing, synthesis, reliability, and verification. Unless requirements specify otherwise, an FSM should have a defined reset state and defined recovery from unused states.

4. Worked Example: Detecting a Serial Pattern

Consider a synchronous input x and output z. The output must become 1 whenever the most recently received bit completes the pattern 101. Overlapping patterns are allowed. For example, the input sequence 10101 contains two occurrences, ending at positions 3 and 5.

We construct a Mealy machine whose states record the longest suffix of the received sequence that is also a prefix of 101:

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

The transitions are:

The output is 1 on the transition from S₂ with input 1. Because the final 1 is also a possible beginning of a new pattern, the next state is S₁, enabling overlap.

State assignment

Three states require

state bits. Choose the encoding

Let the D flip-flop inputs be D₁ and D₀. Reading the table gives:

One valid minimized implementation is:

These equations are valid for the specified valid states. Since 11 is unused, the designer must decide its recovery behavior. A robust implementation can explicitly assign 11 to 00 on the next clock, or simplify equations so that illegal encodings do not cause unsafe outputs. The exact equations may change when don't-care assumptions are used; therefore, illegal-state behavior must be verified rather than assumed.

For the input sequence 1, 0, 1, 0, 1, starting from S₀, the state sequence is:

The output pulses on the third and fifth input bits, demonstrating overlap.

5. State Minimization

State minimization reduces hardware by identifying states that cannot be distinguished by any future input sequence. Two states are equivalent when, for every possible input sequence, they produce identical output sequences and transition to equivalent states after each input.

For a Moore machine, equivalent states must initially have equal outputs. For a Mealy machine, corresponding outputs on every input must initially be equal. A standard partition-refinement procedure is:

1. partition states according to their immediate output behavior;
2. inspect transitions under every input;
3. split a group if its members transition to different groups;
4. repeat until no group changes.

The final groups are equivalence classes. One representative state can be retained for each class.

Minimization must be applied before or after state encoding according to the design method, but it is conceptually a symbolic operation. It is not simply the removal of states that appear unused in one test sequence. An apparently redundant state may be necessary for a future input sequence or for a specified output timing.

6. State Assignment and Implementation Choices

State assignment maps symbolic states to binary vectors. The assignment affects the complexity of next-state and output logic, switching activity, speed, and fault recovery.

Common assignments include:

• binary encoding: approximately ⌈log₂N⌉ flip-flops;
• one-hot encoding: one flip-flop per state, with one active state bit;
• Gray-like encoding: adjacent states differ in few bits;
• tool-optimized encoding: selected by synthesis software according to timing, area, or power goals.

Binary encoding usually saves flip-flops. One-hot encoding can simplify decoding and often performs well in FPGA architectures, where flip-flops are plentiful. It may consume more storage and requires recovery if zero or multiple state bits become active. Gray-like assignments can reduce simultaneous bit transitions, which can be useful where switching noise matters, but they do not automatically minimize logic.

The implementation equations depend on the storage element. For D flip-flops, each next-state bit directly drives a D input:

For a T flip-flop, the excitation relation is

where ⊕ denotes exclusive OR. For a JK flip-flop, excitation equations or a characteristic table must be used. The state model remains the same; only the storage implementation changes.

7. Simulation and Verification

Simulation should test behavior, not merely whether the circuit compiles. A useful verification plan includes:

• reset assertion and release;
• every state and every input combination;
• normal operating sequences;
• shortest and longest relevant sequences;
• overlapping and back-to-back events;
• illegal state encodings;
• input changes near clock edges, where timing assumptions apply;
• output timing and pulse width;
• recovery after reset or fault injection.

A reference model can implement the transition and output functions independently of the gate-level circuit. At each clock edge, the implementation's state and output are compared with the model. Assertions can express properties such as “the detector output is high only when the preceding three sampled bits are 101” or “reset always leads to the idle state.”

Simulation is not a proof of correctness. It samples selected cases. Formal equivalence checking, model checking, exhaustive state exploration, and assertion-based verification can provide stronger guarantees for finite systems. Hardware testing must additionally consider propagation delay, clock skew, metastability, reset distribution, and electrical loading.

Synchronous inputs and metastability

An FSM assumes that inputs satisfy setup and hold requirements relative to the clock. An external asynchronous signal can violate those requirements and cause metastability in a receiving flip-flop. A common mitigation is a synchronizer, often two cascaded flip-flops, followed by FSM sampling. A synchronizer reduces risk but does not make metastability impossible, and it introduces latency. Pulse signals may require pulse stretching, handshaking, or an asynchronous event-capture circuit rather than simple synchronization.

8. Architectural Selection and Practical Trade-offs

The Moore/Mealy decision should follow interface and timing requirements rather than habit. Moore outputs are preferable when a control signal must remain stable throughout a clock interval or when avoiding input-dependent glitches is important. Mealy outputs are useful when a response must be generated in the same cycle as an input condition and the interface can tolerate combinational dependence.

A hybrid architecture is common: use Mealy-style internal decision logic, then register externally visible outputs. This can preserve fast internal decisions while producing clean, clock-aligned outputs. Another option is to use a Moore controller with additional data-path logic when the controller's sequencing and the data computation have different timing requirements.

Professional design also considers:

• clock frequency and critical path delay;
• area and power budgets;
• reset and recovery requirements;
• safe behavior under illegal states;
• synthesis and implementation technology;
• testability and observability;
• interface protocols and latency;
• maintainability of the RTL and state documentation.

9. Illustrative Case: Elevator Door Controller

Background

Consider a small elevator door controller with inputs open_req, close_req, fully_open, fully_closed, and obstruction. Outputs control a motor: open_motor, close_motor, and alarm. The controller is clocked and reset to a closed-idle state.

Problem

The door must open when requested, stop when fully open, close when commanded or after a timer event, and reopen if an obstruction is detected while closing. It must never command opening and closing simultaneously.

Analysis

Useful Moore states are:

• CLOSED: both motor outputs low;
• OPENING: opening motor high;
• OPEN: both motors low;
• CLOSING: closing motor high;
• FAULT: motors low and alarm high.

The state model records the operational mode, while sensors determine transitions. For example, from CLOSING, obstruction=1 causes a transition to OPENING or OPEN, depending on the mechanical policy. A contradictory sensor condition, such as fully open and fully closed simultaneously, should lead to FAULT rather than an arbitrary motor command.

Approach and solution

A Moore architecture is appropriate because motor commands should not glitch directly in response to sensor changes. Each state has safe, mutually exclusive outputs. The transition table should specify behavior for all sensor combinations, including sensor faults. Interlocks may also be implemented independently in the power-control layer so that a logic error cannot energize both motor directions.

The controller should use synchronized sensor inputs, timeout detection for a door that fails to reach a limit, and a reset sequence that leaves motors disabled until sensors are valid. Verification should include obstruction during every closing interval, sensor disagreement, repeated requests, and power-up in each possible state.

Outcome

The resulting controller is more conservative than a minimal Mealy design, but it provides stable outputs, explicit fault handling, and a clear safety argument. In real elevator equipment, this FSM would be only one part of a certified safety system; software or programmable logic cannot replace required independent safety circuits and regulatory compliance.

Learning points

The case demonstrates that state selection is a requirements-analysis activity. Safety-related states should represent not only normal operation but also fault conditions. Moore outputs, synchronized inputs, timeouts, interlocks, and explicit illegal-state recovery are practical design disciplines.

10. Challenges, Limitations, and Best Practices

FSMs are powerful but finite. They may become difficult to maintain when a specification contains many interacting modes, long counters, data values, or concurrent activities. A large monolithic FSM can be replaced by several communicating FSMs, a controller–datapath architecture, or a programmable processor. Decomposition improves structure but introduces interface synchronization and verification obligations.

Best practices include:

• write an unambiguous state transition specification before coding;
• use descriptive symbolic state names;
• separate state, next-state, and output logic clearly;
• define reset and illegal-state behavior explicitly;
• synchronize asynchronous inputs;
• avoid unintended latches in combinational next-state logic;
• ensure mutually exclusive safety outputs;
• document latency for every output;
• use assertions and coverage metrics;
• review the design against requirements, not only waveforms;
• preserve traceability from each requirement to a state, transition, or verification test.

Modern synthesis tools can infer FSMs and optimize state encoding, but automatic optimization does not remove the need for correct specifications. AI-assisted coding and automated property generation may improve productivity, yet generated RTL must be reviewed for reset semantics, incomplete assignments, clock-domain crossings, unreachable states, and unsafe assumptions. Responsibility for verification remains with the engineer.

Chapter Summary

A finite-state machine models sequential behavior using a finite set of states, a transition function, and an output function. The state register stores relevant history; combinational logic determines the next state and outputs. Moore machines produce outputs from current state, while Mealy machines produce outputs from current state and input. Moore designs commonly provide cleaner timing, whereas Mealy designs can respond sooner and use fewer states.

A disciplined FSM workflow begins with requirements, identifies meaningful states, constructs a complete state table or diagram, chooses an output model, minimizes equivalent states, assigns binary codes, derives excitation and output equations, and implements the circuit with flip-flops and combinational logic. Verification must cover reset, normal sequences, overlaps, boundary conditions, illegal states, timing assumptions, and asynchronous inputs. Practical architecture selection balances latency, area, power, glitches, safety, testability, and maintainability.

Key Terms

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

State: Stored information representing the relevant history of a system.

State register: Flip-flops that store the current state.

Next-state function: Function mapping current state and input to the next state.

Output function: Function determining circuit outputs.

Moore machine: FSM whose output depends only on current state.

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

State diagram: Graphical representation of states and transitions.

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

State assignment: Mapping symbolic states to binary codes.

State minimization: Removal or merging of behaviorally equivalent states.

One-hot encoding: Encoding with one active flip-flop per state.

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

Synchronous reset: Reset sampled on a clock edge.

Asynchronous reset: Reset that can affect state independently of the clock.

Metastability: Uncertain flip-flop behavior caused by a timing violation.

Synchronizer: Circuit used to reduce the risk of metastability when sampling asynchronous signals.

Overlap detection: Recognition of a new pattern using symbols that also completed a previous pattern.

Review Questions

Short Answer Questions

1. What distinguishes an FSM from a combinational circuit?
2. State the output function for Moore and Mealy machines.
3. Why can a Mealy machine require fewer states than a Moore machine?
4. What is the purpose of state assignment?
5. Why must asynchronous inputs be synchronized before use in an FSM?

Long Answer Questions

1. Explain a complete workflow for converting behavioral requirements into an implemented FSM.
2. Compare Moore and Mealy machines with respect to timing, glitches, state count, and verification.
3. Describe partition refinement as a method of state minimization.
4. Explain binary, one-hot, and Gray-like state assignments and their trade-offs.
5. Discuss reset, illegal-state recovery, and fault handling in a safety-conscious FSM.

Analytical / Application Questions

1. Design a Mealy FSM that detects the overlapping sequence 1101. Provide states, a state table, and an explanation of the overlap transition.
2. A controller has seven valid states. Determine the minimum number of binary state flip-flops and explain how unused encodings should be handled.
3. Choose Moore or Mealy architecture for a motor-control signal that must never glitch when an asynchronous sensor changes. Justify the choice and describe any additional interface circuitry required.

Multiple Choice Questions with Answers

Question 1

Which expression correctly describes a Moore machine output?

A. Y = λ(Q, X)

B. Y = λ(Q)

C. Q = λ(Y)

D. X = λ(Q)

Correct Answer: B. Y = λ(Q)

Question 2

What is the minimum number of binary state bits required for seven states?

A. 2

B. 3

C. 4

D. 7

Correct Answer: B. 3

Question 3

In a Mealy machine, outputs are associated primarily with which elements of the state diagram?

A. States only

B. Reset signals only

C. Transitions

D. Flip-flop clock pins

Correct Answer: C. Transitions

Question 4

For the 101 detector in the chapter, which transition produces the detection output?

A. S₀ with input 0

B. S₀ with input 1

C. S₁ with input 0

D. S₂ with input 1

Correct Answer: D. S₂ with input 1

Question 5

What is the primary purpose of state minimization?

A. To increase the number of output signals

B. To merge behaviorally equivalent states

C. To eliminate the clock

D. To convert all FSMs into combinational circuits

Correct Answer: B. To merge behaviorally equivalent states

Question 6

For a D flip-flop implementation, what signal is applied to a D input?

A. The present-state bit complement

B. The corresponding next-state bit

C. The output signal only

D. The clock frequency

Correct Answer: B. The corresponding next-state bit

Question 7

Which encoding normally uses one flip-flop for each symbolic state?

A. Binary encoding

B. One-hot encoding

C. Parity encoding

D. ASCII encoding

Correct Answer: B. One-hot encoding

Question 8

Why is an asynchronous external input commonly passed through a synchronizer?

A. To increase the number of FSM states

B. To eliminate all propagation delay

C. To reduce the risk of metastability

D. To convert a Moore machine into a Mealy machine

Correct Answer: C. To reduce the risk of metastability

Question 9

Which architecture generally provides outputs that are less directly sensitive to input glitches?

A. Moore architecture

B. Unclocked combinational architecture

C. Pure asynchronous latch architecture

D. Mealy architecture in every implementation

Correct Answer: A. Moore architecture

Question 10

A seven-state FSM uses two state bits. What issue must the designer address?

A. There are no possible binary codes

B. One binary code is unused and needs defined behavior

C. The FSM cannot be clocked

D. The output must always be one-hot

Correct Answer: B. One binary code is unused and needs defined behavior