JOVANA
Explore Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

Finite State Machines in Hardware

A latch remembers, a clock keeps time, an adder computes — but how does a circuit decide what to do next? Meet the finite state machine: the small, disciplined pattern that turns memory plus logic into a hardware controller, and the seed of every control unit you will ever build.

From remembering to deciding

By now this rung has handed you a full toolbox. A flip-flop remembers one bit across a tick; a register is a row of them remembering a whole word; the clock makes every register snapshot its input at the same instant; and combinational logic — adders, multiplexers, decoders — computes a fresh output the moment its inputs settle. What we have not yet built is the thing that ties them together: a circuit that does not merely store or compute, but decides what to do next based on where it currently is. That is the job of a finite state machine.

The everyday picture is a traffic light. It is always in exactly one of a small, finite set of situations — green, yellow, red — and that situation, the state, is all it needs to remember about the entire past. When the timer fires it moves to the next state by a fixed rule: green goes to yellow, yellow to red, red back to green. It never needs a history book of every car that ever passed; the present state already captures everything that matters. A finite state machine is exactly this idea rendered in gates: a handful of named states, and rules for hopping between them.

The anatomy: one register, two logic blocks

Here is the beautiful part — every finite state machine in hardware has the same three-piece skeleton, and you already know all three pieces. First, a state register: a small bundle of flip-flops that holds the current state as a bit pattern (with k flip-flops you can name up to 2^k states). Second, a block of combinational logic called the next-state logic, which looks at the current state plus any inputs and computes which state to enter next. Third, another combinational block, the output logic, which turns the current state (and maybe the inputs) into the machine's outputs. Wire the next-state output back into the register's input, and you have closed the loop that gives the machine its memory of where it is.

                 +-------------------+
   inputs ------>|  next-state logic |---- next state ---+
        |    +-->| (combinational)   |                  |
        |    |   +-------------------+                  v
        |    |                                 +------------------+
        |    |   current state <---------------| state register   |<-- clock
        |    |          |                      |  (flip-flops)    |
        |    +----------+                      +------------------+
        |               |
        v               v
   +-------------------+
   |   output logic    |----> outputs
   |  (combinational)  |
   +-------------------+

  one clock tick: register latches the computed next state -> it becomes
  the new current state -> logic recomputes outputs and the next next-state.
The universal FSM skeleton: a state register feeding back through combinational next-state and output logic. Everything sequential in a CPU is built from this shape.

Notice how cleanly this splits the world along the line drawn in the previous guides. All the deciding and computing happens in the combinational blocks, which settle to a steady answer between ticks; all the remembering happens in the one register, which only changes at the clock edge. This is synchronous design in its purest form: nothing about the machine's state is ever in flux during a cycle, so you never have to reason about half-finished transitions. The machine steps, frozen frame by frozen frame, one state per tick.

Moore and Mealy: where the output lives

There are two honest flavours of finite state machine, and the difference is exactly where the output comes from. In a Moore machine the output depends only on the current state — the traffic light shows green simply because it is in the green state, full stop. In a Mealy machine the output depends on the current state and the current inputs together, so the output can react within the same cycle that an input arrives. Mealy machines often need fewer states because each state can do more work, but their outputs can glitch as inputs wiggle mid-cycle; Moore machines are a little larger but their outputs are rock-steady because they change only when the state does.

Let's make it concrete with a tiny example: a coin-operated turnstile that costs one token. It has two states — Locked and Unlocked — and two inputs: a token, or a push. Trace it as a Moore machine. Start in Locked; the output 'gate solenoid' is off, so the bar stays put. Drop a token and the next-state logic sends it to Unlocked, where the solenoid output goes on and the bar yields. Push through and the next-state logic returns it to Locked. Two states, a couple of transition rules, and you have captured the whole behaviour of a real device with nothing but a one-bit register and a sliver of logic.

Now watch how little it takes to make that real. Encode Locked as the bit 0 and Unlocked as the bit 1 — a single flip-flop is enough, since there are only two states. The next-state rule reads straight off the description: from Locked a token sends you to 1 and a push keeps you at 0; from Unlocked a push sends you back to 0 and a token leaves you at 1. The output (solenoid on or off) is simply the state bit itself, which is what makes it a Moore machine — the output is on exactly when the state is Unlocked. A one-bit register plus a pinch of boolean algebra for the next-state function, and the device is done.

Building one: from diagram to gates

The reason finite state machines matter so much is that there is a mechanical recipe from 'what I want it to do' all the way down to a working circuit. You do not have to be clever; you follow the steps. This is the same disciplined path you will walk, at far larger scale, when you design a real controller.

  1. Draw the state diagram: a bubble for each state, an arrow for each transition labelled with the input that causes it. Make sure every state has an arrow for every possible input, so the machine is never stuck or undefined.
  2. Encode the states as bit patterns. With S states you need at least ceil(log2 S) flip-flops; choose an assignment (0, 1, 10, 11, ...) — and that choice of encoding fixes the size of your state register.
  3. Fill in the state table: for every (current state, input) pair, write down the next state and the outputs. This table IS the specification — nothing is left to interpretation.
  4. Turn each column of the table into a truth table and derive the combinational logic with the boolean-algebra and Karnaugh-map tools from this rung's first guide. The next-state bits and output bits are just boolean functions of the current-state bits and inputs.
  5. Wire it: feed the next-state logic into the state register's inputs, clock the register, and feed its outputs back to the next-state and output logic. Done — the loop is closed and the machine runs one state per tick.

Why this is the heart of a processor

Step back and look at what you have just built, because it is bigger than a turnstile. Recall the fetch-decode-execute cycle from the foundations rung: a processor endlessly fetches an instruction, decodes it, executes it, then advances to the next. That loop is a finite state machine. Its states are the phases of the cycle; its inputs are the bits of the current instruction; and its outputs are the control signals that steer the datapath — telling the ALU which operation to do, telling registers when to load, telling the multiplexers which source to choose.

This is precisely the control unit of a CPU. The processor's control unit is, at its core, a finite state machine whose outputs are control signals and whose job is to march the datapath through the right sequence of micro-steps for whatever instruction it is running. When engineers build it as a tangle of gates derived from a state table, exactly as you just learned, they call it hardwired control. (There is a softer alternative — storing the control signals for each step in a tiny memory, called microprogramming — but underneath, the sequencer that walks through it is still a finite state machine.) Either way, the controller that brings a whole processor to life is the very pattern from this guide, scaled up.

So this single idea is the keystone of the whole rung. The transistor became a switch; switches became gates; gates became combinational blocks like the adder and the multiplexer; flip-flops gave those gates a memory; the clock disciplined that memory into sequential logic; and now the finite state machine organises memory and logic into something that decides and sequences. Climb one rung higher and you will assemble these into a real datapath and watch this very controller drive a working instruction set — but the controller's beating heart will still be the humble finite state machine you can now build by hand.