FSM Coding Styles: One, Two and Three Procedures

Write one state machine in each common style. Predict the cycle its outputs change in, and whether flops or gates drive them.

You Will Be Able To

  • Predict the cycle in which an output changes in a one-, two- and three-procedure machine.
  • Write registered outputs that are decoded from the next state and arrive on time.
  • Write a one-hot machine with a reverse case, and explain what unique adds in each tool.
  • Find the latch in an output decoder that leaves a state out.
Lesson
R11.4
Time
30 min
Runs on
Your browser
Check
5 questions

A flash controller charges a capacitor until a sensor says charged, then fires. A rewrite put the whole machine in one clocked block "to register the outputs". On the bench the pump ran one cycle too long into a full capacitor. The lamp fired one cycle after the shutter.

Every Output One Cycle LateThe lab bench, 1 ns after edges 2 to 8. state is the state the machine is in. The brief rows are what the brief asks for. The shipped rows are the one-procedure design.
0123456clkstateCHARGEAIMFIRECOOLIDLEchargedcharge (brief)charge (shipped)fire (brief)fire (shipped)pump latepump still onfires late
Scroll horizontally ↔
  1. Cycle 0

    Edge 2: the machine enters CHARGE. The brief wants the pump on now. The shipped design turns it on one edge later.

  2. Cycle 2

    Edge 4: charged was seen and the machine is in AIM. The shipped pump is still on.

  3. Cycle 3

    Edge 5: the machine is in FIRE. The brief fires here.

  4. Cycle 4

    Edge 6: the shipped design fires now, in COOL.

The state sequence is right. Only the outputs are late, each by exactly one cycle.

Three Blocks, and Three Ways to Write Them

Every state machine has three parts. The state register holds the state. The next-state logic picks the state to enter at the next edge. The output logic turns the state into outputs.

The Three Parts of a State MachineArrows show signals. The styles differ in how many procedures hold these three parts.
  • I/O
  • Control / FSM
  • Storage
  • Control
The three parts of a state machineArrows show signals. The styles differ in how many procedures hold these three parts. io Inputs trig, charged, cooled control Next-state logic gates: picks state_d storage State register flops: state_q control Output logic gates: decodes thestate io Outputs charge, fire, busy inputsstate_dstate_qstate_qoutputs
  1. control Next-state logicgates: picks state_d
    • state_d → State register
  2. storage State registerflops: state_q
    • state_q → Next-state logic
    • state_q → Output logic
  3. control Output logicgates: decodes the state
    • outputs → Outputs
  4. io Outputscharge, fire, busy
  5. io Inputstrig, charged, cooled
    • inputs → Next-state logic
  1. Three procedures

    One always_ff for the register, one always_comb for the next state, one always_comb or assign for the outputs.

  2. Two procedures

    One always_ff for the register. One always_comb holds the next state and the outputs. This is the house style of lesson R3.2.

  3. One procedure

    Everything sits in one always_ff. The outputs become flops, loaded from the state before the edge.

Read the diagram as text
  • Inputs: trig, charged, cooled
  • Next-state logic: gates: picks state_d
  • State register: flops: state_q
  • Output logic: gates: decodes the state
  • Outputs: charge, fire, busy
  • Inputs → Next-state logic: inputs
  • Next-state logic → State register: state_d
  • State register → Next-state logic: state_q
  • State register → Output logic: state_q
  • Output logic → Outputs: outputs

The same three parts are in every style. What changes is where the outputs are decoded and whether a flop holds them.

Stylecharge is 1 at edgesfire is 1 at edgeOutputs driven byCellsFlopsLevels
Three procedures2, 35gates after the state flops1634
Two procedures2, 35charge, fire: state flops. busy: a gate1752
One procedure, outputs from state_q (shipped)3, 46flops2082
Outputs registered from state_d2, 35flops2584

The lab bench on Icarus 12, and the pinned Yosys. The brief asks for edges 2, 3 and 5. This flow re-encoded three of the four machines one-hot (lesson R3.2), which is why the flop counts differ.

The three-procedure version
16 cells, 3 flops, 4 levels. Each output is one compare of the state bits.
module shot_ctrl (
  input  logic clk,
  input  logic rst_n,      // asynchronous, active-low
  input  logic trig,       // start a shot
  input  logic charged,    // the capacitor is full
  input  logic cooled,     // the lamp may fire again
  output logic charge,     // run the charge pump
  output logic fire,       // fire the lamp, one cycle
  output logic busy
);
  typedef enum logic [2:0] {IDLE, CHARGE, AIM, FIRE, COOL} state_e;
  state_e state_q, state_d;

  always_ff @(posedge clk or negedge rst_n)     // 1: the state register
    if (!rst_n) state_q <= IDLE;
    else        state_q <= state_d;

  always_comb begin                             // 2: the next state
    state_d = state_q;
    case (state_q)
      IDLE:    if (trig)    state_d = CHARGE;
      CHARGE:  if (charged) state_d = AIM;
      AIM:                  state_d = FIRE;
      FIRE:                 state_d = COOL;
      COOL:    if (cooled)  state_d = IDLE;
      default:              state_d = IDLE;
    endcase
  end

  always_comb begin                             // 3: the outputs, from the state
    charge = (state_q == CHARGE);
    fire   = (state_q == FIRE);
    busy   = (state_q != IDLE);
  end
