Finite State Machines
A vending machine must remember how much money it has received. This happens before deciding to dispense a snack. A traffic light must remember whether it is red, yellow, or green. This happens before deciding what to show next. A CPU's control unit must remember which stage of an instruction it is executing. This happens before deciding which control signals to assert. In every case, the circuit's next output and next behavior depend on more than the current input. They depend on a summary of everything that happened before. That summary is a state, and the circuit that manages it is a finite state machine (FSM). Finite state machines are the bridge between the memory-storing devices covered in Latches and Flip-Flops and the combinational logic optimized with Karnaugh Maps. A latch or flip-flop alone stores one bit. Combinational logic alone has no memory at all. An FSM combines them: a bank of flip-flops holds the current state. Combinational logic computes the next state and the outputs. A clock (see Clocks and Timing) advances the whole system in lockstep. This structure is not a niche trick. It is the single most common template for sequential digital design. It appears in bus arbiters, protocol handlers, instruction decoders, and the control units that orchestrate every datapath in every processor ever built. This article gives a precise, buildable account of FSMs. It covers the two canonical models (Moore and Mealy), how to draw and read state diagrams, and how to encode states as bits. It also covers how to mechanically derive the next-state and output logic. A Karnaugh map or a synthesis tool will turn that logic into gates. We verify every step with a worked numeric trace and a from-scratch encoding exercise. By the end, you can take an English-language behavioral spec. You can produce working gate-level logic from it without hand-waving. The payoff is direct: every control unit in Datapath and Control is, underneath its complexity, a finite state machine. It uses the same five ingredients (states, inputs, outputs, next-state function, output function). These scale up to dozens or hundreds of states.
- An FSM has a finite set of states, remembered in flip-flops, updated once per clock edge.
- Moore machines: outputs depend only on the current state — safer, but can add a clock-cycle delay.
- Mealy machines: outputs depend on state and current inputs — faster reaction, but glitch-prone.
- Design flow: state diagram → state table → state encoding → next-state/output equations (via K-maps) → gates + flip-flops.
- State encoding (binary, one-hot, Gray) trades off flip-flop count against next-state logic complexity.
- FSMs are the literal building block of CPU control units, protocol handlers, and arbiters — this is where control meets circuit.
A finite state machine is a clocked circuit whose next state and outputs are pure functions of its current state (and, for Mealy machines, the current inputs) — memory plus combinational logic, disciplined by a clock.
The idea
Formally, a finite state machine is a 5-tuple (S, Σ, δ, λ, s₀): a finite set of states S, an input alphabet Σ (the possible input bit-vectors), a next-state function δ: S × Σ → S, an output function λ, and an initial state s₀. In hardware, S is encoded as the contents of a register (a bank of D flip-flops); Σ is whatever combination of input wires feeds the circuit; δ and λ are combinational logic blocks built from AND/OR/NOT gates (or a K-map-derived sum of products); and the clock edge is what causes the machine to move from state sₜ to state sₜ₊₁ = δ(sₜ, inputsₜ). The critical distinction is where the output function looks. In a Moore machine, λ depends only on the current state: `output = λ(state)`. The output is stable for the entire clock period and changes only on clock edges, because it is a function purely of the registered state. In a Mealy machine, λ depends on both current state and current input: `output = λ(state, input)`. Because inputs can change asynchronously between clock edges, a Mealy machine's output can glitch mid-cycle whenever the input changes, even though the state has not. Mealy machines can react to an input within the same cycle it arrives, while Moore machines need one extra cycle to register the effect of an input into state before it shows up in the output. Every Mealy machine can be converted into an equivalent Moore machine (at the cost of extra states) and vice versa (with equal state count, just moving the output logic), so the choice is an engineering tradeoff, not a difference in expressive power. A third practical concept is state encoding: assigning a bit pattern to each abstract state so it can live in a register. With n states you need at least ⌈log₂ n⌉ flip-flops for a dense binary encoding, or exactly n flip-flops for one-hot encoding (one flip-flop per state, exactly one high at a time). Binary encoding minimizes flip-flop count but often produces denser, harder-to-optimize next-state logic; one-hot encoding uses more flip-flops but each next-state equation tends to be simpler (often a single OR of a few predecessor-state bits), which frequently yields a faster critical path in FPGAs where flip-flops are cheap and plentiful.
How it works
Step 1 — Capture behavior as a state diagram. Draw each state as a circle; draw directed edges labeled with the input condition that triggers the transition (Mealy machines also label the edge with the output produced; Moore machines write the output inside the state circle instead).
Step 2 — Convert the diagram to a state table. One row per (current state, input combination), listing the next state (and, for Mealy, the output produced on that row).
Step 3 — Choose a state encoding. Assign a bit pattern to every abstract state name.
Step 4 — Derive next-state and output equations. Treat each bit of the next-state register, and each output bit, as its own Boolean function of the current-state bits (and inputs, for Mealy outputs). Build a truth table per bit and simplify with a Karnaugh map exactly as in combinational design.
Step 5 — Build the circuit. Wire the next-state logic into the D inputs of a state register; feed the register's Q outputs back as the "current state" bits into both the next-state logic and the output logic; clock the register. ``` // Generic synchronous FSM update, one clock period // state : register holding current-state bits (n bits) // nextLogic : combinational function, state × input -> next state bits // outLogic : combinational function // Moore: state -> output bits // Mealy: state × input -> output bits function TICK(state, input): // combinational stage: computed continuously, settles before clock edge ns = nextLogic(state, input) if MOORE: out = outLogic(state) // depends on OLD (pre-edge) state else: // MEALY out = outLogic(state, input) // reacts within the same cycle // sequential stage: happens ONLY at the clock edge on CLOCK_RISING_EDGE: state <- ns return out // Driver loop state <- s0 loop forever: input <- sample_inputs() output <- TICK(state, input) emit(output) wait_for_next_clock_edge() ``` The pseudocode makes the Moore/Mealy distinction mechanical: `outLogic` either ignores `input` (Moore) or consumes it (Mealy). Everything else — the register update, the clocking discipline — is identical. Note the crucial ordering: `ns` and `out` are both computed before the clock edge, from the pre-edge state; the register only updates at the edge. This is what prevents race conditions between reading and writing state (the same discipline enforced by edge-triggered flip-flops in Latches and Flip-Flops).
Complexity & correctness
Time. The steady-state throughput of a synchronous FSM is one state transition per clock cycle, by construction — the clock period must simply be long enough for the next-state logic's combinational delay plus flip-flop setup time to settle (`T_clk ≥ t_pd(δ) + t_setup`), a direct application of Clocks and Timing constraints. Producing a specific output sequence of length k in response to an input string of length k takes exactly k cycles for a Moore machine (output visible one cycle after the triggering input for the first symbol, since the very first output reflects `s0` before any input is consumed) and k cycles for Mealy as well, but a Mealy output for input symbol i reflects that same-cycle input, so Mealy machines can recognize/react to a pattern up to one cycle sooner than an equivalent Moore machine — this is the classical Moore-vs-Mealy latency argument, not an asymptotic complexity difference.
Space. State memory requires ⌈log₂|S|⌉ flip-flops under binary encoding, or |S| flip-flops under one-hot encoding; combinational logic size depends on the specific next-state/output functions and is bounded by standard sum-of-products blowup, i.e., worst case exponential in the number of state and input bits, though in practice K-map/Quine–McCluskey minimization (see Karnaugh Maps) keeps real designs far below that bound.
Correctness — the invariant. The central correctness claim for any FSM implementation is an invariant: at every clock edge, the value latched into the state register equals δ applied to the value that was in the register just before the edge, and every value the output logic reads was stable throughout that clock period. This holds by construction because (1) combinational logic has no memory, so `nextLogic(state, input)` is a pure function re-evaluated continuously and always reflects the current register contents and input; (2) edge-triggered flip-flops (from Latches and Flip-Flops) sample their D input only at the clock edge and hold it steady otherwise, which is exactly what breaks the potential feedback race between "reading current state" and "writing next state." Inductively: if the register correctly holds `s_t` before edge t+1, then combinational logic computes `s_{t+1} = δ(s_t, input_t)` correctly (pure function, no timing dependence beyond settling time), and the edge samples it correctly — so by induction the register holds the correct state at every tick, for all t ≥ 0, given a correct `s_0`.
Tradeoffs, honestly.
- Binary encoding: fewest flip-flops, but next-state logic can require deep, irregular gate networks — worse for timing closure on FPGAs.
- One-hot encoding: most flip-flops, but each next-state bit is typically a small OR of a few "predecessor active + condition true" terms — often faster and easier to debug, at the cost of area.
- Gray-code encoding: adjacent states differ by one bit, minimizing simultaneous-bit-flip hazards — valuable when the FSM output feeds asynchronous logic or crosses clock domains, but doesn't generally minimize equation complexity.
- Mealy machines react faster but their outputs are not glitch-free between clock edges if the input changes asynchronously; if the output feeds something without a stable-sampling discipline, Moore is safer.
Worked example
Specification: a sequence detector that outputs 1 (as a Moore output) exactly one cycle after the input stream (one bit per cycle) has produced the pattern `1101`, with overlap allowed (e.g., `11101` should catch `1101` at the end even though it shares a `1` with an earlier attempt).
States: `A` (no progress), `B` (seen "1"), `C` (seen "11"), `D` (seen "110"), `E` (seen "1101" — output 1 here, Moore).
State table (input bit `x`; `A` is start state):
| Current | x=0 | x=1 | Output (Moore, = f(current)) |
|---|---|---|---|
| A | A | B | 0 |
| B | A | C | 0 |
| C | D | C | 0 |
| D | A | B | 0 |
| E | A | B | 1 |
(From `D` on `x=1`, we go to `B`, not `C`, because the suffix `1` restarts the match at "seen one 1" — this is the standard overlap-aware KMP-style construction, and getting this transition wrong is the single most common bug in sequence detectors.)
Encoding (3 bits needed since 5 states, ⌈log₂5⌉ = 3): A=000, B=001, C=010, D=011, E=100.
Next-state truth table (S2 S1 S0 = current state bits; N2 N1 N0 = next-state bits):
| S2 S1 S0 | x | State | N2 N1 N0 | Next | Output |
|---|---|---|---|---|---|
| 000 | 0 | A | 000 | A | 0 |
| 000 | 1 | A | 001 | B | 0 |
| 001 | 0 | B | 000 | A | 0 |
| 001 | 1 | B | 010 | C | 0 |
| 010 | 0 | C | 011 | D | 0 |
| 010 | 1 | C | 010 | C | 0 |
| 011 | 0 | D | 000 | A | 0 |
| 011 | 1 | D | 001 | B | 0 |
| 100 | 0 | E | 000 | A | 1 |
| 100 | 1 | E | 001 | B | 1 |
Reading off N0 (the least-significant next-state bit) across all ten rows and simplifying with a K-map (unused codes 101, 110, 111 are don't-cares): N0 = 1 exactly when `x=1` and current state ≠ C — i.e., `N0 = x · (S2' + S1' )'... ` simplifies cleanly to `N0 = x AND NOT(state=C)`; in terms of literal state bits, `N0 = x · (S1' + S0')` (true whenever x=1 and we are not in state C=010). Output logic (Moore): `OUT = S2` (only state E has S2=1). Both simplifications are directly verifiable by re-scanning the table — every row with `x=1` and state ≠ C shows N0=1, and every row with state=100 shows OUT=1, with no exceptions.
Trace on input stream `1 1 0 1 1 0 1`:
| Cycle | Input x | State before | State after | Output |
|---|---|---|---|---|
| 1 | 1 | A | B | 0 |
| 2 | 1 | B | C | 0 |
| 3 | 0 | C | D | 0 |
| 4 | 1 | D | B | 0 |
| 5 | 1 | B | C | 0 |
| 6 | 0 | C | D | 0 |
| 7 | 1 | D | B | 0 |
Wait — this trace never reaches `E`, exposing exactly why the overlap transition matters: the substring `1101` does appear (positions 1–4: `1,1,0,1`). Let's re-check cycle 4: state is `D` (seen "110") and x=1, so per the table `D` on `x=1` goes to `B`— but it should recognize completion of `1101` and go to `E`! This reveals an error in the state table above: the D→B transition on x=1 is wrong for detecting `1101` — it should be D on x=1 → E (pattern complete), and the overlap logic must be re-derived. Corrected table:
| Current | x=0 | x=1 |
|---|---|---|
| A | A | B |
| B | A | C |
| C | D | C |
| D | A | E |
| E | A | B |
Re-tracing `1 1 0 1`: A→B (x=1), B→C (x=1), C→D (x=0), D→E (x=1). Output at cycle 4 (state becomes E, Moore output read from E on the next cycle) is 1 one cycle later, at cycle 5, matching the "one cycle after pattern completes" specification. This correction is exactly the kind of transition error the pitfalls table below calls out — always re-derive each row from "what suffix of the pattern is still a valid prefix," not by pattern-matching the previous row.
Common pitfalls & traps
| Pitfall | Why it happens | Fix | ||
|---|---|---|---|---|
| Wrong "restart" transition on mismatch | Forgetting overlap: assuming mismatch always returns to start state | Recompute, for each state, the longest suffix of what's-seen-so-far that is still a valid prefix (KMP-style failure function) | ||
| Confusing Moore output timing | Expecting Moore output to reflect the current input immediately | Moore output reflects state entered on a previous edge — always one cycle behind an equivalent Mealy reaction | ||
| Mealy output glitches | Feeding a Mealy output directly into another circuit without re-registering it | Register Mealy outputs, or use Moore if the consumer needs a stable, glitch-free signal | ||
| Incomplete state table (missing input combinations) | Only drawing arrows for "interesting" transitions in the diagram | Every state must have an outgoing transition for every input combination; unspecified = bug | ||
| Ignoring unused encoded states | Binary encoding with | S | not a power of 2 leaves illegal codes reachable via glitches/reset faults | Treat unused codes as don't-cares in K-maps but also explicitly force them back to a safe state ("state design for testability") |
| Race between reading and writing state | Using latches instead of edge-triggered flip-flops for the state register | Always use edge-triggered D flip-flops for state; never combinational feedback loops |
Pioneers & history
Origins · 1 minGeorge H. Mealy and how this was discovered
George Mealy formalized the Mealy machine model in his 1955 paper "A Method for Synthesizing Sequential Circuits," giving engineers a rigorous way to design circuits whose outputs depend on both state and input — the model that still bears his name in every digital logic course and every HDL simulator today.
Edward F. Moore, working independently at Bell Labs around the same period, asked a complementary question: given only external input/output behavior, how few states are needed, and how do we tell two states apart from observation alone? His 1956 paper introduced state-equivalence and minimization — the theoretical basis for taking a sloppy, redundant state diagram and collapsing it to the fewest states that preserve behavior, a step now automated in every logic synthesis tool.
Where this matters
Every CPU control unit — whether the hardwired kind or a microprogrammed one — is architecturally a finite state machine: the "fetch, decode, execute, writeback" cycle in Datapath and Control is literally a Moore or Mealy machine whose states are pipeline stages or micro-operations and whose outputs are the control signals steering muxes, ALUs, and register writes. Communication protocol handlers (USB, PCIe link training, TCP connection states like SYN-SENT/ESTABLISHED/FIN-WAIT) are textbook FSMs, as are bus arbiters that decide which requester gets the shared bus each cycle. Traffic light controllers, elevator dispatchers, vending machines, and garage-door openers are the canonical teaching examples precisely because they map so cleanly onto states and transitions. In FPGA and ASIC design, FSMs are one of the most common HDL idioms (`always @(posedge clk) case(state) ...`), and synthesis tools automatically choose between binary, one-hot, and Gray encodings depending on the target device's flip-flop-to-logic ratio. Even software state machines — parsers, regular-expression engines, game AI behavior trees — borrow the same Moore/Mealy vocabulary because the underlying mathematics of finite automata is identical whether the "flip-flops" are silicon or a variable in a program.
Ask the tutor: How would you extend a Mealy sequence detector to recognize overlapping occurrences of two different patterns simultaneously?
Can every Mealy machine be converted to an equivalent Moore machine?
Yes, though it may require more states. The standard construction splits each Mealy state into multiple Moore states, one per distinct (predecessor state, input) pair that leads into it, so each new state can carry a fixed output. Formally, this is always possible because both models define the same class of languages (regular languages) recognizable by finite automata with output. The practical cost is state count: a Moore equivalent can need up to |Σ| times as many states as the original Mealy machine in the worst case, since the output that used to depend on the incoming edge must now be baked into a distinct state. This is why real designs pick Mealy when reaction latency matters and state count is at a premium, and Moore when output stability and simplicity matter more.
Why does an FSM need a clock at all — why not just let the logic run free?
Without a clock, the next-state logic's output would feed directly back into itself asynchronously, changing continuously as gate delays propagate, with no defined moment to say "now the state has officially updated." This can cause oscillation, race conditions, and metastability, as explored in Clocks and Timing. The clock provides a single, globally agreed instant (the edge) at which the state register samples its input and holds it stable until the next edge, giving every other part of the system a guaranteed window during which the state is well-defined and won't change underneath them. This discipline — "compute freely, but only commit at the edge" — is what makes synchronous digital design analyzable and composable at all.
How do you choose between binary, one-hot, and Gray-code state encoding in practice?
It depends on the target technology and priorities. In ASICs or when flip-flops are relatively expensive/power-hungry, binary encoding minimizes register count, accepting more complex next-state logic. In FPGAs, flip-flops are abundant (one per logic cell) but routing and logic levels are the bottleneck, so one-hot encoding — with its typically shallow, wide OR-based next-state equations — often synthesizes to a faster, simpler circuit despite using more flip-flops. Gray-code encoding is chosen when adjacent-state transitions must differ in only one bit, which matters for reducing glitches when the state feeds asynchronous circuitry or crosses clock domains. Most synthesis tools let you specify the encoding style as a compiler directive and will pick a reasonable default (often one-hot for FPGAs) if you don't.
What is state minimization and why does it matter?
State minimization finds the smallest possible state diagram that produces identical input/output behavior as a given (possibly redundant) one, by merging states that are behaviorally indistinguishable — Edward Moore's original 1956 contribution. Two states are equivalent if, for every possible future input sequence, they produce identical output sequences and transition to equivalent states. Minimizing state count before encoding reduces flip-flop count, simplifies next-state and output logic, and can shorten critical paths. Tools implement this via partition-refinement algorithms that iteratively split states into equivalence classes based on observed output and next-class behavior, converging in at most |S| refinement rounds since each round either stops or strictly increases the number of classes.
How does an FSM relate to a regular expression or regular language?
Finite state machines and regular expressions describe exactly the same class of languages — the regular languages — by the Kleene/Myhill–Nerode equivalence theorems from automata theory. Any regular expression can be mechanically compiled into an equivalent FSM (via Thompson's construction plus subset construction to make it deterministic), and conversely any FSM's accepted language can be written as a regular expression. This is why the sequence-detector example in this article is structurally identical to how a regex engine's `1101` pattern would be compiled into hardware or software: both are finite automata with the same states-and-transitions core, just different substrates (gates versus bytecode).
Does adding more states always make an FSM "more powerful"?
No — finite state machines, no matter how many states, can only recognize regular languages, and cannot count unboundedly or match arbitrarily nested structure (like balanced parentheses of unbounded depth), which requires a pushdown automaton or a stack. Adding states only helps distinguish more finite histories (e.g., detecting longer fixed patterns, or tracking more distinct "modes"), not add fundamentally new computational capability. In hardware terms, this means a plain FSM can never implement, say, a general-purpose arbitrary-depth call stack by itself — it would need external memory (a real stack or RAM) working alongside the FSM control logic, which is exactly the relationship between control units and datapaths in Datapath and Control.
What's the most common real bug when implementing an FSM in hardware description language code?
Incomplete case statements — forgetting to specify the next-state or output logic for every reachable (and ideally every representable) state/input combination. In HDLs like Verilog or VHDL, an unspecified case defaults to inferring a latch instead of clean combinational logic (because the synthesis tool assumes "hold previous value" when no assignment is given), silently introducing unintended latches into what was meant to be a purely combinational next-state block. The fix is a disciplined default: always include a `default:` (or `others =>`) branch covering every state, including illegal/unused encoded states, explicitly routing them to a safe reset state as discussed in the pitfalls above.