Finite state machines

Almost every piece of control logic in an FPGA is a finite state machine, whether or not the person who wrote it called it one. A UART receiver waiting for a start bit, a memory controller stepping through a refresh, a button handler deciding whether a press was short or long: all of them are a small set of named states, rules for moving between them and outputs that depend on where you are. This lesson shows you how to draw one, how to write it in Verilog and VHDL so that synthesis recognises it, and where the sharp edges are. You need the register and simulation material from lesson 04 and lesson 06.

What a state machine is

A state machine has three parts. A state register holds the current state, one value out of a small named set. Next-state logic looks at the current state and the inputs and decides what the state register loads on the next clock edge. Output logic produces the outputs. The state register is the only memory. Everything else is combinational logic, which means an FSM is nothing more than the register-plus-logic pattern you already know, with a name on each value the register can take.

The example for this lesson is a traffic light with a pedestrian crossing. It has four states: red, green, amber and a walk phase that only happens if someone has pressed the button. A slow tick input, one pulse per second from a timer like the one in lesson 08, advances a hold counter so that each light stays on for a sensible number of seconds.

State graph of the traffic-light controller. Each arc is taken on a tick when the hold count has reached zero.

Moore or Mealy

The two classic flavours differ in one thing: what the outputs depend on.

In a Moore machine the outputs are a function of the state alone. The traffic light is a Moore machine. Red is on because the state is S_RED, and nothing an input does during that state can change the lamp. Moore outputs are glitch-free when driven straight from the state register, they change only on clock edges, and they are easy to reason about. Their cost is latency: an input event changes the state on one edge and the output follows on the next.

In a Mealy machine the outputs depend on the state and the current inputs. The output can respond in the same cycle as the input, which saves a clock of latency, but the output is now combinational from an input and can glitch if the input does. This is a small sequence detector written as a Mealy machine. It looks for the pattern 101 on a serial input and raises found in the same cycle as the final 1 arrives.

// Mealy detector: `found` pulses in the same cycle as the last bit of "101".
module seq_mealy (
  input  wire clk,
  input  wire rst,
  input  wire din,
  output reg  found
);
  localparam [1:0] S_IDLE = 2'd0, S_1 = 2'd1, S_10 = 2'd2;
  reg [1:0] state;

  // One-process style: next state and output in one block.
  always @(posedge clk) begin
    if (rst)
      state <= S_IDLE;
    else
      case (state)
        S_IDLE: state <= din ? S_1 : S_IDLE;
        S_1:    state <= din ? S_1 : S_10;
        S_10:   state <= din ? S_1 : S_IDLE;
        default: state <= S_IDLE;
      endcase
  end

  // Mealy output depends on input as well as state, so it is combinational.
  always @(*)
    found = (state == S_10) && din;
endmodule

The 101 detector. The Mealy output rises in the cycle the final 1 arrives. A registered (Moore-style) version of the same output appears one edge later.

In practice most FPGA designers write Moore machines by default and register any Mealy output they need before it leaves the module. If you want a signal that is “the last bit arrived” but also clean, register it: the result is a Moore machine with one more state in disguise.

The two-process style

There are many ways to lay out an FSM in HDL. The one taught here is the two-process style: one clocked process holds the state register, and one combinational process computes the next state and the outputs. Here is the traffic light in Verilog.

