5.6 Testing FSMs

Why this matters

A state machine that works for the inputs you tried can still be wrong on the ones you did not. Because the behavior of a machine is its arrows, a practical baseline for testing it is to make sure that every arrow gets taken, with both its destination and its output checked. That is transition coverage, and it is a minimum, not a proof: the end of the section says what it leaves out. This section turns the idea into a plan you can carry out: a short list of inputs, one testbench line for each, and a waveform you know how to read.

Learning goals

Plan a test that takes every arrow of a state diagram from reset, and write it as a table of cycles.
Turn a plan into a testbench with one line per clock cycle and a comment that names the state.
Count the clock cycles of a test, saying which cycles are included.
Read a simulation for the three things a test must show: reset works, every arrow is taken, every output is right.
Find the arrow that fails in a waveform from a machine with a bug.

Intuition first

Think of checking a new road map by driving it. You do not need to drive every possible route, because there are far too many, but you do need to drive every road at least once, or a missing bridge on a road you skipped will stay hidden until a customer finds it. The state diagram is the road map, the arrows are the roads, and a test is a route that starts at the depot, the reset state. A good route drives every road, and it re-drives some of them only when that is the only way to get back to a junction you still need.

Two things come with driving a road. You check that you ended up where the map says (the state), and you check what the map says happens along the way (the output). A drive that does not look at either has tested nothing.

Taking every arrow

Definition 5.6.1(transition tour).

A transition tour is a sequence of inputs, applied one per clock cycle starting from the reset state, whose walk through the state diagram takes every arrow at least once. Arrows for input combinations that can never occur are not part of the tour.

An arrow that is not taken is an arrow that is not tested. The self-loops and the "no coin" arrows are easy to skip because they look boring, but they are arrows like any other, and a bug can sit in them. The tour has to take them all.

The arrows counted in this section are the arrows of the machine's specification, which lists each one separately even when the diagram draws two of them as a single arrow with a plus sign in its label. The arrows for combinations marked as don't cares are left out, because the machine is never asked to handle them.

How cycles are counted

The book counts the cycles of a test the way the tour table of Section 5.2 did, and tour numbers are what every "cycle" of this section means. The first cycle is the one in which reset is asserted, which the tour table calls cycle 0, and the machine is in its initial state after the edge that ends it. (The scenario tables of Sections 5.4 and 5.5 call the first cycle after reset cycle 0, so cycle $k$ of a scenario is cycle $k+1$ of a tour table.) After that, every arrow taken is one cycle. The testbench then adds one more cycle at the end, so that the effect of the last input can be seen, and that extra cycle is not counted. So a test that takes $k$ arrows takes $k + 1$ cycles with the reset cycle, and $k+2$ lines of testbench if the extra cycle is written out.

Example: the vending machine

Example 5.6.1(a tour of the gumball machine).

The gumball machine of Section 5.4 has six arrows to take. We start at reset, in 0¢, and plan a walk. A program searched every possible walk, and the table below is a shortest one: no shorter walk takes every arrow. The input columns follow the order N, D.

Exact. No walk from the start state that takes every arrow without a reset is shorter than this one.

8 cycles: 1 reset cycle, then 7 arrows taken. The machine has 6 arrows.

Test plan for ch05/vending: one row per clock cycle after the first reset cycle; 8 cycles: 1 reset cycle, then 7 arrows taken. The machine has 6 arrows.
Cycle	State	Inputs N D	Next state	Output Open	Arrow
0	reset asserted: the machine starts in 0¢
1	0¢	00	0¢	0	1
2	0¢	10	5¢	0	2
3	5¢	00	5¢	0	4
4	5¢	10	0¢	1	5
5	0¢	10	5¢	0	2
6	5¢	01	0¢	1	6
7	0¢	01	0¢	1	3

The numbers in the last column are the arrows of the diagram, numbered as in Figure 5.4.3 of Section 5.4, which is repeated here.

