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

4.1 The two-block template

Every state machine in Verilog has the same shape: one clocked block for the state register, and one combinational block that works out the next state and the outputs.

In Volume 03 you did the hard work by hand: codes, excitation tables, K-maps. In real projects, nobody does that. You describe the machine in Verilog, and the synthesis tool finds the gates. Your job is to describe it clearly - and one template does that for every state machine.

Two blocks, two jobs

Remember the three blocks inside every clocked state machine, from Figure 1.3 in Volume 01: the state register, the next-state logic and the output logic. In Verilog, they become two always blocks:

• Block 1 - the state register. It runs at every rising clock edge, and it holds the state. This becomes flip-flops.
• Block 2 - the next-state and output logic. It runs whenever any of its inputs changes, and it decides where to go next and what the outputs are. This becomes gates.

When an always block runs is set by its sensitivity list, the part after the @. Here is block 1 on its own:

always @(posedge clk) begin        // run at every rising edge of clk
  if (rst) state <= C0;            // reset: go to the start state
  else     state <= next_state;    // otherwise: take the step block 2 chose
end

That is all block 1 ever does. It never changes from one machine to the next, apart from the name of the reset state.

Naming the states

Block 2 talks about states by name, so we first give each code a name with a localparam - a named constant:

localparam [1:0] C0   = 2'b00,     // [1:0] means "2 bits wide"
                 C1   = 2'b01,     // 2'b01 means "2 bits, binary 01"
                 C2   = 2'b11,
                 VEND = 2'b10;
reg [1:0] state, next_state;       // the current and the next state

These are the codes chosen in Volume 03. You could pick others, and the machine would still work.

The whole machine

Here is the drink machine from Volume 03, complete. Read the comments first, then the code.

module drink_fsm (
  input  wire clk,
  input  wire rst,          // reset, active high
  input  wire coin,         // 1 in the cycle a coin arrives
  output reg  vend          // 1 for one cycle to release a drink
);
  localparam [1:0] C0 = 2'b00, C1 = 2'b01, C2 = 2'b11, VEND = 2'b10;
  reg [1:0] state, next_state;

  // Block 1: the state register (flip-flops)
  always @(posedge clk) begin
    if (rst) state <= C0;
    else     state <= next_state;
  end

  // Block 2: next-state and output logic (gates)
  always @(*) begin
    next_state = state;     // default: stay where you are
    vend       = 1'b0;      // default: no drink
    case (state)
      C0:   if (coin) next_state = C1;
      C1:   if (coin) next_state = C2;
      C2:   if (coin) next_state = VEND;
      VEND: begin
              vend       = 1'b1;               // Moore output of VEND
              next_state = coin ? C1 : C0;     // a coin now counts as the first
            end
    endcase
  end
endmodule

Compare it with the state diagram in Figure 3.5 of Volume 03. Each line of the case statement is one state, and each if is one arrow. The two lines at the top of block 2 are the self-loops and the "vend is 0" rule, written once instead of four times.

Two kinds of assignment

Look closely, and you will see two different assignment signs:

• state <= next_state; uses <=, a non-blocking assignment. Every <= in a clocked block takes effect together, at the end of the moment. That is exactly how flip-flops behave: they all change at the same edge.
• next_state = C1; uses =, a blocking assignment. It takes effect at once, like a step in an ordinary program. That suits gates, which simply work out an answer.

The reason behind this rule is covered in depth in the Verilog course, sub-module 1.4. For state machines, following the rule is enough.

4.2 One-, two- and three-process styles

The same machine can be written with one, two or three always blocks. They differ in where the outputs come from - and so in their timing.

Engineers call each always block a "process", so the three styles are known as the one-, two- and three-process styles. You have just seen the two-process style. Here are the other two.

One process: everything in one clocked block

always @(posedge clk) begin
  if (rst) begin
    state <= C0;
    vend  <= 1'b0;
  end else begin
    case (state)
      C0:   if (coin) state <= C1;
      C1:   if (coin) state <= C2;
      C2:   if (coin) state <= VEND;
      VEND: state <= coin ? C1 : C0;
    endcase
    vend <= (state == VEND);      // looks right - but it is one cycle late
  end
end

