Coding an FSM: states, encodings, the default

Every code the register can hold

A state register of N bits can hold 2^N codes. The enum names five of them; the hardware does not know which ones have names. The next-state logic must say what happens in every code, including the ones no transition produces. That is the job of the default arm.

st_d = st_q;
case (st_q)
  ...
  DONE: st_d = IDLE;
endcase

st_d = st_q;
case (st_q)
  ...
  DONE:    st_d = IDLE;
  default: st_d = IDLE;
endcase

The tools can point at the gap before any upset. Lint (Verilator 5.052) reports %Warning-CASEINCOMPLETE: Case values incompletely covered (example pattern 0x5) on the case line. Written as unique case, the same block makes Icarus print value is unhandled for priority or unique case statement when the register holds 110.

The house style for a state machine

1. An enum with a logic base type

   typedef enum logic [2:0] {...} state_e; The simulator then rejects a bare number assigned to the state, and waveforms show names.

2. A clocked block for the register

   st_q <= st_d under the asynchronous reset. It looks the same in every machine.

3. A combinational block for the next state

   st_d = st_q; first, so every path assigns st_d and no latch is possible. Then unique case (st_q) with one arm per state and a default arm back to IDLE.

4. Outputs from the state

   Assigns or a third block decode the outputs. Moore or Mealy is the brief's choice (R3.1).

A one-block machine, with the next state and the outputs inside the clocked block, is legal. Its outputs are all registered, and its next-state logic is hidden among register updates. Reviews prefer separate blocks because each one does one job.

Encodings, and what the synthesizer did with yours

Binary numbers the states 0, 1, 2, ...: 3 flops for 5 states. One-hot gives each state its own flop, set only in that state: 5 flops, with outputs that are single register bits. Gray changes one bit per step and suits a state read by another clock domain (R6).

Press Synthesize on the lab and the report says 5 flops, although the enum has 3 bits. Yosys 0.70 recognized the state machine and re-encoded it. Its log, from a verbose run of the same flow, says so.

Found FSM state register seq5.st_q.
Recoding FSM `$fsm$\st_q$23' from module `\seq5' using `auto' encoding:
  mapping auto encoding to `one-hot` for this FSM.
  000 -> ----1
  100 -> ---1-
  010 -> --1--
  001 -> -1---
  011 -> 1----

With and without the default arm, Yosys 0.70 wrote the same 11-cell netlist: the arm for codes the machine cannot reach was dropped. Simulated as gates, that netlist failed in a new way. When an upset cleared its one set bit, the state stayed 00000 and start never moved it.

The attribute (* fsm_encoding = "none" *) on the state register tells Yosys to leave the machine alone. Then the code you wrote is the circuit you get, default arm included.

The lab

