# Finite state machines

*A circuit that steps through states*

A finite state machine (FSM) is a circuit that holds one of a fixed set of states in a register and, on each clock edge, moves to a next state chosen by combinational logic from the current state and inputs. It is the standard way to build a controller that steps through a sequence.

Group: Processor
URL: https://digiwleea.wleeaf.dev/learn/state-machine/

You can now [store state](https://digiwleea.wleeaf.dev/learn/regbit/) and [clock](https://digiwleea.wleeaf.dev/learn/clock/) it. The natural next step is a circuit that does not just hold a value but **walks through a planned sequence of values**, one per clock: step 1, step 2, step 3, then loop. That pattern, a circuit that lives in one of a fixed set of **states** and moves between them on the clock, is a **finite state machine** (FSM). It is the shape of every controller, and in particular the CPU's [control unit](https://digiwleea.wleeaf.dev/learn/control/) is one.

## State register plus next-state logic

Every FSM is two pieces wired in a loop:

- A **state register** (a bank of [flip-flops](https://digiwleea.wleeaf.dev/learn/dff/)) that remembers which state the machine is in right now. It updates only on the clock edge, so the state is rock-steady between edges.
- **Next-state logic** (pure [combinational](https://digiwleea.wleeaf.dev/learn/clock/) gates) that looks at the current state and the inputs and computes which state to enter next. Its output feeds back into the state register's input.

On each [clock](https://digiwleea.wleeaf.dev/learn/clock/) edge the register loads the next state, which changes what the next-state logic produces, which becomes the input for the *following* edge. So the machine advances one step per clock. Often there is also **output logic** that turns the current state into useful control signals (which is exactly what drives a CPU's control lines).

> **KEY:** The feedback loop is safe for the same reason a [register bit](https://digiwleea.wleeaf.dev/learn/regbit/)'s was: the state register only samples on the **edge**. Between edges the next-state value is stable, so the loop cannot race. This is the whole reason sequential controllers are built around a clocked register instead of raw [combinational feedback](https://digiwleea.wleeaf.dev/learn/srlatch/), which has to be handled far more carefully.

## A worked example: a 4-step ring counter

The simplest concrete FSM in this course is a **ring counter**: it has four states, and exactly one of its outputs `T0, T1, T2, T3` is high in each state. The next-state rule is just 'rotate the high bit one position'. So its **state diagram** is a plain loop:

```
T0 -> T1 -> T2 -> T3 -> T0 -> ... (one step per clock edge)
```

Here the state register is four flip-flops (one per `T` line), and the next-state logic simply shifts each flip-flop's value into the next one, wrapping `T3` back to `T0`. (That makes a ring counter a [shift register](https://digiwleea.wleeaf.dev/learn/shift-register/) wired in a loop.) A reset forces the machine into a known starting state (`T0` high, the rest `0`) so it always begins in a defined place. This is exactly the stepper the [control unit](https://digiwleea.wleeaf.dev/learn/control/) uses to walk the micro-steps of an instruction.

_Circuit diagram: A 4-state ring-counter FSM (RING4): its state is which one of T0-T3 is high, and each clock edge rotates that to the next, looping T0 to T1 to T2 to T3 and back. RST forces the start state. Before the first clock the outputs read Z; open it in the lab, pulse reset, then run the clock and watch the single high state march around the ring._

> **TIP:** A useful way to design an FSM is to draw its **state diagram** first: a bubble for each state, and a labelled arrow for each transition (which input value sends you from one state to the next). Once the bubbles and arrows are fixed, the hardware is mechanical: number the states, store the number in a register, and build combinational logic that reads the current-state number plus inputs and outputs the next-state number. A [counter](https://digiwleea.wleeaf.dev/learn/counter/) is the special case where the transitions are just 'always go to the next number'.

**Q (Try it):** On the ring-counter FSM, you pulse `RST` (so `T0` is high) and then apply three clock edges. Which output is high after the third edge? In general, what two things decide an FSM's next state?

**A:** Starting at `T0`, three edges step `T0 -> T1 -> T2 -> T3`, so after the third edge `T3` is high. In general, an FSM's next state is decided by its **current state** and its **inputs**, combined by the next-state logic; the clock edge is just when that computed next state is loaded into the state register. (The ring counter has no data inputs, so here the next state depends only on the current state.)

> **KEY:** Finite state machines are how a circuit gets a sense of **sequence and time**: do this, then that, then loop. The CPU's [control unit](https://digiwleea.wleeaf.dev/learn/control/) is a state machine whose states are the micro-steps of fetch-decode-execute, whose inputs include the opcode, and whose outputs are the control lines that gate the [bus](https://digiwleea.wleeaf.dev/learn/tristate/) and trigger register loads. With the FSM idea in hand, that control unit is the next lesson.

### FAQ

**Q:** What is a finite state machine?

**A:** A finite state machine (FSM) is a circuit that holds one of a fixed set of **states** in a register and, on each [clock](https://digiwleea.wleeaf.dev/learn/clock/) edge, moves to a next state chosen by combinational logic from the current state and inputs. It is the standard way to build a controller that steps through a planned sequence.

**Q:** What are the parts of a finite state machine?

**A:** Three: a **state register** (flip-flops that remember the current state and update only on the clock edge), **next-state logic** (combinational gates that compute the next state from the current state and inputs), and often **output logic** (gates that turn the current state into useful control signals). The next-state output feeds back into the register's input.

**Q:** What is a state diagram?

**A:** A state diagram is a drawing of an FSM as bubbles (one per state) connected by labelled arrows (one per transition), where each arrow's label is the input condition that triggers that move. It is the design starting point: once the states and transitions are fixed, you number the states, store the number in a register, and build logic that maps current-state-plus-inputs to the next-state number.

**Q:** Is a counter a finite state machine?

**A:** Yes. A [counter](https://digiwleea.wleeaf.dev/learn/counter/) is the special case of an FSM whose states are the count values and whose only transition rule is 'go to the next number each clock'. A general FSM is more flexible because its transitions can branch on inputs, but the structure (state register plus next-state logic) is identical.