1. Home
2. Academy
3. State Machines from Zero
4. Volume 01

1.1 Machines that remember: everyday examples

A state machine is anything that is always in one of a few situations, and moves between them when something happens.

A turnstile

Think of the turnstile at a metro station or a stadium gate. It has a rotating arm, a slot for a coin or a card, and a lock. It can be in only two situations:

• Locked. The arm will not turn. You cannot walk through.
• Unlocked. The arm turns once, and lets one person through.

Two things can happen to it. You can put in a coin, or you can push the arm. Here is what the turnstile does in each case:

1. It is locked, and you put in a coin. It unlocks.
2. It is unlocked, and you push the arm. You walk through, and it locks again behind you.
3. It is locked, and you push the arm. Nothing happens. It stays locked.
4. It is unlocked, and you put in another coin. Nothing changes. It stays unlocked.

Now look closely at "you push the arm". Sometimes a push lets you through. Sometimes it does nothing. The push is the same. What differs is the situation the turnstile was already in. To behave correctly, the turnstile must remember whether someone has paid.

That memory is what makes it a state machine. Each situation it can be in is called a state. The turnstile has two states: LOCKED and UNLOCKED.

State machines are everywhere

Once you know what to look for, you see state machines all around you:

The last one is worth a second look. A lamp with a single push-button turns on when you press it, and off when you press it again. The same press does opposite things. That only works because the lamp remembers whether it is on.

The exact version

Engineers call these circuits finite state machines, or FSMs for short. Finite means the number of states is fixed and countable - two for the turnstile, three for the traffic light. A finite state machine is always in exactly one of its states. It moves between them only when its inputs tell it to.

1.2 States, inputs, outputs and transitions

Every state machine is described by four things: its states, its inputs, its outputs, and its transitions - the rules for moving between states.

Let us take the turnstile apart, one piece at a time.

States

The states are the situations the machine can be in. The turnstile has two: LOCKED and UNLOCKED. At every moment it is in exactly one of them - never both, never neither.

One state is special: the reset state, where the machine starts. A turnstile should start LOCKED. Otherwise, the first person after a power cut would walk through for free.

Inputs

The inputs are the things that happen to the machine from outside. The turnstile has two inputs: coin (a coin goes in) and push (someone pushes the arm).

Outputs

The outputs are what the machine does to the world. The turnstile has one output, locked. When locked is 1, a small motor holds the arm still. When locked is 0, the arm is free to turn. Some turnstiles also have a green "go" lamp, which is simply the opposite of locked.

Transitions

A transition is a move from one state to another. Each transition has a condition: "if I am in this state, and this input happens, go to that state." The turnstile has four transitions:

Two of these rows do not change the state at all: LOCKED + push stays LOCKED, and UNLOCKED + coin stays UNLOCKED. These still count as transitions. A transition that returns to the same state is called a self-loop, and it means "stay where you are".

1.3 Drawing a state diagram

A state diagram draws each state as a circle and each transition as an arrow, labelled with the input that causes it.

Tables are precise, but they are hard to take in at a glance. So engineers usually draw a state machine first. The drawing is called a state diagram. It has only four ingredients:

1. A circle for each state, with the state's name inside.
2. An arrow for each transition, from the old state to the new one. The arrow is labelled with the input that makes it happen.
3. A looping arrow for each self-loop - an arrow that leaves a state and comes back to it.
4. A short arrow marked reset, pointing at the state where the machine starts.

Figure 1.1 is the turnstile, drawn this way.

To read a state diagram, put your finger on the reset state. Then follow the arrow that matches each input. Start at LOCKED. A coin arrives, so follow the coin arrow - you are now at UNLOCKED. Someone pushes, so follow the push arrow - you are back at LOCKED. Someone pushes again, so follow the push loop - you stay at LOCKED.

A second example: a traffic light

A simple traffic light has three states: GREEN, YELLOW and RED. It has one input, called done. A timer sets done to 1 when the current colour has been on for long enough. Until then, done is 0.

The rules are:

• In any state, while done = 0, stay in that state.
• When done = 1, move on to the next colour: GREEN to YELLOW, YELLOW to RED, and RED back to GREEN.

How to check a state diagram

A good state diagram passes two tests. Check them for every state:

1. Nothing is missing. The arrows leaving the state cover every possible input. In Figure 1.2, each state has an arrow for done = 0 and an arrow for done = 1.
2. Nothing clashes. No input value appears on two arrows leaving the same state. The machine cannot go to two places at once.

1.4 The state table

A state table holds the same information as a state diagram, in rows. The current state and the inputs go in; the next state and the outputs come out.

A diagram is easy to read. A table is easy to check, and it is the form you will turn into gates in Volume 03 and into code in Volume 04. So engineers keep both.

A state table has one row for every combination of state and input. Each row gives the next state and the outputs. Here is the turnstile:

The state the machine is in now is called the current state. The output, locked, depends only on the current state here: it is 1 in LOCKED and 0 in UNLOCKED.