Run the lab: two jobs, the upset, then 110 until the end and "2 jobs started". Press Lint and read the CASEINCOMPLETE warning. Add default: st_d = IDLE; and run again: IDLE at e9, LOAD at e10, "3 jobs started". Synthesize: still 11 cells and 5 flops. Now write (* fsm_encoding = "none" *) in front of state_e st_q;: 13 cells, 3 flops, 2 levels. Last, change the enum to one-hot (IDLE = 5'b00001, ...): the bench still recovers, and Synthesize reports 27 cells, 5 flops, 5 levels.

Try it

The first job runs IDLE, LOAD, RUN, DRAIN, DONE, IDLE (edges 2 to 6). The second reaches RUN at edge 8, then the upset writes 110. From edge 9 on the register holds 110 and the request for a third job is ignored.

With the default arm, e9 shows 000, e10 shows 001 with load = 1, and the summary reads "3 jobs started". The bench forces 3'b110; after the switch to one-hot it lands as 00110, two bits set, which is just as illegal.

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic start = 0, last = 0;
  logic load, run, done;
  int   jobs = 0;
  seq5 dut (.clk(clk), .rst_n(rst_n), .start(start), .last(last), .load(load), .run(run), .done(done));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    if (load) jobs++;
    if (edge_n >= 2) $display("e%0d start=%b last=%b st=%b load=%b run=%b done=%b", edge_n, start, last, dut.st_q, load, run, done);
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    start = 1; tick(); start = 0;           // e2: LOAD
    tick();                                 // e3: RUN
    last = 1;  tick(); last = 0;            // e4: DRAIN
    tick(); tick();                         // e5: DONE, e6: IDLE
    start = 1; tick(); start = 0;           // e7: LOAD
    tick();                                 // e8: RUN
    #2 force dut.st_q = 3'b110;             // an upset: bit 2 of RUN (010) flips
    #1 release dut.st_q;
    $display("upset after e8: st_q = 110");
    tick();                                 // e9
    start = 1; last = 1;                    // ask for a third job
    tick(); tick(); tick();                 // e10 to e12
    $display("%0d jobs started", jobs);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

// seq5: a five-state sequencer. start begins a job: LOAD for one cycle, RUN until last,
// DRAIN for one cycle, DONE for one cycle, then IDLE.
module seq5 (
  input  logic clk,
  input  logic rst_n,      // asynchronous, active-low
  input  logic start,
  input  logic last,
  output logic load,
  output logic run,
  output logic done
);
  typedef enum logic [2:0] {IDLE, LOAD, RUN, DRAIN, DONE} state_e;   // binary: 0 to 4
  state_e st_q;
  state_e st_d;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) st_q <= IDLE;
    else        st_q <= st_d;

  always_comb begin
    st_d = st_q;                        // stay, unless an arm says otherwise
    case (st_q)
      IDLE:  if (start) st_d = LOAD;
      LOAD:  st_d = RUN;
      RUN:   if (last) st_d = DRAIN;
      DRAIN: st_d = DONE;
      DONE:  st_d = IDLE;
      default: st_d = IDLE;            // any other code: back to IDLE
    endcase
  end

  assign load = (st_q == LOAD);
  assign run  = (st_q == RUN);
  assign done = (st_q == DONE);
endmodule

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  logic rst_n = 1;                        // falls at 1 ns: a real edge, so an asynchronous reset acts before any clock
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic start = 0, last = 0;
  logic load, run, done;
  seq5 dut (.clk(clk), .rst_n(rst_n), .start(start), .last(last), .load(load), .run(run), .done(done));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;   // asserted at 1 ns, edges 0 and 1 in reset, released 1 ns after edge 1
    start = 1; tick(); start = 0; tick();   // e2 LOAD, e3 RUN
    #2 force dut.st_q = 3'b101;             // an upset in RUN: an unnamed code
    #1 release dut.st_q;
    start = 1;
    tick(); tick();                         // two edges later
    $display("st=%b load=%b run=%b", dut.st_q, load, run);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

st_d = st_q;
    case (st_q)
      IDLE:    if (start) st_d = LOAD;
      LOAD:    st_d = RUN;
      RUN:     if (last) st_d = DRAIN;
      DRAIN:   st_d = DONE;
      DONE:    st_d = IDLE;
      default: st_d = IDLE;
    endcase

st_d = st_q;
    case (st_q)
      IDLE:  if (start) st_d = LOAD;
      LOAD:  st_d = RUN;
      RUN:   if (last) st_d = DRAIN;
      DRAIN: st_d = DONE;
      DONE:  st_d = IDLE;
    endcase

st_d = IDLE;
    case (st_q)
      IDLE:  if (start) st_d = LOAD;
      LOAD:  st_d = RUN;
      RUN:   if (last) st_d = DRAIN; else st_d = RUN;
      DRAIN: st_d = DONE;
    endcase

st_d = st_q;
    unique case (st_q)
      IDLE:    if (start) st_d = LOAD;
      LOAD:    st_d = RUN;
      RUN:     if (last) st_d = DRAIN;
      DRAIN:   st_d = DONE;
      DONE:    st_d = IDLE;
      default: st_d = IDLE;
    endcase