Lesson 23 · Memory elements and clocks

State machines

A finite state machine is a circuit that remembers which of a few states it is in and moves between them on each clock edge. Follow a traffic light through GREEN, YELLOW and RED: see its state diagram, the flip-flops that hold the state, the next-state logic that reads a timer input, the output logic that drives the lamps, and the difference between Moore and Mealy machines.

12 min9 steps5 questionsBeginner

Fig 23 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01In a state diagram, what does an arrow show?

Circles are states. An arrow is a possible move, labelled with the input that makes it happen, such as T=1.

02A machine has 3 states and stores them in binary in flip-flops. What is the fewest number of flip-flops it needs?

One flip-flop gives 2 patterns, too few. Two flip-flops give 4 patterns (00, 01, 10, 11), enough for 3 states.

03The timer input T becomes 1 while the light is GREEN. When does the state register change to YELLOW?

Next-state logic works out 01 at once, but the flip-flops only copy it on the next rising clock edge.

04Which three parts make up a state machine circuit?

The register holds the state; next-state logic decides where to go; output logic turns the state (and, in a Mealy machine, the inputs) into outputs.

05In a Moore machine, the outputs depend on what?

Moore outputs come only from the state, so they change only after a clock edge. Mealy outputs also read the inputs.

Key terms

Glossary

Finite state machine (FSM): A circuit that is always in one of a fixed, small number of states and moves between them by fixed rules.
State: Which situation the machine is in right now, such as GREEN. It is stored as bits.
State diagram: A drawing of a state machine: one circle per state and one arrow per possible move, labelled with the input that causes it.
Flip-flop: A one-bit memory. A D flip-flop copies its input to its output on the rising edge of the clock and holds it otherwise.
Clock edge: The moment the clock signal changes. On a rising edge it goes from 0 to 1, and every flip-flop updates together.
Next-state logic: Gates that work out the next state from the current state and the inputs.
Output logic: Gates that turn the state (and in a Mealy machine the inputs) into the machine's outputs.
Moore and Mealy: Moore machine: outputs depend only on the state. Mealy machine: outputs depend on the state and the inputs.

Fine print

Notes and sources

A finite state machine is a state register (flip-flops) plus two blocks of combinational logic: next-state logic and output logic (Harris and Harris, Digital Design and Computer Architecture, section 3.4).
A D flip-flop copies its input to its output only on the rising edge of the clock and holds it at all other times. Texas Instruments' SN74HC74 holds two of them in one chip.
Moore machine: the outputs depend only on the current state. Mealy machine: the outputs depend on the current state and the inputs. The names come from Edward F. Moore (1956) and George H. Mealy (1955).
With n flip-flops a register can hold 2^n patterns, so two flip-flops are enough for three states. Here the unused pattern 11 is sent back to GREEN, a safe choice if it ever appears.
Real traffic controllers time each light and also read sensors and push buttons; this machine keeps only the timer so the idea stays clear.

Quiz Unlocks after the last step.