Skip to main content

Finite State Machines: Concept & Notation

A counter, from the previous page, is a state machine with exactly one thing it can do: advance to the next state in a fixed sequence, on every clock edge, with no say from the outside world. A finite state machine (FSM) generalizes that idea fully — its next state depends on both its current state and its current inputs, giving a circuit the ability to make decisions, not just repeat a pattern. This is the model underneath essentially every control circuit in digital design: bus protocol handlers, instruction decoders, communication receivers, and yes, traffic-light controllers and vending machines too.

What makes something an FSM​

Every FSM has the same three ingredients:

  • A finite set of states — a fixed, enumerable list of distinct conditions the circuit can be in, each represented internally as a unique bit pattern held in a register (built from the flip-flops covered two pages ago).
  • Transitions — rules for which state comes next, as a function of the current state and the current input values.
  • Outputs — signals the FSM produces, which may depend on the state alone, or on the state combined with the current inputs (the distinction that separates the two FSM styles below).

Structurally, every FSM is the same two blocks wired together: a state register (holding the current state, updated once per clock) and combinational logic that computes the next state and the outputs from the current state and inputs.

Inputs feed next-state logic, which feeds the state register (flip-flops); the state register feeds back its current state into the next-state logic and forward into output logic, which produces outputs

This is exactly the general counter-design structure from the previous page — a state register plus next-state combinational logic — with one addition: the next-state logic now also reads external inputs, and there's a separate output-logic block instead of just wiring the state register straight out.

Moore vs. Mealy machines​

The two block diagrams above collapse into two standard variants, distinguished by what the output logic is allowed to depend on:

Moore machine — outputs depend on the current state only, never directly on the current inputs:

Moore machine: inputs feed next-state logic only; state register feeds output logic and feeds back to next-state logic

Because outputs come straight from the state register (through combinational logic that doesn't touch the inputs), a Moore machine's outputs change only on a clock edge, at the same instant the state itself changes — they're synchronized to the clock and glitch-free with respect to input changes.

Mealy machine — outputs depend on the current state and the current inputs directly:

Mealy machine: inputs feed both next-state logic and output logic directly; state register feeds output logic and feeds back to next-state logic

Because the output logic reads the raw inputs directly, a Mealy machine's outputs can change the instant an input changes, without waiting for the next clock edge — which typically lets a Mealy machine react one clock cycle sooner than an equivalent Moore machine, and often needs fewer states, since the same state can produce different outputs for different current input values instead of needing a separate state per output value. The tradeoff is that a Mealy output is only as clean as its input: if the input is asynchronous or glitchy, that glitch can ripple straight through to the output between clock edges, something a Moore machine's registered outputs are naturally immune to.

Neither style is strictly better — Moore machines are generally preferred when output stability matters more than reacting instantly (e.g., driving another synchronous block), and Mealy machines are preferred when reacting a cycle sooner, or minimizing state count, matters more.

State diagrams and state tables​

An FSM's behavior is specified with a state diagram: one circle per state, arrows for transitions labeled with the input condition that triggers them (and, for a Mealy machine, the output produced during that transition). As a small running example, a sequence detector that asserts its output when it has just seen two consecutive 1s on a serial input X (overlapping matches allowed — 111 should assert the output at both the second and third bit, since the middle 1 serves as the end of one "11" match and the start of the next):

Moore version (output labeled inside each state — it doesn't depend on the current input):

Moore sequence detector: S0 (out=0) self-loops on X=0 and moves to S1 on X=1; S1 (out=0) moves to S0 on X=0 and to S2 on X=1; S2 (out=1) moves to S0 on X=0 and self-loops on X=1

Mealy version (output labeled on the transition arrow instead — one fewer state, since "just saw two 1s" and "still seeing 1s" collapse into the same state, distinguished only by which input triggered the arrow):

Mealy sequence detector: S0 self-loops on X=0/0 and moves to S1 on X=1/0; S1 moves to S0 on X=0/0 and self-loops on X=1/1

The same information is equally captured in a state table (a truth table with the current state as an extra input, and next-state as an extra output) — the form that's actually used for the design procedure on the next page:

Mealy state table:
Current state | X=0            | X=1
              | next state,out | next state,out
S0            | S0, 0          | S1, 0
S1            | S0, 0          | S1, 1

Both notations describe exactly the same circuit; the diagram is easier for a human to read and verify against the intended behavior, and the table is the mechanical starting point for turning that behavior into gates and flip-flops.

What's next​

With the state diagram and state table established as ways to specify an FSM's behavior, the next page covers how to turn that specification into an efficient circuit: minimizing redundant states and assigning binary codes to the ones that remain, before applying the same excitation-table-and-K-map procedure used for arbitrary-sequence counters.

Test Yourself on This Section