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

12.1 Tests that hit every transition

A thorough test drives the machine along every arrow of its state diagram at least once, and checks the outputs and the next state at every step.

Visiting every state is not enough

Suppose a test for the turnstile puts in a coin, then pushes the arm. It visits both states, LOCKED and UNLOCKED. But it never pushes while locked, and never puts a coin in while unlocked - the two self-loops. If one of those arrows were wrong, this test would pass anyway.

So the goal is to take every arrow at least once. A test that does this is a transition tour.

Planning a tour for the drink machine

The drink machine from Volume 03 has four states and one input, so its state table has 4 × 2 = 8 rows - 8 arrows. Starting from reset, in C0, the shortest input sequence that takes all 8 arrows is ten coins long: 0, 1, 0, 1, 0, 1, 1, 1, 1, 0. It cannot be done in 8 - some arrows can only be reached by passing along others again.

Checking every step

A tour is only useful if every step is checked. The testbench below holds the state table as data, in a function, and runs its own copy of the machine beside the design. After every clock edge it compares the two. This is the reference model idea from Volume 06, written as a table.

module drink_tour_tb;
  reg  clk = 0, rst = 1, coin = 0;
  wire vend;
  reg  [1:0] model;                          // the reference model's state
  reg  [0:9] tour = 10'b0101011110;          // the ten-step tour, step 1 first
  integer i, errors = 0;

  drink_fsm dut (.clk(clk), .rst(rst), .coin(coin), .vend(vend));
  always #5 clk = ~clk;

  function [1:0] model_next(input [1:0] s, input c);   // the state table, as data
    case ({s, c})
      3'b00_0: model_next = 2'b00;  3'b00_1: model_next = 2'b01;   // C0
      3'b01_0: model_next = 2'b01;  3'b01_1: model_next = 2'b11;   // C1
      3'b11_0: model_next = 2'b11;  3'b11_1: model_next = 2'b10;   // C2
      default: model_next = c ? 2'b01 : 2'b00;                     // VEND
    endcase
  endfunction

  initial begin
    model = 2'b00;
    repeat (2) @(negedge clk); rst = 0;
    for (i = 0; i < 10; i = i + 1) begin
      coin = tour[i];                        // this step's input, away from the rising edge
      @(negedge clk);                        // one rising edge later...
      model = model_next(model, tour[i]);    // ...the model takes the same step
      if (dut.state !== model || vend !== (model == 2'b10)) begin
        errors = errors + 1;
        $display("step %0d: state %b, expected %b", i + 1, dut.state, model);
      end
    end
    if (errors == 0) $display("PASS: all 8 transitions taken and checked");
    else             $display("FAIL: %0d error(s)", errors);
    $finish;
  end
endmodule

dut.state looks inside the design by name, so the test checks the state itself, not only the output. Checking the internal state makes a failure much easier to understand: the message says exactly which step went wrong, and where the machine went instead.

12.2 State and transition coverage

Coverage measures what your tests actually did: which states they visited, and which arrows they took. It turns "I think we tested everything" into a number.

Two measures

Coverage records, during a simulation, which situations the design actually met. For a state machine, two measures matter most:

• State coverage: the share of states visited.
• Transition coverage: the share of arrows taken.

The turnstile test from sub-module 12.1 had 100% state coverage, but only 50% transition coverage - two of its four arrows were never taken. Transition coverage is the one to trust.

Counting arrows in plain Verilog

Add one counter per row of the state table. On every clock edge, the current state and the current input together name the row about to be taken:

integer hits [0:7];                              // one counter per (state, coin) row
integer k, taken;
initial for (k = 0; k < 8; k = k + 1) hits[k] = 0;

always @(posedge clk)
  if (!rst) hits[{dut.state, coin}] = hits[{dut.state, coin}] + 1;

// at the end of the test:
//   taken = 0;
//   for (k = 0; k < 8; k = k + 1) if (hits[k] > 0) taken = taken + 1;
//   $display("transition coverage: %0d of 8 arrows", taken);

{dut.state, coin} joins the 2-bit state and the 1-bit input into a 3-bit number from 0 to 7 - the row of the state table. Any counter still at 0 at the end is an arrow the test never took.

Covergroups in SystemVerilog

SystemVerilog has this built in. A covergroup samples signals on a clock and counts the values it sees:

covergroup drink_cov @(posedge clk);
  st:     coverpoint dut.state { bins state[] = {2'b00, 2'b01, 2'b11, 2'b10}; }  // C0 C1 C2 VEND
  cn:     coverpoint coin;
  arrows: cross st, cn;             // every (state, input) pair = every row of the table
endgroup

drink_cov cov = new();              // create it once, in the testbench

The cross counts every combination of state and input, which for a single-input machine is exactly transition coverage. Coverpoints can also count sequences directly: bins steps[] = (2'b00 => 2'b01) counts the step from C0 to C1. Covergroups need a simulator that supports SystemVerilog coverage; most commercial simulators do, but the free Icarus Verilog does not - the plain counters above work everywhere.

12.3 Assertions for FSMs

An assertion is a rule about the design, written as code and checked on every clock cycle. A broken rule is reported the moment it breaks - not later, when its effects finally reach an output.

Rules that watch all the time

A testbench checks what it looks at, when it looks. An assertion checks a rule on every clock cycle of every test, including the random ones, forever. When the rule breaks, the simulator reports the time and the rule, right at the source of the bug.

State machines have natural rules:

• The state is always a legal code.
• A given state and input always lead to the right next state.
• An output is 1 exactly in the right states.
• Something that must happen, happens within a time limit.

Writing them in SystemVerilog

SystemVerilog Assertions (SVA) express rules that span clock cycles. A few symbols carry most of the meaning:

Here are rules for safe_ctrl from Volume 11, written inside the module:

// 1. the state is always legal
assert property (@(posedge clk) disable iff (rst)
                 state inside {IDLE, RUN, DONE})
  else $error("illegal state %b", state);

// 2. from IDLE, go leads to RUN at the next edge
assert property (@(posedge clk) disable iff (rst)
                 (state == IDLE && go) |=> (state == RUN));

// 3. busy is 1 exactly in RUN
assert property (@(posedge clk) busy == (state == RUN));

And two from earlier volumes. For the GCD calculator of Volume 09, "every start is answered within 300 cycles" - for 8-bit inputs the slowest case needs 254 subtractions, so 300 is a safe limit:

// GCD: done must follow start within 300 cycles (it catches the gcd(0, x) hang)
assert property (@(posedge clk) disable iff (rst) start |-> ##[1:300] done);

// four-phase handshake: a request is never taken back, and its data never changes, until ack
assert property (@(posedge clk) disable iff (rst) (req && !ack) |=> req);
assert property (@(posedge clk) disable iff (rst) (req && !ack) |=> $stable(data));

$stable(data) means "data has the same value as in the previous cycle".

Without SystemVerilog

If your simulator does not support SVA - Icarus Verilog does not - a plain check in an always block does the simplest job:

always @(posedge clk)
  if (!rst && state == 2'b11)
    $display("ERROR at time %0t: illegal state", $time);

12.4 Formal reachability in plain words

A formal tool does not run tests. It works out every state the design can reach from reset, and then either proves that a rule always holds, or hands you the input sequence that breaks it.

Reachability, by hand

In Volume 10 you removed unreachable states by starting at reset and following every arrow. Do it carefully, one step at a time, on this machine:

The set of reachable states stops growing after step 3. TEST is not in it, so no test can ever reach TEST. If it was put there for factory testing, the designer must provide another way in; if not, it is dead logic.

What a formal tool does

Formal verification does exactly this, but for the whole design at once - every register, every input combination, every cycle - using mathematics rather than simulation. You give it the design and your assertions. It answers in one of two ways:

• Proven: the rule holds for every possible input sequence. No test could ever break it.
• Failed: here is a counterexample - an input sequence, often very short, that breaks the rule. You can replay it in simulation and watch the bug happen.

Formal tools also make excellent test generators. Give one the deliberately false rule "vend is never 1", and it will reply with the shortest way to get a drink: reset, then coin, coin, coin.

What formal tools find in state machines

• Unreachable states, such as TEST above.
• Illegal transitions: an arrow your assertions forbid.
• Deadlocks: a deadlock is a reachable situation in which the machine waits for something that can never happen, and so stops for ever.
• Missed deadlines: "done within 300 cycles", proven for every input, not just the ones you tried.

A related failure is livelock: the machines keep changing state, but never make progress. Think of two people in a corridor who keep stepping the same way to let each other pass.

12.5 Debugging a stuck FSM

When a machine seems stuck, find the state it is stuck in, read which input would move it on - and then find out why that input never comes.

A method, not a guess

"The machine is stuck" is the most common state machine bug report. Work through it in order:

1. Is it alive? Is the clock running? Is reset released - with the right polarity? A reset held active looks exactly like a stuck machine.
2. Where is it? Read the state - in the waveform, or on hardware with a logic analyser probe. Remember that synthesis may have re-encoded it (Volume 05): use the synthesis report to translate the codes.
3. Is that a legal state? If not, the problem is a fault, a timing violation or a reset issue - Volume 11.
4. What is it waiting for? Read the arrows out of that state. Which input would move it on?
5. Why does that input never come? This is where the real bug is.

Why the input never comes

The missed pulse

The first row is the most common of all. A parent machine starts a child, does one more cycle of setup work, then waits for the child's one-cycle done pulse. But this child is fast: its pulse comes during the setup cycle, when the parent is not looking.

The fix is a sticky flag: a register that is set by the pulse, whenever it comes, and stays set until the machine has used it.

always @(posedge clk)
  if (rst)                            got_done <= 1'b0;
  else if (done)                      got_done <= 1'b1;   // catch the pulse, whenever it comes
  else if (state == WAIT && got_done) got_done <= 1'b0;   // clear it once it has been used

// in the next-state logic:  WAIT: if (got_done) next_state = NEXT;

What you learned

• Test every arrow, not only every state: a transition tour takes each transition at least once.
• Check every step against a reference model built from the specification.
• Transition coverage measures which arrows were taken; coverage says where you looked, checks say what you found.
• Assertions check rules on every cycle; SVA writes rules across cycles with symbols such as |->, |=> and ##[1:n].
• Formal tools prove rules for every input sequence, or return a counterexample; they find unreachable states and deadlocks.
• To debug a stuck machine: is it alive, where is it, is that state legal, what is it waiting for - and why does that never come?

Key words from this volume

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

• Transition tour
• Reference model
• Coverage
• State coverage
• Transition coverage
• covergroup
• Assertion
• SystemVerilog Assertions (SVA)
• Reachable state
• Formal verification
• Counterexample
• Deadlock
• Livelock
• Sticky flag

Practice

assert property (@(posedge clk) disable iff (rst) pulse |=> !pulse);

Interview corner

Next, Volume 13 turns to speed: why some state machines can run faster than others, and how to make the outputs clean and the critical path short.