It is short, and every output comes from a flip-flop. But the marked line has a trap. At the edge where the machine enters VEND, state == VEND is still false, because state still holds its old value, C2. So vend rises one edge later - in the cycle after VEND. To fix it, set the output on the arrow that enters the state:

end else begin
  vend <= 1'b0;                                           // default: off
  case (state)
    C0:   if (coin) state <= C1;
    C1:   if (coin) state <= C2;
    C2:   if (coin) begin state <= VEND; vend <= 1'b1; end  // set it on the way in
    VEND: state <= coin ? C1 : C0;
  endcase
end

This works, but with many outputs it becomes hard to read: each output must be set on every arrow into every state where it is 1.

Three processes: registered outputs, on time

The three-process style keeps the two-process template, and adds a third clocked block for the outputs. The trick is that it looks at next_state, not at state:

// 1. state register
always @(posedge clk)
  if (rst) state <= C0;
  else     state <= next_state;

// 2. next-state logic only
always @(*) begin
  next_state = state;
  case (state)
    C0:   if (coin) next_state = C1;
    C1:   if (coin) next_state = C2;
    C2:   if (coin) next_state = VEND;
    VEND: next_state = coin ? C1 : C0;
  endcase
end

// 3. registered output, decoded from next_state so it is not late
always @(posedge clk)
  if (rst) vend <= 1'b0;
  else     vend <= (next_state == VEND);

At the edge where the state register takes the value VEND, the output register takes next_state == VEND, which is true. Both change at the same edge. The output now comes straight from a flip-flop - a registered output - so it cannot glitch, and it is not late.

Figure 4.1 shows all three on the same coins.

Which style should you use?

This course uses the two-process style for teaching, and the three-process style where outputs must be clean. For a deeper comparison, including the synthesis results, see the three FSM coding styles in the Verilog course.

4.3 Default assignments and avoiding latches

In a combinational block, every output must get a value on every path through the block. A default assignment at the top makes sure it always does.

A drink machine that never stops giving

Here is block 2 of the drink machine, written slightly differently. Can you spot the problem?

always @(*) begin
  next_state = state;
  case (state)
    C0:   if (coin) next_state = C1;
    C1:   if (coin) next_state = C2;
    C2:   if (coin) next_state = VEND;
    VEND: begin vend = 1'b1; next_state = coin ? C1 : C0; end
  endcase
end

vend is given a value only in VEND. In C0, C1 and C2 the block says nothing about it. But Verilog has a firm rule: a variable that is not assigned keeps its old value. So after the first drink, vend becomes 1 - and stays 1 forever. The machine gives away every drink after the first.

What the hardware does

To "keep the old value" without a clock, the synthesis tool has to build a memory that is not a flip-flop. It builds a latch: a memory that copies its input while it is enabled, and holds it otherwise. A latch built by accident is almost always a bug:

• It remembers things you did not mean it to remember, as with vend.
• It has no clock, so the timing tools cannot check it properly.
• In some cases, the simulation and the real chip even behave differently.

Most synthesis tools print a warning that mentions a latch when this happens. Read your warnings.

The fix: defaults first

Give every output, and next_state, a value at the very top of the block. This is called a default assignment. Then each branch only has to say what is different:

always @(*) begin
  next_state = state;      // default: stay
  vend       = 1'b0;       // default: no drink
  case (state)
    C0:   if (coin) next_state = C1;
    C1:   if (coin) next_state = C2;
    C2:   if (coin) next_state = VEND;
    VEND: begin vend = 1'b1; next_state = coin ? C1 : C0; end
    default: next_state = C0;   // any other code: go back to the start
  endcase
end

Now every path assigns vend - even the paths that never mention it assign the default 0. There is no latch.

The default: branch catches any state value not listed above it. The drink machine uses all four codes, so it can never be reached - but in a machine with unused codes, it sends a lost machine home. Volume 11 builds on this idea.

4.4 Synchronous vs asynchronous reset

A synchronous reset acts only at a clock edge. An asynchronous reset acts at once, whatever the clock is doing.

Every state machine needs a reset, to start in a known state. There are two ways to connect it to the state register.

Synchronous reset

