09A state machine from a state table

1. A state machine is one register and two combinational blocks

Every sequential circuit in this course so far was a state machine with a number for a state: a counter whose state is its count. A state machine in the narrow sense has a small set of named states, and it is built from three parts you already know.

A machine whose outputs depend on the state alone is a Moore machine; one whose outputs also read the inputs directly is a Mealy machine. The assumptions are the same as everywhere in this course: one clock, rising edge, synchronous reset.

2. The state table says everything before any code exists

Take the rise detector from Register stages, observation and waveforms and give its memory a name. The one register prev has two values, so there are two states: LOW, meaning the last sampled level was 0, and HIGH, meaning it was 1. The input is level; the output rise is 1 when a rise is being seen right now.

Every row is one edge: the state and input before it, the state after it. rise reads the input, so this is a Mealy output. The table has 2 states × 2 input values = 4 rows, and like a truth table it must have a row for every combination before you write code.

3. The code follows the table part by part

The table becomes three blocks of RiseFsm.v. Read it next to the table, one part at a time.

// A two-state rise detector built from its state table.
module rise_fsm (
  input      clock,
  input      reset,
  input      level,
  output     rise,
  output reg pulse,
  output reg state
);
  localparam LOW = 1'b0, HIGH = 1'b1;
  reg next;

  // Next-state logic: one branch per current state, every path assigned.
  always @* begin
    case (state)
      LOW:     next = level ? HIGH : LOW;
      HIGH:    next = level ? HIGH : LOW;
      default: next = LOW;
    endcase
  end

  // State register: the only block that writes state.
  always @(posedge clock) begin
    if (reset) state <= LOW;
    else       state <= next;
  end

  // Mealy output: reads the state and the input of this cycle.
  assign rise = (state == LOW) & level;

  // Registered copy of rise: one edge later, one full period wide.
  always @(posedge clock) begin
    if (reset) pulse <= 1'b0;
    else       pulse <= rise;
  end
endmodule

localparam gives the states names; two states fit in one bit, three or four states need two bits, and so on. The case has one branch per state and a default, so next is assigned on every path, as Nets, variables and the combinational always required. The state register is the only clocked block that touches state, and reset puts the machine into a known state. Without reset, state is x at the start, case (state) matches no named state and takes the default branch, which sets next to LOW. The output rise can still be known when level is 0, because x & 0 is 0; when level is 1 it remains x until the state becomes known. The output rise is wired from state and input; pulse registers it, which is the version the Practice problem rise-pulse asked for. state is also a port here only so that the testbench can print it; a machine normally keeps its state inside.

4. Predict the machine cycle by cycle

The browser model rise-detect is this machine with prev as the state: prev 0 is LOW, prev 1 is HIGH. Its rise is the combinational output during a cycle, computed from the state at the start of the cycle and the input applied in it. Drive it a few cycles first.

Now fill in the table: prev after the edge that ends each cycle, and rise during the cycle.

5. Run the machine and compare it with your table

The testbench drives the pattern 0111010011 into level, one value per cycle, after a reset that spans two rising edges. It changes level on a falling edge and prints one time unit later, so every line shows, for one cycle:

Predict from the table before you run: write the state, rise and pulse columns for the ten cycles. The pattern contains a run of three 1s, so a level that stays high must not count as a new rise.

module tb;
  reg        clock = 0;
  reg        reset = 1;
  reg        level = 0;
  wire       rise, pulse, state;
  reg  [9:0] pattern = 10'b01110_10011;
  integer    i;
  integer    rises = 0;

  rise_fsm dut (.clock(clock), .reset(reset), .level(level), .rise(rise), .pulse(pulse), .state(state));

  always #5 clock = ~clock;

  initial begin
    $dumpfile("dump.vcd");
    $dumpvars(0, tb);
    // Reset across two rising edges, released on a falling edge.
    @(negedge clock);
    @(negedge clock) reset = 0;
    for (i = 0; i < 10; i = i + 1) begin
      // Inputs change on the falling edge; one time unit later the line shows
      // the state before the next rising edge and the outputs of this cycle.
      level = pattern[9 - i];
      #1 $display("cycle %0d: level=%b state=%s rise=%b pulse=%b",
                  i, level, state ? "HIGH" : "LOW ", rise, pulse);
      rises = rises + rise;
      @(negedge clock);
    end
    $display("DONE rises=%0d", rises);
    $finish;
  end
endmodule

Press Run and compare every line with your columns. The last line, DONE rises=3, is the testbench adding up rise over the ten cycles. Then open the waveform:

• tb.dut.state changes only at rising edges, and after each edge it equals the level that edge sampled;
• tb.rise goes high in the middle of a cycle, at the falling edge where level rises, and falls at the next rising edge when the state becomes HIGH;
• tb.pulse is rise shifted to the following rising edge, one full period wide.

If a printed line disagrees with your table, find that cycle in the waveform first and ask which of the three parts produced the wrong value: the state, the next-state logic, or the output logic.

6. The waveform must show three different kinds of signal

Checking a state machine in a waveform means knowing in advance how each signal is allowed to move.

If state moves between rising edges, check for a wrong sensitivity list or an assignment outside its clocked block. Blocking = inside always @(posedge clock) can create a race, but does not by itself make that block run between edges. If rise flickers between edges while level is noisy, that is correct for a Mealy output, and the reason to register it when the output must be stable for a whole cycle.

7. Break one transition, then verify again

A state machine is only as correct as every row of its table. Make these edits in the lab one at a time, predict, run, and restore the original before the next.

The first edit is the error the Practice problem below hides in its starter. The second shows why the reset value of the state is part of the contract: it decides what the first cycle after reset compares against.

8. Moore and Mealy in the same trace

rise and pulse in the trace you just ran mark the same event at two different moments.

A machine whose output reads the state alone needs a state that means "a rise was just sampled". Give the detector three states, LOW, ROSE and HIGH: LOW with level 1 goes to ROSE, ROSE goes to HIGH on 1 and back to LOW on 0, and the Moore output is 1 in ROSE. That output can only change at an edge, one cycle after the Mealy rise.

Choose by what the receiver needs: a Mealy output answers in the same cycle but follows any glitch on the input; a Moore output is stable for whole cycles and costs one cycle of latency, and here one extra state.

9. Variation: a toggle as a two-state Moore machine

Change the table and the same three parts build a different machine. A toggle has states OFF and ON and input t: with t 1 the next state is the other one, with t 0 it is the same one. The output q is 1 in ON, read from the state alone, so this one is a Moore machine. In the code only the case branches and the assign change. Predict q after each edge.

10. Apply it: repair a machine, then design one

Two Practice problems close the chapter, with less help in the second.

• Find the broken transition. The starter is this chapter's detector with one wrong branch. The trace shows the symptom; you compare the case with the table, find the row that is missing, and fix it.
• Design a three-state detector from its contract. Only the ports and the contract are given: seen is 1 while the last two sampled values of din were 1, as a Moore output. Write the state table first, then the state register, the next-state case and the output logic. Grading accepts any encoding that meets the contract and reports the first failing cycle, whether the check was before or after the edge, and the expected and actual value.

11. Summary

The testbench techniques for driving such a machine are in Testbench techniques, and recording its signals in a VCD is in Recording waveforms.