endmodule

Registered Outputs with No Extra Cycle

A registered output is steady for the whole cycle and has the shortest delay after the clock. The one-procedure style gets those flops and loses a cycle. One change gets both: decode the output from state_d, the state the machine is about to enter.

From the present state: a cycle late

always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) fire <= 1'b0;
  else        fire <= (state_q == FIRE);

The flop loads 1 at the edge where the machine leaves FIRE. The output is 1 during COOL.

From the next state: on time

always_ff @(posedge clk or negedge rst_n)
  if (!rst_n) fire <= 1'b0;
  else        fire <= (state_d == FIRE);

The flop loads 1 at the edge where the machine enters FIRE. The output is 1 during FIRE.

The whole controller with outputs registered from the next state
25 cells, 8 flops, 4 levels. In the netlist a $_DFF_PN0_ flop drives each output directly.
module shot_ctrl (
  input  logic clk,
  input  logic rst_n,      // asynchronous, active-low
  input  logic trig,       // start a shot
  input  logic charged,    // the capacitor is full
  input  logic cooled,     // the lamp may fire again
  output logic charge,     // run the charge pump
  output logic fire,       // fire the lamp, one cycle
  output logic busy
);
  typedef enum logic [2:0] {IDLE, CHARGE, AIM, FIRE, COOL} state_e;
  state_e state_q, state_d;

  always_comb begin
    state_d = state_q;
    case (state_q)
      IDLE:    if (trig)    state_d = CHARGE;
      CHARGE:  if (charged) state_d = AIM;
      AIM:                  state_d = FIRE;
      FIRE:                 state_d = COOL;
      COOL:    if (cooled)  state_d = IDLE;
      default:              state_d = IDLE;
    endcase
  end

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin
      state_q <= IDLE;
      charge  <= 1'b0;
      fire    <= 1'b0;
      busy    <= 1'b0;
    end else begin
      state_q <= state_d;
      charge  <= (state_d == CHARGE);     // decoded from the state being entered
      fire    <= (state_d == FIRE);
      busy    <= (state_d != IDLE);
    end
endmodule

The price is logic in front of the output flops: the next-state logic and then the decode. Give each registered output a reset value, or it is unknown until the first edge.

One-Hot by Reverse case

A one-hot machine has one flop per state, and exactly one of them holds 1. Testing "am I in FIRE?" is then a look at one bit. The reverse case writes that directly. Its case expression is the constant 1'b1, and each item is one state bit.