// Traffic-light controller, Moore machine, two-process style.
// `tick` is a slow enable (for example once per second) from a timer.
// `walk_req` asks for a pedestrian phase at the next red.
module traffic_fsm (
  input  wire clk,
  input  wire rst,
  input  wire tick,
  input  wire walk_req,
  output reg  red,
  output reg  amber,
  output reg  green,
  output reg  walk
);
  // State encoding. Synthesis may recode this; see the lesson text.
  localparam [1:0] S_RED   = 2'd0,
                   S_GREEN = 2'd1,
                   S_AMBER = 2'd2,
                   S_WALK  = 2'd3;

  reg [1:0] state, state_next;
  reg [2:0] hold, hold_next;   // ticks remaining in the current state

  // Process 1: state register.
  always @(posedge clk) begin
    if (rst) begin
      state <= S_RED;
      hold  <= 3'd0;
    end else begin
      state <= state_next;
      hold  <= hold_next;
    end
  end

  // Process 2: next-state and output logic (combinational).
  always @(*) begin
    // Defaults first, so every path assigns every signal.
    state_next = state;
    hold_next  = hold;
    red = 1'b0; amber = 1'b0; green = 1'b0; walk = 1'b0;

    case (state)
      S_RED: begin
        red = 1'b1;
        if (tick) begin
          if (hold == 3'd0) begin
            if (walk_req) begin
              state_next = S_WALK;
              hold_next  = 3'd3;
            end else begin
              state_next = S_GREEN;
              hold_next  = 3'd4;
            end
          end else
            hold_next = hold - 3'd1;
        end
      end

      S_GREEN: begin
        green = 1'b1;
        if (tick) begin
          if (hold == 3'd0) begin
            state_next = S_AMBER;
            hold_next  = 3'd1;
          end else
            hold_next = hold - 3'd1;
        end
      end

      S_AMBER: begin
        amber = 1'b1;
        if (tick) begin
          if (hold == 3'd0) begin
            state_next = S_RED;
            hold_next  = 3'd2;
          end else
            hold_next = hold - 3'd1;
        end
      end

      S_WALK: begin
        red  = 1'b1;
        walk = 1'b1;
        if (tick) begin
          if (hold == 3'd0) begin
            state_next = S_RED;
            hold_next  = 3'd2;
          end else
            hold_next = hold - 3'd1;
        end
      end

      default: state_next = S_RED;
    endcase
  end
endmodule

Three details in the combinational block carry most of the weight.

Every signal it drives is given a default at the top. That guarantees that whatever path the case takes, each output and each _next signal has a value. If any path left one unassigned, the synthesiser would have to remember the previous value, and the only way to do that in combinational logic is a latch. Latches in an FPGA are slow, hard to time and almost always a mistake.

The case has a default arm. With two state bits and four states every pattern is used, but the habit matters for machines with five states in three bits, where the three spare codes are reachable through a glitch or a radiation event and the machine should recover rather than lock up.

Assignments in the combinational block use = and those in the clocked block use <=. Mixing them is legal and will usually simulate correctly, but keeping the rule makes the intent visible and avoids the few cases where it does not.

The hold counter is loaded when the machine enters a state, so the number of ticks spent there is one more than the value loaded. Entering S_GREEN with hold_next = 4 gives five ticks of green. Off-by-one questions like this are exactly what the testbench from the previous lesson is for, and a testbench for this module is in the exercise.

The same machine in VHDL

VHDL brings one real advantage to FSMs: an enumerated type. The states are named values of a type with no numeric encoding at all, and the synthesiser chooses one.

-- Traffic-light controller, Moore machine, two-process style.
library ieee;
use ieee.std_logic_1164.all;
use ieee.numeric_std.all;

entity traffic_fsm is
  port (
    clk      : in  std_logic;
    rst      : in  std_logic;
    tick     : in  std_logic;
    walk_req : in  std_logic;
    red      : out std_logic;
    amber    : out std_logic;
    green    : out std_logic;
    walk     : out std_logic
  );
end entity;

architecture rtl of traffic_fsm is
  type state_t is (s_red, s_green, s_amber, s_walk);
  signal state, state_next : state_t := s_red;
  signal hold, hold_next   : unsigned(2 downto 0) := (others => '0');
begin
  -- Process 1: state register.
  regs : process (clk)
  begin
    if rising_edge(clk) then
      if rst = '1' then
        state <= s_red;
        hold  <= (others => '0');
      else
        state <= state_next;
        hold  <= hold_next;
      end if;
    end if;
  end process;

  -- Process 2: next state and outputs.
  comb : process (all)
  begin
    state_next <= state;
    hold_next  <= hold;
    red <= '0'; amber <= '0'; green <= '0'; walk <= '0';

    case state is
      when s_red =>
        red <= '1';
        if tick = '1' then
          if hold = 0 then
            if walk_req = '1' then
              state_next <= s_walk;
              hold_next  <= to_unsigned(3, 3);
            else
              state_next <= s_green;
              hold_next  <= to_unsigned(4, 3);
            end if;
          else
            hold_next <= hold - 1;
          end if;
        end if;

      when s_green =>
        green <= '1';
        if tick = '1' then
          if hold = 0 then
            state_next <= s_amber;
            hold_next  <= to_unsigned(1, 3);
          else
            hold_next <= hold - 1;
          end if;
        end if;

      when s_amber =>
        amber <= '1';
        if tick = '1' then
          if hold = 0 then
            state_next <= s_red;
            hold_next  <= to_unsigned(2, 3);
          else
            hold_next <= hold - 1;
          end if;
        end if;

      when s_walk =>
        red  <= '1';
        walk <= '1';
        if tick = '1' then
          if hold = 0 then
            state_next <= s_red;
            hold_next  <= to_unsigned(2, 3);
          else
            hold_next <= hold - 1;
          end if;
        end if;
    end case;
  end process;
end architecture;

process (all) is VHDL-2008 and means “sensitive to everything read inside”. Before 2008 you had to list every signal by hand, and a missed one was a classic source of simulation and synthesis disagreeing. There is no when others arm because a case on an enumerated type must cover every value, and the compiler checks that it does.

One process or two

The one-process style puts the next-state logic and the outputs into the clocked block, as seq_mealy did. It is shorter and it cannot produce a latch, because everything in a clocked block is a register. Its drawbacks are that every output becomes registered, which adds a cycle of latency you may not want, and that in Verilog it is easy to write state <= S_GREEN in one branch and forget that the outputs for the state you are leaving are still being driven. Many experienced engineers use it anyway and are happy. The two-process style is taught here because it maps onto the state graph one to one: process 1 is the circle, process 2 is the arcs and the labels.

A three-process style, with a separate block for registered outputs, is a common refinement once the machine has more than a handful of outputs.

State encoding and what synthesis does

The Verilog version assigned numbers to the states by hand: 0, 1, 2, 3. That is binary encoding, the smallest number of flip-flops. Two other schemes are common.

Encoding	Flip-flops for N states	Strengths	Weaknesses
Binary	ceil(log2 N)	Fewest registers	Deepest next-state logic, several bits change per transition
Gray	ceil(log2 N)	One bit changes per transition on a simple ring	Awkward for machines with branches
One-hot	N	Shallowest logic, fastest, outputs often come free from state bits	N flip-flops, and N-1 of them are zero

Flip-flops are plentiful in an FPGA and logic depth sets the clock speed, so one-hot is the usual choice for machines with up to a few dozen states. You rarely have to pick. Vivado, Quartus Prime, Radiant, Gowin EDA and Yosys all perform FSM extraction: they spot a register whose value is only ever compared against and assigned from constants, rebuild the state graph, remove unreachable states and recode it. Vivado reports this in the synthesis log and, with its default auto setting, usually picks one-hot for small machines. You can override it with the fsm_encoding attribute, and the equivalent syn_encoding and fsm_encoding attributes exist in the other tools.

Two things stop extraction from happening. If the state register is read as a number anywhere, for example used as an index or sent out of the module, the tool has to keep your encoding. And if the reset value is not a constant, there is no known starting state. In both cases the machine still works, but with the encoding you wrote.

Common bugs

A short list, in the order you are most likely to meet them.

An inferred latch, from a missing default in the combinational process. Synthesis will warn you. Read the warnings.

A missing reset, so that the machine starts in whatever state the power-up value of the flip-flops happens to be. Most FPGAs initialise registers to zero from the bitstream, which hides the problem until a soft reset is added later.

An input sampled directly from a pin, such as a button, with no synchroniser. The state register has two or three bits, and a metastable input can send some of them one way and some the other, landing the machine in a state it never meant to visit. Synchronise every asynchronous input first, as lesson 08 shows.

A transition condition that is true for several cycles when you wanted one. A level such as btn will walk the machine through several states in a row. What you want is usually a one-cycle pulse, which is again an edge-detector job.

A machine that works in simulation and not on the board, because an output is a Mealy function of an input and glitches. Register it.

Exercise

Write a testbench for traffic_fsm in the style of lesson 06. Generate a tick pulse every four clocks, hold reset for two cycles, and print the four lamp outputs on every tick. Run through two full cycles of the lights with walk_req low, then raise it and confirm that the walk phase appears after the next red and lasts four ticks. Check that red and green are never high together, and make that check an automatic $display("FAIL") rather than something you read by eye.

Then convert the machine to one-hot by hand: four state bits, one per state. Note how much of the output logic disappears.

Summary

An FSM is a state register plus next-state and output logic. Draw the graph first, then write the code from it.
Moore outputs depend on state only and change on clock edges. Mealy outputs also depend on inputs, respond a cycle sooner, and can glitch.
The two-process style keeps the register and the logic separate. Give every signal a default at the top of the combinational process to avoid latches.
Synthesis tools extract FSMs and recode them, usually one-hot, unless the state is read as a number or has no constant reset.
The usual bugs are latches, missing resets, unsynchronised inputs, level-triggered transitions and glitching Mealy outputs.

Finite state machines

You will learn

What a state machine is

Moore or Mealy

The two-process style

The same machine in VHDL

One process or two

State encoding and what synthesis does

Common bugs

Exercise

Summary

Further reading