5.2 State diagrams

Why this matters

Chapter 4 introduced registers, which let a circuit hold on to a value. A button debouncer, a vending machine, a traffic light and a CPU controller all need to remember what happened earlier, and a state diagram is a systematic way to say what must be remembered and how that memory changes. It is the drawing you make before you build such a circuit: it fixes what must be remembered and what happens on each clock tick, so the SystemVerilog and the test come straight from the picture.

Learning goals

Read a state diagram: its states, its arrows, the input and output on each arrow, and the initial state.
Trace a sequence of inputs through a diagram, one clock cycle at a time, and give the output of each cycle.
Draw a state diagram for a circuit described in words.
Match each part of a state-machine module to the picture it implements.
Plan a test that takes every arrow of a diagram.

Intuition first

Imagine checking a button once every second and counting on your fingers how many checks in a row have found it held down. You never need the whole history, only that one number. At each check you look at the button: if it is down you raise one more finger, and if it is up you put all your fingers down. When you reach three, you say so and start counting again. That number is the machine's state: the smallest summary of the past that still lets you answer the question.

A state diagram draws this memory as circles, one per thing worth remembering, and moves between them as time passes. Time advances in jumps, one per tick of the clock, so at each tick you stand in one circle, look at the input, say something aloud (the output) and step along one arrow to the next circle.

For a programmer, this is a loop that runs once per clock tick, around a switch on an enum. The state is a variable that survives from one iteration to the next. The analogy breaks in one way: a circuit has no "iteration order". All the logic is always running, and the only thing that decides when the state changes is the clock edge.

The pieces of a diagram

Definition 5.2.1(state diagram).

A state diagram shows a machine in three parts. The states are circles, one for each situation worth remembering. The transition function is the set of arrows between circles: for every state and every input value it says which output the machine produces and which state comes next (an arrow may start and end at the same circle). The initial state is where the machine starts, marked by an arrow that comes from no state at all.

Definition 5.2.2(arrow label).

Each arrow is labeled with an input and an output written as input/output, in that order. The label means: when the machine is in the state the arrow leaves and sees this input, it produces this output and moves to the state the arrow points to. Every input value that can occur must be accounted for in every state: exactly one arrow leaving the state carries it. One arrow may carry several input values, and an input combination that can never occur may be left out and declared a don't care (Section 5.4 has an example). With one input, as here, every arrow carries a single value.

Two facts about timing complete the picture. First, the machine takes exactly one step per clock cycle, so an arrow is the same as "one tick of the clock". Second, the machine starts in its initial state because a reset puts it there. Until reset has happened, the circuit's state is unknown. One consequence for counting: later tables in this chapter list the machine's clock cycles with numbers. A tour table, which the exercises of this section introduce, numbers the reset cycle itself as cycle 0. A scenario table, which Section 5.4 introduces, numbers the first cycle after reset as cycle 0.

A machine whose output is written on its arrows, so that the output depends on the input of the same cycle as well as on the state, is called a Mealy machine. That is the kind this book teaches first. A Moore machine writes the output inside each state instead, so the output depends only on the state. Lecture 5 shows the instruction-fetch controller of the Intel 8086 as a historical Moore machine.^{F (fact ch05/moore-8086)}

The long-press detector

Example 5.2.1(detect three 1s in a row).

A button is read once per clock cycle, giving an input In that is 1 when the button is down. We want an output Out that is 1 in the cycle that shows the third 1 in a row. After that pulse the count starts again, so six 1s in a row give two pulses, one for the third 1 and one for the sixth. A 0 anywhere resets the count.

One assumption sits under this example, and under every machine in this chapter: each cycle's input is taken as it is, so a button that stays down for three clock cycles gives three 1s in a row. The machines do not turn a press, a coin or a switch of any length into one clean pulse. With a fast clock a human press lasts a very large number of cycles, and this detector would fire at the third of them and then again every third cycle until the button comes up. How inputs from the outside world are brought into a clocked design is the subject of Chapter 6 (not written yet).