Figure 5.6.1. The gumball machine with its arrows numbered, as the tour table uses them.

Six arrows take seven cycles after the reset cycle, because one arrow is taken twice. The reason is that 5¢ has two arrows that lead out of it, arrow 5 (5¢ to 0¢ when N=1, D=0, output 1) and arrow 6 (5¢ to 0¢ when N=0, D=1, output 1), and the only way into 5¢ is arrow 2 (0¢ to 5¢ when N=1, D=0, output 0). To take both of the two leaving arrows, the walk has to be in 5¢ twice, and so it enters through arrow 2 twice, once at cycle 2 (in 0¢ with N=1, D=0, arrow 2 to 5¢, output 0) and again at cycle 5 (in 0¢ with N=1, D=0, arrow 2 to 5¢, output 0). With the reset cycle that makes 8 cycles.

In SystemVerilog: from the table to a testbench

Each row of the table becomes one line of the testbench, in the shape that Section 5.2 introduced. The line sets the inputs of the cycle and waits for the clock edge that ends it, and its // expect: comment names the state the machine is in during that cycle, which is the table's State column, and the output of the arrow. The comment reports the state that the previous edge produced, as always. The first line of the testbench holds reset, and the line after the last row is the extra cycle.

// A second testbench for vending_machine: reset, then one walk that takes every arrow of the diagram, then one extra cycle.
module vending_tour_tb();
  logic clk, reset, N, D, Open;

  vending_machine dut(.*);

  parameter CLOCK_PERIOD = 100;

  initial begin
    clk <= 0;
    forever #(CLOCK_PERIOD / 2) clk <= ~clk;
  end

  initial begin
    reset <= 1; N <= 0; D <= 0; @(posedge clk);
    reset <= 0;                 @(posedge clk);   // expect: ps=C0, Open=0
                N <= 1;         @(posedge clk);   // expect: ps=C0, Open=0
                N <= 0;         @(posedge clk);   // expect: ps=C5, Open=0
                N <= 1;         @(posedge clk);   // expect: ps=C5, Open=1
                                @(posedge clk);   // expect: ps=C0, Open=0
                N <= 0; D <= 1; @(posedge clk);   // expect: ps=C5, Open=1
                                @(posedge clk);   // expect: ps=C0, Open=1
                D <= 0;         @(posedge clk);   // expect: ps=C0, Open=0
    $stop;
  end
endmodule

The book's tools run this testbench and check every comment against the simulation of the module and against the machine of Section 5.4, so a comment that disagrees with either fails the check.

Run it, and the waveforms are the evidence. Two figures cover the nine cycles.

Time in ps; one column is 50 ps.

Figure 5.6.2. The first seven cycles of the tour. Reset is high only in the first cycle.

Time in ps; one column is 50 ps.

Figure 5.6.3. The later part of the tour, from cycle 3 of the tour table to the extra cycle at the end.

What the waveform has to show

A waveform of a tour is read for three things, in this order.

Reset works. The state is unknown until the first clock edge with reset high, and the state after it is the initial state. In the first figure the state is drawn hatched before the first edge, and it is C0 after it. (The waveform writes the states by their names in the code, C0 and C5; the diagram and the table write them as 0¢ and 5¢.)
Every arrow is taken. The sequence of states follows the table: compare each cycle's state and input with its row. The State column of the table is the state during the cycle, so the Next state of a row shows up on the waveform at the edge that ends that row's cycle.
The outputs match. In every cycle, the output is the one on the arrow taken. The output of a Mealy machine depends on the input, so the question is what it is while that cycle's input is applied, which is just before the edge that ends the cycle.

Where the table says an arrow has output 1, look for Open high in that cycle: here, the cycles of cycle 4 (in 5¢ with N=1, D=0, arrow 5 to 0¢, output 1), cycle 6 (in 5¢ with N=0, D=1, arrow 6 to 0¢, output 1) and cycle 7 (in 0¢ with N=0, D=1, arrow 3 to 0¢, output 1).