always @(posedge clk)              // only the clock is listed
  if (rst) state <= C0;            // reset is looked at only on a rising edge
  else     state <= next_state;

With a synchronous reset, rst is just another input that the flip-flops look at on each edge. Nothing happens until the next rising edge.

Asynchronous reset

always @(posedge clk or negedge rst_n)   // the reset is listed too
  if (!rst_n) state <= C0;               // acts at once when rst_n falls to 0
  else        state <= next_state;

With an asynchronous reset, the reset is in the sensitivity list, so the block runs the moment reset arrives - no clock edge needed. This version is also active low: it resets when rst_n is 0. The _n at the end of the name is a common way to say so. The ! means NOT.

Figure 4.2 shows both kinds meeting the same reset pulse, which arrives in the middle of a cycle.

Which one should you use?

Both are correct when used properly. Many FPGA design guides prefer synchronous resets. Many chip designs use asynchronous resets that are applied at once but released in step with the clock. Follow your project's rule, and use the same style everywhere in a design.

4.5 enum, unique case, always_ff and always_comb

SystemVerilog adds keywords that say what you mean - and the tools check that you meant it.

SystemVerilog is the newer, larger version of Verilog. Four of its features make state machines clearer and safer:

SystemVerilog also has the type logic, which you can use almost everywhere Verilog needs wire or reg.

The drink machine in SystemVerilog

module drink_fsm_sv (
  input  logic clk, rst, coin,
  output logic vend
);
  typedef enum logic [1:0] {C0 = 2'b00, C1 = 2'b01, C2 = 2'b11, VEND = 2'b10} state_t;
  state_t state, next_state;

  always_ff @(posedge clk) begin
    if (rst) state <= C0;
    else     state <= next_state;
  end

  always_comb begin
    next_state = state;
    vend       = 1'b0;
    unique case (state)
      C0:   if (coin) next_state = C1;
      C1:   if (coin) next_state = C2;
      C2:   if (coin) next_state = VEND;
      VEND: begin
              vend       = 1'b1;
              next_state = coin ? C1 : C0;
            end
    endcase
  end
endmodule

It has the same shape as the Verilog version. The differences are all about intent:

• The enum gives the state a type of its own, state_t. A waveform viewer now shows C2 instead of 11, and the tools stop you from putting a value that is not a state into state by mistake.
• always_ff says "this is flip-flops". If you accidentally write combinational logic inside it, the tool reports an error.
• always_comb says "this is gates". If a path leaves a variable unassigned, the tool warns you about the latch.
• unique case says "exactly one branch will match". If the state ever holds a value that matches no branch, the simulator warns you.

To run SystemVerilog, save the file as .sv. In EDA Playground, choose a simulator that supports SystemVerilog. With Icarus Verilog, add the flag -g2012.

4.6 Your first FSM testbench

A testbench drives the inputs cycle by cycle and checks the outputs by itself, so the computer - not your eyes - decides whether the machine works.

In Volume 00 you ran a testbench that printed values for you to read. That is fine for a flip-flop. For a state machine with many paths, reading printouts by eye is slow and easy to get wrong. A self-checking testbench knows the right answers, compares them with what the design does, and prints PASS or FAIL.

A testbench for the drink machine