First decide what to remember. At any moment, the useful fact is how many 1s in a row we have seen since the last 0 or the last pulse: none, one, or two. We never need to remember "three", because the moment we see a third 1 we pulse and start over. That gives three states, which we call S0 (none), S1 (one) and S2 (two).

Figure 5.2.1. The long-press detector. S0 is the initial state, marked by the thick arrow from nowhere; labels are input over output.

Now go state by state, asking what each input should do.

In S0 we have no 1s. An input of 0 changes nothing, so the arrow loops back to S0 with output 0. An input of 1 is our first 1, so we move to S1, still with output 0.

In S1 we have one 1. A 0 breaks the run and sends us back to S0. A 1 makes it two in a row, so we move to S2.

In S2 we have two 1s. A 0 breaks the run and sends us back to S0, with output 0. A 1 is the third in a row. This is the one arrow with output 1, and it goes back to S0, because after the pulse the count restarts. If this arrow went to S2 instead, a run of six 1s would pulse four times.

The same six arrows, written as a table with one row for every state and input combination, are easier to check for completeness:

State table of ch05/long-press: one row for every present state and input combination, giving the next state and the output; inputs in the order In.
Present state	In	Next state	Out
S0	0	S0	0
S0	1	S1	0
S1	0	S0	0
S1	1	S2	0
S2	0	S0	0
S2	1	S0	1

The machine is in S0 and the input is 1, 1, 1, 1, 1, 1 in six consecutive cycles. In which of those cycles is the output 1? The third and the fourth The third and the sixth Only the sixth

In SystemVerilog

The course writes a state machine in four parts: a declaration of the states, the logic that computes the next state, the logic that computes the output, and the register that holds the state. Here is the long-press detector in that shape.