Another machine: the long-press detector

The long-press detector of Section 5.2 has six arrows and needs a tour of 10 cycles, as Exercise 5.2.2 works out. That is more cycles than arrows for a similar reason: the last state has two arrows out, so the walk has to be there twice. The plan, the table and the testbench lines have the same shape for every machine, and only the table changes.

An aside: what a tour does not check

A tour is the minimum for a test, not everything a test could check, and passing it does not show that a machine is correct: a machine with extra hidden state can behave on the first visit to an arrow and differently on a later one. The checks that this book runs on its own modules go further than one walk. They also run each scenario of the machine's specification, they assert reset from every state that can be reached, and they sample every Mealy output at several points in each cycle, with the inputs changing a quarter of the way into the cycle, to see that the output follows the input and is stable until the next change. A reset that fails when the machine is in one particular state would pass a tour that resets only at the start, and an output that is wrong for part of a cycle and right again by the end would pass a test that looks at it only just before the edge. Those are the reasons for the extra checks, and they are what to add when a design matters.

Course conventions

How CSE 369 writes this

In CSE 369 we test by taking every arrow that can occur; arrows for input combinations marked as don't cares are left out. The testbench starts with a reset, defines every input at time zero, adds an extra cycle at the end to see the effect of the last input, and ends each line with a comment naming the current state. The count of cycles above follows the same pieces: the reset cycle is counted and the extra cycle is not.

Pitfalls

Common pitfall

Skipping the arrows that look boring. Self-loops and "nothing happened" arrows are arrows too, and a bug in one of them is found only by taking it.
Checking the states and forgetting the outputs, or the other way round. An arrow is tested only when both its destination and its output are checked.
Counting cycles in different ways. State whether the reset cycle and the extra cycle at the end are included; the book counts the first and not the second.
Reading a line's comment as the state after its edge. The comment names the state during the cycle, which the previous edge produced.
Trusting a test written from the same table as the design. If the table is wrong, the design and the test are wrong in the same way; write the expected behavior from the description first.

Check your understanding

Take the quiz (4 questions)

Exercises

Exercise 5.6.1

Plan a test for the 15-cent machine of Section 5.4 that takes every arrow from reset in as few clock cycles as you can, and then write its testbench. How many cycles does it take, counting the reset cycle and not the extra cycle?

Hint

List the ways out of each state. How many times must you be in the 10-cent state to take each of the arrows that leave it? The same question for the 5-cent state tells you which arrows have to be taken more than once.

Solution

The 15-cent machine has twelve arrows, but a tour of twelve cycles after the reset cycle is impossible, because some states have to be entered more than once. A program searched every possible walk and found a shortest one, shown below.

Exact. No walk from the start state that takes every arrow without a reset is shorter than this one.

16 cycles: 1 reset cycle, then 15 arrows taken. The machine has 12 arrows.

Test plan for ch05/vend15: one row per clock cycle after the first reset cycle; 16 cycles: 1 reset cycle, then 15 arrows taken. The machine has 12 arrows.
Cycle	State	Inputs N D Q	Next state	Output Open	Arrow
0	reset asserted: the machine starts in 0¢
1	0¢	000	0¢	0	1
2	0¢	001	0¢	1	2
3	0¢	100	5¢	0	3
4	5¢	000	5¢	0	5
5	5¢	100	10¢	0	6
6	10¢	000	10¢	0	9
7	10¢	100	0¢	1	10
8	0¢	100	5¢	0	3
9	5¢	010	0¢	1	7
10	0¢	100	5¢	0	3
11	5¢	001	0¢	1	8
12	0¢	010	10¢	0	4
13	10¢	010	0¢	1	11
14	0¢	010	10¢	0	4
15	10¢	001	0¢	1	12