`timescale 1ns/1ps
module drink_tb;
  reg  clk = 0, rst = 1, coin = 0;
  wire vend;
  integer errors = 0, drinks = 0;

  drink_fsm dut (.clk(clk), .rst(rst), .coin(coin), .vend(vend));

  always #5 clk = ~clk;                        // a 10 ns clock

  task insert_coin;                            // one coin, for one cycle
    begin
      @(negedge clk) coin = 1;
      @(negedge clk) coin = 0;
    end
  endtask

  always @(posedge clk) if (vend) drinks = drinks + 1;   // count drinks

  initial begin
    $dumpfile("dump.vcd"); $dumpvars(0, drink_tb);
    repeat (2) @(negedge clk); rst = 0;        // two cycles of reset
    insert_coin; insert_coin;                  // two coins: no drink yet
    repeat (3) @(negedge clk);
    if (drinks != 0) begin $display("ERROR: a drink after 2 coins"); errors = errors + 1; end
    insert_coin;                               // the third coin
    repeat (3) @(negedge clk);
    if (drinks != 1) begin $display("ERROR: expected 1 drink, saw %0d", drinks); errors = errors + 1; end
    if (errors == 0) $display("PASS"); else $display("FAIL: %0d error(s)", errors);
    $finish;
  end
endmodule

Here is what each part does:

1. The clock. always #5 clk = ~clk; flips the clock every 5 ns, so one cycle takes 10 ns. The first line, starting with a backtick and the word timescale, says that the numbers are nanoseconds.
2. The design under test. drink_fsm dut (...) places one copy of the machine, and connects its ports to the testbench's signals.
3. A task. A task is a named group of steps that you can call many times. insert_coin makes coin 1 for exactly one clock cycle.
4. A checker. The always @(posedge clk) line counts every cycle in which vend is 1.
5. The script. The initial block runs once, from top to bottom: reset, two coins, a check, a third coin, another check, and a final PASS or FAIL.

When the machine is correct, the simulator prints PASS. Try breaking the design on purpose - remove the vend = 1'b0; default, for instance - and watch the testbench catch it.

Why the inputs change on the falling edge

The task changes coin at @(negedge clk) - the falling edge, halfway between two rising edges. If the testbench changed coin at the very same instant as a rising edge, the simulator would be free to update the flip-flops before or after the change. The result could differ from one simulator to another. This is called a race. Changing inputs half a cycle away from the rising edge removes it, just as real signals settle well before the edge.

What you learned

• Every state machine fits one template: a clocked block for the state register, and an always @(*) block for next state and outputs.
• Use <= in clocked blocks and = in combinational blocks.
• The one-process style can make outputs a cycle late; the three-process style registers outputs from next_state, so they are clean and on time.
• A variable left unassigned on any path keeps its old value, which builds a latch. Defaults at the top of the block prevent it.
• A synchronous reset waits for a clock edge; an asynchronous reset acts at once but must be released in step with the clock.
• SystemVerilog's enum, always_ff, always_comb and unique case state your intent, so the tools can check it.
• A self-checking testbench drives inputs away from the clock edge and decides PASS or FAIL by itself.

Key words from this volume

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

• always block
• Sensitivity list
• localparam
• Non-blocking assignment (<=)
• Blocking assignment (=)
• Registered output
• Latch
• Default assignment
• Synchronous reset
• Asynchronous reset
• Active low
• SystemVerilog
• enum
• always_ff
• always_comb
• unique case
• Self-checking testbench
• Task
• Race (in simulation)

Practice

module turnstile_fsm (
  input  wire clk, rst, coin, push,
  output reg  locked
);
  localparam LOCKED = 1'b0, UNLOCKED = 1'b1;
  reg state, next_state;

  always @(posedge clk)
    if (rst) state <= LOCKED;
    else     state <= next_state;

  always @(*) begin
    next_state = state;
    locked     = 1'b0;
    case (state)
      LOCKED:   begin locked = 1'b1; if (coin) next_state = UNLOCKED; end
      UNLOCKED: if (push) next_state = LOCKED;
    endcase
  end
endmodule

always @(*) begin
  next_state = state;
  green = 1'b0;
  case (state)
    GO:   begin green = 1'b1; if (stop) next_state = HALT; end
    HALT: begin red   = 1'b1; if (go)   next_state = GO;   end
  endcase
end

module edge_tb;
  reg clk = 0, rst = 1, btn = 0;
  wire pulse;
  integer pulses = 0;

  edge_detector dut (.clk(clk), .rst(rst), .btn(btn), .pulse(pulse));

  always #5 clk = ~clk;
  always @(posedge clk) if (pulse) pulses = pulses + 1;

  initial begin
    repeat (2) @(negedge clk); rst = 0;
    @(negedge clk) btn = 1;                  // press ...
    repeat (3) @(negedge clk); btn = 0;      // ... hold for three cycles, release
    repeat (3) @(negedge clk);
    if (pulses == 1) $display("PASS"); else $display("FAIL: %0d pulses", pulses);
    $finish;
  end
endmodule

Interview corner

Next, Volume 05 looks at a choice you have been making quietly all along: the bit patterns of the states. It also shows why the tools may change them behind your back.