// A long-press detector: Out is 1 in the cycle that shows the third 1 in a row.
module long_press(input logic clk, reset, In, output logic Out);
  enum logic [1:0] {S0 = 2'b00, S1 = 2'b01, S2 = 2'b10} ps, ns;

  // Next state: one arm per state; an if on In picks between a state's arrows. S2 needs none: both its arrows go to S0.
  always_comb
    case (ps)
      S0: if (In) ns = S1;
          else ns = S0;
      S1: if (In) ns = S2;
          else ns = S0;
      S2: ns = S0;
      default: ns = S0;
    endcase

  // Output: a Mealy output, so it looks at the input as well as the state.
  assign Out = (ps == S2) & In;

  // State update: the only place the machine remembers anything.
  always_ff @(posedge clk)
    if (reset) ps <= S0;
    else ps <= ns;
endmodule

The enum gives each state a name and a code. Because the names in the file match the names in the diagram, the picture and the code can be compared line by line. The codes in the enum are the ones that Example 5.3.1 uses when it turns the same machine into gates and flip-flops. Two variables are declared, ps for the present state and ns for the next state. The next-state logic is a case on ps, with one arm per circle of the diagram. Inside an arm, an if on In picks between the circle's arrows. In S2 both arrows go to S0, so that arm needs no if: one assignment stands for both arrows. The output, which does differ between those two arrows, is computed separately below. There is also a default arm, which covers the codes that no state uses, so every path assigns ns.

The output is a single assign. It is 1 exactly when the machine is in S2 and the input is 1, which is the one arrow labeled 1/1. Because it looks at In, it changes as soon as In changes within a cycle. That is what makes this a Mealy machine, and a second testbench below shows it.

The last block is the only place the circuit remembers anything. At each rising clock edge, ps takes the value of ns, unless reset is 1, in which case it takes S0. The reset is synchronous: it takes effect at a clock edge, not the instant it is raised.

A testbench for the module is shown next. It follows the book's testbench pattern (Section 4.8): no ports, an instance named dut, a clock from a forever loop inside an initial block, and one initial block that drives the inputs.

// Testbench for long_press: reset, then fourteen cycles of input, then a reset in the middle of a run.
module long_press_tb();
  logic clk, reset, In, Out;

  long_press dut(.*);

  parameter CLOCK_PERIOD = 100;

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

  initial begin
    reset <= 1; In <= 0; @(posedge clk);
    reset <= 0; In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S2, Out=1
                In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S2, Out=1
                In <= 0; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
                In <= 0; @(posedge clk);   // expect: ps=S2, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S2, Out=1
                In <= 0; @(posedge clk);   // expect: ps=S0, Out=0
    // A second run, interrupted by reset while the machine is in S1.
                In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                reset <= 1; @(posedge clk);   // expect: ps=S1, Out=0
    reset <= 0; In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S2, Out=1
                In <= 0; @(posedge clk);   // expect: ps=S0, Out=0
                         @(posedge clk);
    $stop;
  end
endmodule

Each line of the stimulus sets the inputs and then waits for the next rising edge. The inputs are set with <=, the nonblocking assignment. The new value takes effect at the same instant as the clock edge, but only after every flip-flop triggered by that edge has read its input, so the dut sees the value the input had before the edge. (Definition 5.1.2 explains why. It is the simulator's idealization of an input that changes just after the edge, as Section 4.7 described, and not a guarantee about every real input.) Each // expect: comment says what the signals should be just before the edge at the end of that line, and the book's tools run the testbench and check every one. That reading rule is easy to get wrong: the comment on a line reports the state that the previous edge produced, not the edge that ends the line. So the third In <= 1 shows ps=S2, Out=1: two earlier 1s have already moved the machine to S2, and the third 1 is on the input now. The course writes the same information as a // curr state: comment on each line.^{F (fact ch05/curr-state-comment)} The book's // expect: form is that comment made checkable.

Time in ps; one column is 50 ps.

Figure 5.2.2. The first part of the testbench run, with the state shown by name. Out is high in the cycles where the third 1 of a run is on the input.

Time in ps; one column is 50 ps.

Figure 5.2.3. A later part of the same run. A reset arrives while the machine is in S1, and the count starts over.

Read Figure 5.2.2 from left to right. Before the first edge, reset is high and the state is unknown, so it is drawn hatched. The first edge sets the state to S0, and reset falls at that same edge. From then on the state follows the arrows: each 1 at an edge moves the machine one state along, and the third 1 brings it back to S0. Out is high during the cycle that holds the third 1. The waveform shows the state by the names of the enum constants. In this run Out changes only at edges, but that is because this testbench changes In only at edges. Out is computed from In directly, so if In changed halfway through a cycle, Out would change with it, in the middle of the cycle and before any edge.

Changing the input in the middle of a cycle

The second testbench does exactly that. It uses the same module and gives In a few changes between edges while the machine is in S2. A # delay waits for that many time units, here a quarter and a half of the clock period (Definition 5.1.1 covers the timing controls).

// A second testbench for long_press: In changes in the middle of a clock cycle, while the machine is in S2.
module long_press_mid_tb();
  logic clk, reset, In, Out;

  long_press dut(.*);

  parameter CLOCK_PERIOD = 100;

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

  initial begin
    reset <= 1; In <= 0; @(posedge clk);
    reset <= 0; In <= 1; @(posedge clk);   // expect: ps=S0, Out=0
                In <= 1; @(posedge clk);   // expect: ps=S1, Out=0
    // The machine is in S2 now. In falls at the edge and stays low for a quarter of the cycle.
                In <= 0; #(CLOCK_PERIOD / 4);   // expect: ps=S2, Out=0
    // In rises in the middle of the cycle: Out rises with it, but ps is still S2.
                In <= 1; #(CLOCK_PERIOD / 2);   // expect: ps=S2, Out=1
    // In falls again before the edge: Out falls with it. The edge sees In = 0, so the state goes to S0.
                In <= 0; @(posedge clk);   // expect: ps=S2, Out=0
                         @(posedge clk);   // expect: ps=S0, Out=0
    $stop;
  end
endmodule

Time in ps; one column is 25 ps.

Figure 5.2.4. Out follows In in the middle of a cycle, while ps stays in S2 until the next edge.

Look at Figure 5.2.4 in the cycle that starts when the machine enters S2. In is 0 at that edge, so Out is 0 at first. A quarter of the way into the cycle In rises, and Out rises at that very instant, although ps is still S2 and no clock edge has happened. Half a clock period later In falls, and Out falls with it. At the next rising edge the machine sees In = 0, so it goes from S2 to S0, and the pulse on Out is over. The state changed only at the edge, while the output followed the input between edges. The three // expect: lines that read the signals during that cycle say the same: Out is 0, then 1, then 0 while ps is S2 on all three.

That is what Mealy means: the output depends on the input of the current cycle as well as on the state, so it can change at any moment In does. An output that came straight from a register could change only at an edge, together with the state.

Course conventions

How CSE 369 writes this

In CSE 369 we teach Mealy machines first, and the initial state is the one with an arrow coming from nowhere. When a machine has several inputs, the input part of a label is a string of bits in a declared input order, or a product of literals such as $\overline{N}D$ , or a sum of such products. Many textbooks, including B&V, start with Moore machines, where the output is written inside the circle, so check which kind a diagram uses before reading its labels.

Pitfalls

Common pitfall

Reading a label backward. The input comes first: 1/0 means input 1, output 0, and not the other way round.
Leaving an input value out. Unless it can never happen, every input value needs an arrow from every state, or the machine has no defined behavior there.
Forgetting that the run restarts. The arrow from S2 on a 1 returns to S0, so after a pulse the count begins again. Sending it somewhere else changes how many pulses a long run produces.
Expecting the output to wait for the clock edge. In a Mealy machine the output follows the input of the same cycle, so it can change in the middle of a cycle, before the state has changed.
Tracing from the wrong state. A machine begins in its initial state only after reset. Before that, the state register holds an unknown value.
Testing with one lucky input sequence. Taking every arrow at least once is the least a test can do, and an arrow that is never taken is never tested (Section 5.6 says what even that leaves out).

Check your understanding

Take the quiz (6 questions)

Exercises

Exercise 5.2.1

The figure shows the clock and the inputs of the long-press detector for a run in which reset is asserted in the middle. Work out the state and the output in every cycle. Just before the first edge shown, the machine is in S0. In this simulation an input that changes at an edge is drawn changing at that edge, and the simulator counts it as changing just after it, so the machine sees the value the input had before the edge (Section 4.7).

Time in ps; one column is 50 ps.

Figure 5.2.5. The question: only the clock and the inputs.

Hint

The state only changes at a rising clock edge, and the reset has priority over the input at that edge. The output is 1 only in a cycle that has the machine in S2 with a 1 on the input.

Solution

At each edge, the state becomes S0 if reset is high, and otherwise the state the arrow for the current input leads to. Take the edges one at a time, using the value each input had just before the edge.

Edge at 1450: In was 0, so the machine stays in S0.
Edge at 1550: In was 1, so S0 goes to S1.
Edge at 1650: reset was 1, so the machine goes to S0, and the 1 on In is ignored.
Edge at 1750: reset has fallen and In was 1, so S0 goes to S1.
Edge at 1850: In was 1, so S1 goes to S2. Until the next edge the machine is in S2 with In = 1, so Out is 1.
Edge at 1950: In was 1 in S2, so the machine goes to S0.
Edge at 2050: In was 0, so it stays in S0.

Reset arrived while the machine was in S1, so the run of 1s was cut short and gave no pulse. After the reset, three 1s in a row produce one pulse.

Time in ps; one column is 50 ps.

Figure 5.2.6. The answer: every signal, from the simulation of the testbench.

Tags: Warm-upFinite state machinesWaveforms

Exercise 5.2.2

You have written a long-press detector, and you want a testbench that checks it. Plan a test that starts from reset and takes every arrow of the diagram at least once, using as few clock cycles as possible.

Hint

Which arrows lead back to S0? After taking one of them, where are you standing, and how many cycles does it cost to get to the next arrow you still need?

Solution

The goal is to take every arrow at least once. Start from the initial state, since every real run starts after a reset, and find a walk through the diagram that crosses each arrow. A program searched every possible walk, and the table below is a shortest one: no shorter walk exists, although other walks of the same length do (there are several). Each row is one clock cycle, giving the input to apply and the state and output to expect.

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

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

Test plan for ch05/long-press: one row per clock cycle after the first reset cycle; 10 cycles: 1 reset cycle, then 9 arrows taken. The machine has 6 arrows.
Cycle	State	Input In	Next state	Output Out	Arrow
0	reset asserted: the machine starts in S0
1	S0	0	S0	0	1
2	S0	1	S1	0	2
3	S1	0	S0	0	3
4	S0	1	S1	0	2
5	S1	1	S2	0	4
6	S2	0	S0	0	5
7	S0	1	S1	0	2
8	S1	1	S2	0	4
9	S2	1	S0	1	6

The Cycle column of a tour table counts the reset cycle, the cycle in which reset is asserted, as cycle 0, so the first input is applied in cycle 1. The scenario tables that Section 5.4 introduces count differently: their cycle 0 is the first cycle after reset. So cycle $k$ of a scenario is cycle $k+1$ of a tour table. Wherever a page of this chapter names a cycle number, it says which kind of table it means.

Figure 5.2.7. The same diagram with its arrows numbered. The last column of the table uses these numbers.

The last column of the table gives the number of the arrow taken in each cycle. In this tour arrow 2 (S0 to S1 when In=1, output 0) is crossed three times and arrow 4 (S1 to S2 when In=1, output 0) twice. The reason is that S2 can be reached only through those two arrows, and arrows 3, 5 and 6 all end back in S0. After arrow 3 and after arrow 5 the machine must climb again, through S1 to S2, before it can reach an arrow that is still missing; arrow 6 ends the tour. Turn each row into one line of the testbench, in the shape of the listing above, with the State column (the state before the edge, not Next state) in the // expect: comment.

Tags: StandardFinite state machinesTest benches and simulation

Exercise 5.2.3

Change the long-press detector so that it pulses on every second consecutive 1, not every third. Six 1s in a row should give three pulses.

Draw the state diagram, and write its state table.
Optional, a preview of Section 5.5: write the module.

Hint

How many things does the machine now have to remember? Start by drawing S0 and S1, and ask what each input does in each state.

Solution

Counting to two needs only two states: S0 (no 1 waiting) and S1 (one 1 seen). From S0, a 0 stays in S0 and a 1 moves to S1. From S1, a 0 returns to S0, and a 1 is the second in a row, so the machine pulses and returns to S0 to start counting again.

Figure 5.2.8. A two-state detector that pulses on every second consecutive 1.

The state table, one row for every state and input combination:

State table of ch05/s02-pair-press: one row for every present state and input combination, giving the next state and the output; inputs in the order In.
Present state	In	Next state	Out
S0	0	S0	0
S0	1	S1	0
S1	0	S0	0
S1	1	S0	1

For the optional module, the four parts are the same as before. The declaration shrinks to two states and one state bit, and the next-state and output logic follow the new diagram. The state register is unchanged.

// Exercise solution: Out is 1 in the cycle that shows the second 1 of a run, and the count restarts.
module pair_press(input logic clk, reset, In, output logic Out);
  enum logic {S0 = 1'b0, S1 = 1'b1} ps, ns;

  always_comb
    case (ps)
      S0: if (In) ns = S1;
          else ns = S0;
      S1: ns = S0;
      default: ns = S0;
    endcase

  assign Out = (ps == S1) & In;

  always_ff @(posedge clk)
    if (reset) ps <= S0;
    else ps <= ns;
endmodule

Tags: StandardFinite state machinesSystemVerilog