The reason for the repeats is in the arrows that leave the 10-cent state: three of them, one for each coin, each going back to 0¢, so the walk has to be in 10¢ three times and must enter it three times. In the table above it enters once from 5¢ and twice directly from 0¢, which is why the arrow from 0¢ to 10¢ appears twice. The same argument for 5¢, which has three ways out (a nickel to 10¢, and a dime or a quarter back to 0¢), makes the walk visit it three times, each time through the nickel arrow from 0¢. That is how twelve arrows become fifteen cycles after the reset cycle, and sixteen with it.

Turning each row into a testbench line, with the state before the edge in the comment:

// Testbench for vend15: reset, one walk that takes every arrow, and an extra cycle. Each line is one clock cycle.
module vend15_tb();
  logic clk, reset, N, D, Q, Open;

  vend15 dut(.*);

  parameter CLOCK_PERIOD = 100;

  initial begin
    clk <= 0;
    forever #(CLOCK_PERIOD / 2) clk <= ~clk;
  end

  initial begin
    {reset, N, D, Q} <= 4'b1000; @(posedge clk);
    reset <= 0; {N, D, Q} <= 3'b000; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b001; @(posedge clk);   // expect: ps=C0, Open=1
                {N, D, Q} <= 3'b100; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b000; @(posedge clk);   // expect: ps=C5, Open=0
                {N, D, Q} <= 3'b100; @(posedge clk);   // expect: ps=C5, Open=0
                {N, D, Q} <= 3'b000; @(posedge clk);   // expect: ps=C10, Open=0
                {N, D, Q} <= 3'b100; @(posedge clk);   // expect: ps=C10, Open=1
                {N, D, Q} <= 3'b100; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b010; @(posedge clk);   // expect: ps=C5, Open=1
                {N, D, Q} <= 3'b100; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b001; @(posedge clk);   // expect: ps=C5, Open=1
                {N, D, Q} <= 3'b010; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b010; @(posedge clk);   // expect: ps=C10, Open=1
                {N, D, Q} <= 3'b010; @(posedge clk);   // expect: ps=C0, Open=0
                {N, D, Q} <= 3'b001; @(posedge clk);   // expect: ps=C10, Open=1
                {N, D, Q} <= 3'b000; @(posedge clk);   // expect: ps=C0, Open=0
    $stop;
  end
endmodule

Tags: StandardFinite state machinesTest benches and simulation

Exercise 5.6.2

The equal-inputs counter of Section 5.4 has two inputs, A and B, and pulses its output on the third cycle in a row in which they are equal. How many cycles does the shortest test from reset take, counting the reset cycle but not the extra cycle?

Hint

The diagram draws each arrow once, but each such arrow stands for two input combinations. The table lists twelve arrows, one for every state and every input combination.

Solution

The machine has twelve arrows in its table, three states with four input combinations each, and the tour takes each one. The search below reports the minimum.

Exact. No walk from the start state that takes every arrow without a reset is shorter than this one.

19 cycles: 1 reset cycle, then 18 arrows taken. The machine has 12 arrows.

Test plan for ch05/s04-agree-run: one row per clock cycle after the first reset cycle; 19 cycles: 1 reset cycle, then 18 arrows taken. The machine has 12 arrows.
Cycle	State	Inputs A B	Next state	Output Out	Arrow
0	reset asserted: the machine starts in R0
1	R0	00	R1	0	1
2	R1	00	R2	0	5
3	R2	00	R0	1	9
4	R0	00	R1	0	1
5	R1	00	R2	0	5
6	R2	11	R0	1	10
7	R0	00	R1	0	1
8	R1	00	R2	0	5
9	R2	01	R0	0	11
10	R0	00	R1	0	1
11	R1	11	R2	0	6
12	R2	10	R0	0	12
13	R0	00	R1	0	1
14	R1	01	R0	0	7
15	R0	11	R1	0	2
16	R1	10	R0	0	8
17	R0	01	R0	0	3
18	R0	10	R0	0	4