In hardware, every input is a bit

So far we have treated "coin" and "push" as events that happen one at a time. In a circuit, they are two wires, and each is a bit. At any moment, coin can be 0 or 1, and push can be 0 or 1. So there are four input combinations: nothing, push only, coin only, and both at once.

"Both at once" sounds unlikely, but in hardware it will happen sooner or later - and the table must say what to do. Here is the full table, with a row for every combination:

Two rows were design decisions. In LOCKED with both inputs, we unlock, because a coin was paid. In UNLOCKED with both inputs, we lock, because someone walked through. That second choice loses the new coin - a real ticket gate would need to count coins. Writing the full table forced us to notice the problem. That is exactly what tables are for.

How many rows?

If your table has fewer rows than this, some case is missing.

A shorter layout

When there are only a few inputs, a table can put one column per input value. Each cell is then the next state. Here is the traffic light from Figure 1.2 in this shorter form:

Both layouts carry the same facts. Use whichever is easier to read for the machine in front of you.

1.5 Why hardware needs a clock

In hardware, a state machine moves only at clock edges. The clock keeps every part of the machine in step.

The three blocks inside every state machine

Every clocked state machine is built from the same three blocks. Figure 1.3 shows them.

1. The state register is a group of flip-flops. It holds the current state as a pattern of bits.
2. The next-state logic is made of gates. It looks at the current state and the inputs, and works out the next state.
3. The output logic is also made of gates. It looks at the current state and works out the outputs.

Notice the purple line. The current state leaves the register and goes back into the next-state logic. A path that brings a result back to its own start is called feedback. Feedback is how the machine's past affects its future.

What happens in one clock cycle

1. During the cycle, the state register holds the current state steady.
2. The next-state logic sees the current state and the inputs, and works out the next state. Its answer waits at the register's input.
3. At the rising clock edge, the register copies that answer. The machine has moved.
4. The new state flows back through the feedback line, and the next-state logic starts working on the move after that.

Why not leave the clock out?

Imagine the same circuit with no clock - the gates connected straight back to themselves. The next-state logic would compute a new state, which would feed straight back in, which could change the answer again, and again, as fast as the gates can switch. The machine would race through states with no control. And if the state has several bits, some bits would change a little before others. For a short moment, the state would be a mix of old and new bits - a state that should not exist.

The clock fixes all three problems:

• The flip-flops break the feedback loop. A new state takes effect only at the next edge, so the machine moves exactly once per cycle.
• All the flip-flops change at the same instant, so the state is never a mix of old and new.
• The machine looks at its inputs only at the edges, so short changes between edges are ignored.

A circuit that moves in step with a clock like this is called synchronous. Every state machine in this course is synchronous.

The turnstile on a clock

Figure 1.4 shows the turnstile running on a clock. Coin and push are now two input wires, and each is 1 during the cycle when that event happens.

1. Edge 2. Coin was 1 during the cycle before this edge. The state becomes UNLOCKED, and locked drops to 0.
2. Edge 4. Push was 1. The state becomes LOCKED again.
3. Edge 5. Push was 1 again, but the turnstile was already locked. It stays LOCKED - the push self-loop.
4. Edge 6. A coin: the state becomes UNLOCKED.
5. Edge 7. A second coin while unlocked. It stays UNLOCKED - the coin self-loop.

A first look at the code

You will learn to write state machines in Volume 04. But it is worth seeing now how closely the code follows the diagram. Each else if line below is one arrow of Figure 1.1:

module turnstile (
  input  wire clk, rst, coin, push,
  output wire locked
);
  localparam LOCKED = 1'b0, UNLOCKED = 1'b1;   // the two states
  reg state;                                    // the state register

  always @(posedge clk) begin                   // move only at a rising edge
    if (rst)                            state <= LOCKED;    // the reset arrow
    else if (state == LOCKED   && coin) state <= UNLOCKED;  // coin arrow
    else if (state == UNLOCKED && push) state <= LOCKED;    // push arrow
  end                                           // no match: stay (the self-loops)

  assign locked = (state == LOCKED);            // the output logic
endmodule

What you learned

• A state machine is always in exactly one of a fixed number of states, and remembers which.
• It is described by four lists: states (with a reset state), inputs, outputs and transitions.
• A state diagram shows states as circles and transitions as labelled arrows. Every state needs an arrow for every input, and no two arrows may clash.
• A state table holds the same facts in rows. A full table has states × 2^{input bits} rows.
• Inside every clocked state machine are a state register, next-state logic and output logic, with the state fed back.
• The clock makes the machine move exactly once per cycle, with every flip-flop changing together.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• State machine (FSM)
• State
• Finite
• Reset state
• Input
• Output
• Transition
• Self-loop
• State diagram
• State table
• Next state
• Current state
• State register
• Next-state logic
• Output logic
• Feedback
• Synchronous

Practice

Interview corner

Next, Volume 02 looks closely at the outputs - and shows that there are two quite different ways for a state machine to make them.