Finite state machines
A finite state machine is a sequential circuit that is always in one of a fixed set of states, moves between them on each clock according to its inputs, and produces outputs from where it is. Every counter, controller and protocol handler is one. This page explains the two kinds and works one through from specification to circuit, with every step generated and checked.
What a state machine is
Combinational logic answers a question about its inputs right now. A flip-flop remembers one bit. Put a few flip-flops together and feed their outputs back through some combinational logic into their inputs, and you have a circuit whose behaviour depends on its history: a state machine. The flip-flops hold the state, a code for "what has happened so far". On every clock edge the next-state logic looks at the state and the inputs and decides where to go. The output logic turns the state, and possibly the inputs, into the outputs.
"Finite" just means the set of states is fixed in advance. A 4-bit counter is a state machine with sixteen states and no inputs. A traffic light controller has a handful of states and a timer input. A vending machine remembers how much money has gone in. What makes them all the same thing is that they can be drawn as a diagram of circles and arrows, and designed by the same procedure.
Moore vs Mealy
The two kinds differ in one thing only: where the outputs come from.
Moore machine
Outputs depend on the state alone. They are written inside the state circles, change only on a clock edge, and stay steady for a whole cycle. Free of input-induced glitches and easy to reason about, at the cost of sometimes needing an extra state.
Mealy machine
Outputs depend on the state and the inputs. They are written on the arrows as input/output, can change the moment an input does, and typically respond a cycle earlier, often with fewer states. The price is outputs that can glitch while inputs settle.
Any Moore machine can be rewritten as a Mealy machine and vice versa, though the Moore version may need more states and its output lags by a cycle. The worked example below is done both ways, so the difference is visible in the diagrams, the equations and the timing.
The design procedure
- Draw the state diagram. One circle per situation the machine must remember, one arrow per input value from each.
- Write the state table. Every present state and input, with the next state and output. This is the diagram as data.
- Assign codes. Give each state a binary code; two bits cover up to four states. Codes nobody uses become don't cares.
- Choose flip-flops. With D flip-flops the input equation for each bit is simply its next-state column, which is why they are the usual choice.
- Derive the equations. Each next-state bit and each output is a boolean function of the state bits and inputs: simplify it with a Karnaugh map.
- Build and check. Wire the gates to the flip-flops, then run a test sequence through it and compare against the specification.
Worked example: a Moore detector for 101
Raises its output for one clock cycle after it has seen the bits 1, 0, 1 arrive in order, overlaps allowed.
The specification: watch a stream of bits x, one per clock, and raise z whenever the last three bits were 1, 0, 1. Overlaps count, so 10101 contains the pattern twice. The machine needs to remember how much of the pattern it has seen so far, which gives four states: nothing useful, seen 1, seen 10, and seen 101. In a Moore machine the output belongs to that last state.
State diagram
Arrows are labelled with the input; the output is written inside each state, and the code under it.
State table
| Present state | x | Next state | z |
|---|---|---|---|
| S0 00 nothing useful seen yet | 0 | S0 00 | 0 |
| S0 00 nothing useful seen yet | 1 | S1 01 | 0 |
| S1 01 seen 1 | 0 | S2 10 | 0 |
| S1 01 seen 1 | 1 | S1 01 | 0 |
| S2 10 seen 10 | 0 | S0 00 | 0 |
| S2 10 seen 10 | 1 | S3 11 | 0 |
| S3 11 seen 101 | 0 | S2 10 | 1 |
| S3 11 seen 101 | 1 | S1 01 | 1 |
Equations
With D flip-flops, each next-state bit is a function of the present state bits and the input, read straight off the table and simplified on a Karnaugh map. The state bits are Q1 and Q0, written a = Q1, b = Q0 in the expressions; the timing diagram below writes the same signals in capitals.
- d1
- b ∧ ¬x ∨ a ∧ ¬b ∧ x
- d0
- x
- z
- a ∧ b
d1 and d0 are the D inputs of the flip-flops holding Q1 and Q0; z is the output. Notice that z depends only on the state bits: that is what makes it Moore.
The combinational part
The outputs d1 and d0 feed two D flip-flops whose outputs Q1 and Q0 come back in as a = Q1, b = Q0. The flip-flops and the feedback wires are the only parts not drawn.
Timing
The machine run on the input 0101101001011, one bit per cycle, starting in S0. Each dashed line is a clock edge, where the state changes.
The same run as a table
| Cycle | x | State | Next | z |
|---|---|---|---|---|
| 1 | 0 | S0 | S0 | 0 |
| 2 | 1 | S0 | S1 | 0 |
| 3 | 0 | S1 | S2 | 0 |
| 4 | 1 | S2 | S3 | 0 |
| 5 | 1 | S3 | S1 | 1 |
| 6 | 0 | S1 | S2 | 0 |
| 7 | 1 | S2 | S3 | 0 |
| 8 | 0 | S3 | S2 | 1 |
| 9 | 0 | S2 | S0 | 0 |
| 10 | 1 | S0 | S1 | 0 |
| 11 | 0 | S1 | S2 | 0 |
| 12 | 1 | S2 | S3 | 0 |
| 13 | 1 | S3 | S1 | 1 |
The same machine as a Mealy detector
The same detector with the output on the transitions, which saves a state and flags the pattern a cycle earlier.
Moving the output onto the arrows removes the need for a "seen 101" state: the machine can announce the match on the very transition that completes it, from "seen 10" on a 1. Three states instead of four, and the flag appears one cycle earlier.
State diagram
Arrows are labelled input/output; there is no output in the states themselves.
State table
| Present state | x | Next state | z |
|---|---|---|---|
| S0 00 nothing useful seen yet | 0 | S0 00 | 0 |
| S0 00 nothing useful seen yet | 1 | S1 01 | 0 |
| S1 01 seen 1 | 0 | S2 10 | 0 |
| S1 01 seen 1 | 1 | S1 01 | 0 |
| S2 10 seen 10 | 0 | S0 00 | 0 |
| S2 10 seen 10 | 1 | S1 01 | 1 |
Equations
With D flip-flops, each next-state bit is a function of the present state bits and the input, read straight off the table and simplified on a Karnaugh map. The state bits are Q1 and Q0, written a = Q1, b = Q0 in the expressions; the timing diagram below writes the same signals in capitals. The unused code 11 is a don't care, which is what lets d1 lose a literal.
- d1
- b ∧ ¬x
- d0
- x
- z
- a ∧ x
d1 and d0 are the D inputs of the flip-flops holding Q1 and Q0; z is the output. Notice that z depends on x as well as the state: that is what makes it Mealy.
The combinational part
The outputs d1 and d0 feed two D flip-flops whose outputs Q1 and Q0 come back in as a = Q1, b = Q0. The flip-flops and the feedback wires are the only parts not drawn.
Timing
The machine run on the input 0101101001011, one bit per cycle, starting in S0. Each dashed line is a clock edge, where the state changes.
The same run as a table
| Cycle | x | State | Next | z |
|---|---|---|---|---|
| 1 | 0 | S0 | S0 | 0 |
| 2 | 1 | S0 | S1 | 0 |
| 3 | 0 | S1 | S2 | 0 |
| 4 | 1 | S2 | S1 | 1 |
| 5 | 1 | S1 | S1 | 0 |
| 6 | 0 | S1 | S2 | 0 |
| 7 | 1 | S2 | S1 | 1 |
| 8 | 0 | S1 | S2 | 0 |
| 9 | 0 | S2 | S0 | 0 |
| 10 | 1 | S0 | S1 | 0 |
| 11 | 0 | S1 | S2 | 0 |
| 12 | 1 | S2 | S1 | 1 |
| 13 | 1 | S1 | S1 | 0 |
Unused states
Two bits give four codes, and the Mealy machine uses three of them. During design the fourth is a don't care, and the minimal equations send it wherever makes the maps simplest. A real design has to ask what that is: if a glitch at power-up lands the machine in the unused code, will it find its way back? Simulate the equations from every code, or give every unused code an explicit arrow to the reset state and accept the extra gate or two. Either is fine; not checking is not.
Build one
Two D flip-flops, a toggle for x, a clock, and the gates for the Moore equations:
- d1
- b ∧ ¬x ∨ a ∧ ¬b ∧ x
- d0
- x
- z
- a ∧ b
with a = Q1, b = Q0. The simulator has no flip-flop node, so build a D flip-flop from gates, as the D flip-flop page outlines and the learning path shows for the latch inside it, and package it as a custom node; two of those, an Interval node as the clock, and the gates above make the whole detector. Feed it 1, 0, 1 on successive clocks and watch z rise one cycle later.
Counters are the same procedure with no input: the counters page shows a decade counter and how to design one that runs through any sequence you choose, and the flip-flop pages have the excitation tables you need if you use JK or T flip-flops instead of D.
Questions about state machines
What is a finite state machine?
A sequential circuit that is always in exactly one of a fixed, finite set of states. On each clock edge it moves to a next state chosen by its present state and its inputs, and it produces outputs from its state, or from its state and inputs together. Counters, controllers, protocol handlers and sequence detectors are all finite state machines; in hardware one is a register holding the state plus combinational logic computing the next state and the outputs.
What is the difference between a Moore machine and a Mealy machine?
In a Moore machine the outputs depend only on the present state, so they change only on a clock edge and are stable for a whole cycle. In a Mealy machine the outputs depend on the present state and the inputs, so they can change as soon as an input does and can respond a cycle earlier. A Mealy machine often needs fewer states for the same job; a Moore machine has outputs that cannot glitch when an input does.
How do you design a finite state machine?
Draw the state diagram from the specification, list it as a state table, assign a binary code to each state, choose a flip-flop type, derive the flip-flop input equations and the output equations from the table using Karnaugh maps, and build the circuit. Unused state codes are don't cares in the maps. Then simulate it against the specification, which is what the diagrams on this page do.
What is a state table?
The state diagram written as a table: one row per combination of present state and input, giving the next state and the output. With the states replaced by their binary codes it is a truth table whose inputs are the state bits and the machine inputs, and whose outputs are the next-state bits and the machine outputs, which is what the flip-flop logic is designed from.
How many flip-flops does a state machine need?
Enough bits to give every state a distinct code: for n states, the smallest whole number of bits not less than log₂ n, so two flip-flops for three or four states and three for five to eight. One-hot encoding uses one flip-flop per state instead, which costs more flip-flops but usually simpler next-state logic, and is common in FPGAs.
What happens if a state machine enters an unused state?
Codes that no state uses are don't cares during design, so the minimal logic sends them wherever is convenient, which could be a loop the machine never leaves. A robust design either checks what the derived equations do with every unused code, or assigns every unused code an explicit transition to the reset state, at the cost of slightly larger logic.