It takes 18 cycles after the reset cycle, and 19 with it. Here is why it is more than twelve. R2 has four arrows out, so the walk has to be in R2 four times, and R2 can only be entered from R1, so the two arrows from R1 to R2 are taken four times between them. R1 also has two arrows back to R0, which need two more visits, so R1 is visited six times, and it can only be entered from R0, so the two arrows from R0 to R1 are taken six times between them. Add the four arrows out of R2, the two arrows from R1 to R0 and the two loops at R0, and the total is $6 + 4 + 4 + 2 + 2 = 18$ .

Tags: StandardFinite state machinesTest benches and simulation

Exercise 5.6.3

The sequence generator of Section 5.4 has no inputs and outputs 1, 1, 0, 1, 0 repeatedly after reset. How many cycles does a test that takes every arrow take, counting the reset cycle but not the extra cycle? What does each line of its testbench contain?

Hint

With no inputs there is nothing to choose: the machine takes one arrow per cycle. How many arrows does it have?

Solution

There are five arrows, one leaving each state, and they form a ring. One walk takes all five, so the test is the reset cycle and five more: 6 cycles.

Exact. No walk from the start state that takes every arrow without a reset is shorter than this one.

6 cycles: 1 reset cycle, then 5 arrows taken. The machine has 5 arrows.

Test plan for ch05/s04-sequence: one row per clock cycle after the first reset cycle; 6 cycles: 1 reset cycle, then 5 arrows taken. The machine has 5 arrows.
Cycle	State	Input	Next state	Output Out	Arrow
0	reset asserted: the machine starts in B0
1	B0	(none)	B1	1	1
2	B1	(none)	B2	1	2
3	B2	(none)	B3	0	3
4	B3	(none)	B4	1	4
5	B4	(none)	B0	0	5

Each line of the testbench has no inputs to set; it waits for a clock edge and checks the output of the state the machine is in. Since the output is inside the state, the five lines check 1, 1, 0, 1 and 0 in turn.

Tags: Warm-upFinite state machinesTest benches and simulation

Exercise 5.6.4

A different gumball machine has a bug, and the tour of the previous example was run on it. The waveform shows its inputs, its state and its output. Using the tour table above, find the first cycle at which it goes wrong, and say which arrow is at fault.

Time in ps; one column is 50 ps.

Figure 5.6.4. The tour run on a machine with a bug. The window starts a few cycles into the run.

Hint

Compare the state in each cycle with the State column of the table, starting from the first cycle in the window. The input changes at an edge, so the state that results shows one edge later.

Solution

Go through the window with the tour table beside it. At the left edge the machine is in 5¢, and a nickel arrives in cycle 4 (in 5¢ with N=1, D=0, arrow 5 to 0¢, output 1): Open rises, and after the edge the state is 0¢, as the table says. In cycle 5 (in 0¢ with N=1, D=0, arrow 2 to 5¢, output 0) the nickel is still there, now in 0¢, and the state is 5¢ after the edge that ends it. Then comes cycle 6 (in 5¢ with N=0, D=1, arrow 6 to 0¢, output 1): the machine is in 5¢ and a dime arrives. Open is high, as it should be, and the table says the next state is 0¢.

The waveform does not do that. The state stays at C5 through the whole cycle after the dime was taken, and the table row for cycle 7 (in 0¢ with N=0, D=1, arrow 3 to 0¢, output 1) expects the machine to be in 0¢ there. So the first cycle that goes wrong is cycle 7 of the tour table, the one that starts at the edge on which the dime was taken, and the fault is in arrow 6 (5¢ to 0¢ when N=0, D=1, output 1), the arrow that the machine is taking in cycle 6: it leaves the machine in 5¢ instead of sending it back to 0¢.

Notice that Open matches the table in every cycle of the window, even in the wrong cycle, because a dime opens the machine from either state. A test that checked only the outputs would have passed this machine, and only the state comparison finds the fault. That is why every arrow has to be checked for its destination as well as its output.

Here is the same stretch of the tour on the correct machine:

Time in ps; one column is 50 ps.

Tags: ChallengeFinite state machinesWaveforms