18 cells, 5 flops, 4 levels. charge and fire are state flops. busy is one inverter.
module shot_ctrl (
  input  logic clk,
  input  logic rst_n,      // asynchronous, active-low
  input  logic trig,       // start a shot
  input  logic charged,    // the capacitor is full
  input  logic cooled,     // the lamp may fire again
  output logic charge,     // run the charge pump
  output logic fire,       // fire the lamp, one cycle
  output logic busy
);
  localparam int IDLE = 0, CHARGE = 1, AIM = 2, FIRE = 3, COOL = 4;   // bit numbers: one flop per state
  logic [4:0] state_q, state_d;

  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) state_q <= 5'b00001;
    else        state_q <= state_d;

  always_comb begin
    state_d = '0;
    unique case (1'b1)                    // which state bit is 1?
      state_q[IDLE]:   if (trig)    state_d[CHARGE] = 1'b1; else state_d[IDLE]   = 1'b1;
      state_q[CHARGE]: if (charged) state_d[AIM]    = 1'b1; else state_d[CHARGE] = 1'b1;
      state_q[AIM]:                 state_d[FIRE]   = 1'b1;
      state_q[FIRE]:                state_d[COOL]   = 1'b1;
      state_q[COOL]:   if (cooled)  state_d[IDLE]   = 1'b1; else state_d[COOL]   = 1'b1;
      default:                      state_d[IDLE]   = 1'b1;     // no bit set: go home
    endcase
  end

  assign charge = state_q[CHARGE];
  assign fire   = state_q[FIRE];
  assign busy   = !state_q[IDLE];
endmodule
SpellingCellsLevelsNo bit set (zero-hot)Two bits set
unique case (1'b1) with a default184returns to IDLEthe first matching item wins
case (1'b1) with a default214returns to IDLEthe first matching item wins
priority case (1'b1), no default214stays at 00000 for everthe first matching item wins
unique case (1'b1), no default152stays at 00000 for everthe first matching item wins

Cells and levels on the pinned Yosys. Behaviour on Icarus 12, with the state forced by the bench. unique let the tool drop the priority between items.

unique is also a check in simulation, and the tools differ on how much of it they run.

ToolTwo bits set, unique with a defaultNo bit set, unique with no default
Icarus 12no messageWARNING: value is unhandled for priority or unique case statement
Verilator 5.052stops: unique case, but multiple matches foundstops: unique case, but none matched
Lintno messageno message

With no default, both simulators report at time 0, before reset, because the state is still unknown there.

Latches in the Decoders

A combinational decoder must give every output a value in every state. Leave one out and the output has to remember, which is a latch. FSM decoders are where this happens most, because each state lists only the outputs it cares about.

Each state lists only what it sets

always_comb
  case (state_q)
    IDLE:   begin charge = 1'b0; fire = 1'b0; busy = 1'b0; end
    CHARGE: begin charge = 1'b1; busy = 1'b1; end
    AIM:    begin busy = 1'b1; end
    FIRE:   begin fire = 1'b1; busy = 1'b1; end
    COOL:   begin busy = 1'b1; end
  endcase

Lint: LATCH for charge, fire and busy, and CASEINCOMPLETE. Synthesize refuses the block: found logic loop. Written with always @* it builds 3 $_DLATCH_P_ cells.

Defaults first, then the exceptions

always_comb begin
  charge = 1'b0;
  fire   = 1'b0;
  busy   = 1'b1;
  case (state_q)
    IDLE:    busy   = 1'b0;
    CHARGE:  charge = 1'b1;
    FIRE:    fire   = 1'b1;
    default: ;
  endcase
end

Every path assigns all three outputs. No latch, and each state shows only what makes it different.

The same rule covers state_d. Start the next-state block with state_d = state_q;, as lesson R3.2 does. Lesson R11.5 compares five ways to close such gaps.

The Lab: Outputs a Cycle Late

Design brief
PortDirectionWidthMeaning
clkinput1clock
rst_ninput1reset, asynchronous, active-low
triginput1start a shot
chargedinput1the capacitor is full
cooledinput1the lamp may fire again
chargeoutput11 while the machine is in CHARGE
fireoutput11 while the machine is in FIRE, one cycle
busyoutput11 in every state but IDLE
Clock
rising edge
Reset
rst_n asynchronous, active-low; IDLE, all outputs 0
Corner cases
the cycle a state is entered. Done when: Run shows charge=1 at edges 2 and 3 only and fire=1 at edge 5. Flops still drive the outputs
  1. Run as shipped

    charge is 1 at edges 3 and 4, and fire at edge 6. The brief says 2, 3 and 5. Synthesize reports 20 cells and 8 flops.

  2. Try the three-procedure form

    Replace the body with the three-procedure version from the first section. Run: the outputs are on time. Synthesize: 16 cells, 3 flops. The outputs now come from gates.

  3. Register them again, on time

    Use the version registered from state_d. Run: the same lines as the three-procedure form. Synthesize: 25 cells, 8 flops.

  4. Check what drives the outputs

    Open the Gates tab. In the registered version each output is the Q pin of a flop. In the three-procedure version each one is a gate.

Asked in interviews
  1. What are the one-, two- and three-procedure FSM styles?

    Three procedures separate the state register, the next-state logic and the output logic. Two procedures merge the two combinational parts. One procedure puts everything in a clocked block, which registers the outputs.

  2. How do you register FSM outputs without adding a cycle?

    Decode them from the next state, not the present one. The output flop then loads at the same edge as the state register. The output is valid in the cycle the state is entered.

  3. What is a reverse case statement?

    A case (1'b1) whose items are single state bits of a one-hot machine. Each test is one bit, not a full compare. Keep a default so a state with no bit set can recover.

Try It

The bench changes its inputs 1 ns after an edge and prints 1 ns after the next one. The machine enters CHARGE at edge 2, AIM at edge 4 and FIRE at edge 5. It enters COOL at edge 6 and IDLE at edge 7.

Each printed output belongs to the state of one edge earlier. charge is still 1 at edge 4, after charged was seen. fire is 1 at edge 6, when the machine is already in COOL.

Synthesize reports 20 cells: 8 flops and 12 gates, with 2 levels of logic. Five flops hold the state, which this flow re-encoded one-hot. Three hold the outputs.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: e2 trig=1 charged=0 cooled=0 | charge=0 fire=0 busy=0 e3 trig=0 charged=0 cooled=0 | charge=1 fire=0 busy=1 e4 trig=0 charged=1 cooled=0 | charge=1 fire=0 busy=1 e5 trig=0 charged=0 cooled=0 | charge=0 fire=0 busy=1 e6 trig=0 charged=0 cooled=0 | charge=0 fire=1 busy=1 e7 trig=0 charged=0 cooled=1 | charge=0 fire=0 busy=1 e8 trig=0 charged=0 cooled=0 | charge=0 fire=0 busy=0

Original design · 20 cells · 8 flip-flops · 0 latches · 2 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
`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, rises 1 ns after edge 1
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic trig = 0, charged = 0, cooled = 0;
  logic charge, fire, busy;
  shot_ctrl dut (.*);
  task automatic tick();
    @(posedge clk); #1;
    if (rst_n) $display("e%0d trig=%b charged=%b cooled=%b | charge=%b fire=%b busy=%b", edge_n, trig, charged, cooled, charge, fire, busy);
  endtask
  initial begin
    #1 rst_n = 0; tick(); tick(); rst_n = 1;
    trig = 1;    tick();   // e2: the shot starts
    trig = 0;    tick();
    charged = 1; tick();   // e4: the capacitor is full
    charged = 0; tick();
                 tick();
    cooled = 1;  tick();   // e7: the lamp has cooled
    cooled = 0;  tick();
    $finish(0);
  end
endmodule

Check Yourself

Spot the bugThe brief wants done at 1 in the cycle the machine is in LAST. Each option drives done. The bench checks it after every edge. Which option fails?
ConceptThe one-hot reverse case was written as unique case (1'b1) with no default. On this flow it was the smallest version. What happened when the state had no bit set?
ConceptIn which version of the lab controller can fire glitch between clock edges?
ConceptAn output decoder is an always_comb with a case over five states. The CHARGE item assigns charge and busy, and says nothing about fire. What did the tools report for this block?
Predict the outputThe machine goes IDLE, RUN, LAST, IDLE. Flop a loads a decode of the present state and flop b a decode of the next state. After each of four edges the bench prints a then b. What exact line does it print?
module tb;
  typedef enum logic [1:0] {IDLE, RUN, LAST} state_e;
  state_e state_q, state_d;
  logic clk = 0, rst_n = 1, go = 0, a, b;
  always_comb begin
    state_d = state_q;
    case (state_q)
      IDLE:    if (go) state_d = RUN;
      RUN:             state_d = LAST;
      default:         state_d = IDLE;
    endcase
  end
  always_ff @(posedge clk or negedge rst_n)
    if (!rst_n) begin state_q <= IDLE; a <= 1'b0; b <= 1'b0; end
    else begin
      state_q <= state_d;
      a       <= (state_q == LAST);
      b       <= (state_d == LAST);
    end
  initial begin
    #1 rst_n = 0;
    #1 rst_n = 1;
    go = 1;
    repeat (4) begin #4 clk = 1; #1 $write("%b%b", a, b); go = 0; #5 clk = 0; end
    $write("\n");
    $finish(0);
  end
endmodule

Common Mistakes

Wrong Move the output assignments into the clocked case to "register the outputs", and keep the old timing in mind.

An output set from the present state arrives one cycle after the machine enters that state.

Fix Decode registered outputs from state_d, the state being entered, or keep them combinational.

Before
always_ff @(posedge clk)
  case (state_q)
    FIRE: begin fire <= 1'b1; state_q <= COOL; end
    // ...
  endcase
After
always_ff @(posedge clk) begin
  state_q <= state_d;
  fire    <= (state_d == FIRE);
end

Wrong Drop the default item from a one-hot reverse case because unique says exactly one bit is set.

Synthesis then builds no way out of a state with no bit set, and the machine stays there.

Fix Keep a default that returns to the reset state, and let unique report two bits set in simulation.

Wrong Treat a combinational output as safe to use as a clock, a reset or an asynchronous strobe.

An output decoded by gates can glitch between edges while the state bits settle.

Fix Take such signals from a flop: a registered output, or a state bit of a one-hot machine.

Wrong Judge a style by its flop count on this flow.

The synthesizer may re-encode the state, so the count depends on the tool as much as on the style.

Fix Compare what the brief cares about: the cycle each output changes in, and what drives it.

Remember

  • A state machine is a state register, next-state logic and output logic. The styles differ in which procedure holds each.
  • Outputs assigned from state_q in a clocked block arrive one cycle late.
  • Register outputs from state_d to get flop outputs with no extra cycle.
  • A reverse case (1'b1) tests one bit per state. Keep its default, and know what unique does in your tools.
  • Give every output a default at the top of a decoder, or the missing state builds a latch.

Practice

Report a problem with this page