Factoring and Communicating State Machines

Split a machine whose states only count time into a small main machine and a timer that talk through start and done.

You Will Be Able To

  • Spot states that only count cycles, and move them into a helper machine.
  • Connect a main machine and a timer with start, length and done signals.
  • Get the timer count right: load length minus one, and finish on done.
  • Compare the state counts of a flat machine and a factored one.
Lesson
G7.7
Time
30 min
Runs on
Your browser
Check
5 questions

A sign controller had to hold a light on for 30 cycles, then dark for 20. The first design drew one state per cycle: 51 states, and a change of time meant redrawing it. The fix kept three states and moved the counting into a timer. Here the lab lamp's two machines talk.

Two Machines and Their HandshakeOne column per cycle, from the lab run. start is the main machine's request; t is the timer; done is its answer.
0123456789101112clkgomainIDLEONOFFIDLEONOFFstarttdonelampstart, len 3done: start, len 2done
Scroll horizontally ↔
  1. Cycle 1

    go = 1 in IDLE. The main machine raises start with len = 3 for the edge that enters ON.

  2. Cycle 2

    The timer loaded 3 - 1 = 2 at that edge. done is 0 while it counts down.

  3. Cycle 4

    t = 0: done = 1 in the third ON cycle. The main machine moves to OFF and starts a 2-cycle count.

  4. Cycle 7

    done ends OFF after 2 cycles. The press in cycle 3 was ignored: ON never looks at go.

Measured: the lab below, on Icarus Verilog 12.

States That Only Count

Draw the lamp as one machine and you need a state for every cycle of light and dark. Those states make no decisions. They only count.

The Lamp as One Flat Machine
The Lamp as One Flat Machine010101010101IDLE0idleLIT11on, 1stLIT21on, 2ndLIT31on, 3rdDARK10dark, 1stDARK20dark, 2nd
  1. idle · IDLE0
    • ↓0 → IDLE
    • ↓1 → LIT1
  2. on, 1st · LIT11
    • ↓0 → LIT2
    • ↓1 → LIT2
  3. on, 2nd · LIT21
    • ↓0 → LIT3
    • ↓1 → LIT3
  4. on, 3rd · LIT31
    • ↓0 → DARK1
    • ↓1 → DARK1
  5. dark, 1st · DARK10
    • ↓0 → DARK2
    • ↓1 → DARK2
  6. dark, 2nd · DARK20
    • ↓0 → IDLE
    • ↓1 → IDLE
StateInputNextOutput in state
IDLE0IDLE0
IDLE1LIT10
LIT10LIT21
LIT11LIT21
LIT20LIT31
LIT21LIT31
LIT30DARK11
LIT31DARK11
DARK10DARK20
DARK11DARK20
DARK20IDLE0
DARK21IDLE0

Current state: DARK2 · Output: 0

Sampled input, state and output waveformStepState0IDLE1IDLE2LIT13LIT24LIT35DARK16DARK27IDLE8IDLE9LIT110LIT211LIT312DARK113DARK2go—0101000010000lamp00111000011100
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step012345678910111213
Input—0101000010000
StateIDLEIDLELIT1LIT2LIT3DARK1DARK2IDLEIDLELIT1LIT2LIT3DARK1DARK2
Output00111000011100

  1. Step 2. The press seen at the end of cycle 1 starts the flash. Each cycle of light is its own state.
  2. Step 5. Three lit states, then two dark ones. The press in cycle 3 changes nothing: every arc out of LIT2 goes to LIT3.
  3. Step 7. Back in IDLE after 3 + 2 cycles. A 30-cycle flash would need 30 ON states.

Same lamp, same stream as the lab. Six states, and the count grows with every cycle added to a time.

On, dark (cycles)Flat machine statesMain machine statesTimer bits
3, 2632
10, 51634
30, 205135
100, 5015137

Flat: IDLE plus one state per timed cycle. Factored: the main machine stays at 3 states; the timer needs enough bits for the longer time minus one.

A Main Machine and a Helper

Factoring splits one machine into smaller machines that run on the same clock. The main machine makes the decisions. A helper, such as a timer or a counter, does one job and reports back.

Two Machines, One ClockThe main machine sends start and len to the timer. The timer sends done back.
  • I/O
  • Control / FSM
  • Storage
  • Control
Two machines, one clockThe main machine sends start and len to the timer. The timer sends done back. io go the button control Main machine IDLE, ON, OFF storage Timer down counter t io lamp on in ON start, lendone
  1. control Main machineIDLE, ON, OFF
    • start, len → Timer
    • lamp
  2. storage Timerdown counter t
    • done → Main machine
  3. io gothe button
    • Main machine
  4. io lampon in ON
  1. Request

    On an arc into a timed state, the main machine raises start for one cycle and puts the length on len.

  2. Count

    At that edge the timer loads len - 1. Then it counts down, one per edge, to 0.

  3. Answer

    done = (t == 0). The main machine waits on a self-loop until done = 1.

Read the diagram as text
  • go: the button
  • Main machine: IDLE, ON, OFF
  • Timer: down counter t
  • lamp: on in ON
  • go → Main machine
  • Main machine → Timer: start, len
  • Timer → Main machine: done
  • Main machine → lamp

The lab's two machines. Each has its own register; both load at the same clock edge.

The Main Machine, With the Timer Outside
The Main Machine, With the Timer Outside000110110010011100100111IDLE0idleON1on: wait for doneOFF0dark: wait for done
  1. idle · IDLE0
    • ↓00 → IDLE
    • ↓01 → IDLE
    • ↓10 → ON
    • ↓11 → ON
  2. on: wait for done · ON1
    • ↓00 → ON
    • ↓10 → ON
    • ↓01 → OFF
    • ↓11 → OFF
  3. dark: wait for done · OFF0
    • ↓00 → OFF
    • ↓10 → OFF
    • ↓01 → IDLE
    • ↓11 → IDLE
StateInputNextOutput in state
IDLE00IDLE0
IDLE01IDLE0
IDLE10ON0
IDLE11ON0
ON00ON1
ON10ON1
ON01OFF1
ON11OFF1
OFF00OFF0
OFF10OFF0
OFF01IDLE0
OFF11IDLE0

Current state: OFF · Output: 0

Sampled input, state and output waveformStepState0IDLE1IDLE2ON3ON4ON5OFF6OFF7IDLE8IDLE9ON10ON11ON12OFF13OFFgo—0101000010000done—1100101110010lamp00111000011100
Scroll horizontally ↔
Sampled waveform: Moore output after each edge; Mealy output on the taken arc.
Step012345678910111213
Input—01110010010001011100000100
StateIDLEIDLEONONONOFFOFFIDLEIDLEONONONOFFOFF
Output00111000011100

  1. Step 2. Input words are go, done. In IDLE only go matters: 11 takes the arc to ON, and the timer is started on that arc.
  2. Step 5. ON waits on its self-loop while done = 0. The word 01 in cycle 4 moves it to OFF.
  3. Step 7. OFF leaves on done as well. The main machine never counts: three states, whatever the times are.

The stream is the lab's go and done, cycle by cycle. The timer that makes done is the second machine.

Getting the Handshake Right

The handshake has two rules. Start is raised on the arc that enters a timed state. The timer then loads at the same edge as the main register. Done is tested only inside the timed state.

RuleIn the labIf broken
Load length - 1len 3 loads t = 2: ON lasts 3 cyclesLoading 3 makes ON last 4 cycles
Leave on doneON leaves at the end of the cycle with t = 0Leaving at t = 1 cuts every time by one
Test done after startingdone is read in ON, after the loadIn the start cycle done still shows the old count

Each rule, and the timing bug its break causes.

Asked in interviews
  1. Why factor a state machine?

    Long waits and repeated counts make a flat machine huge: one state per cycle. A main machine with a timer or counter keeps the decisions small and lets the times change without redrawing anything.

  2. How do two state machines talk?

    Through handshake signals on the same clock. The main machine raises a request, such as start with a length; the helper answers with a status, such as done. Each signal has one driver.

  3. A timed state lasts one cycle too long. Where do you look?

    At the timer's load value and its done compare. Loading N instead of N - 1, or finishing at -1 instead of 0, adds one cycle.

Try It

Each line is read mid-cycle. start shows in the cycle before the edge that loads t.

The press in cycle 3 comes while ON. The main machine does not look at go there, so nothing happens.

Change len for ON to 3'd5 and predict how many lines show lamp=1 for the first press. Then make the timer load len instead of len - 1.

RUNIcarus Verilog · in your browser
Edit the code, then run it
Expected: cycle 0 go=0 main=IDLE start=0 t=0 done=1 lamp=0 cycle 1 go=1 main=IDLE start=1 t=0 done=1 lamp=0 cycle 2 go=0 main=ON start=0 t=2 done=0 lamp=1 cycle 3 go=1 main=ON start=0 t=1 done=0 lamp=1 cycle 4 go=0 main=ON start=1 t=0 done=1 lamp=1 cycle 5 go=0 main=OFF start=0 t=1 done=0 lamp=0 cycle 6 go=0 main=OFF start=0 t=0 done=1 lamp=0 cycle 7 go=0 main=IDLE start=0 t=0 done=1 lamp=0 cycle 8 go=1 main=IDLE start=1 t=0 done=1 lamp=0 cycle 9 go=0 main=ON start=0 t=2 done=0 lamp=1 cycle 10 go=0 main=ON start=0 t=1 done=0 lamp=1 cycle 11 go=0 main=ON start=1 t=0 done=1 lamp=1 cycle 12 go=0 main=OFF start=0 t=1 done=0 lamp=0
Read included file: tb.sv
// tb.sv: the bench (read-only). go is pressed in cycles 1, 3 and 8; one line per cycle, read mid-cycle.
module tb;
  logic clk = 0, rst = 1, go = 0, lamp;
  flash dut (.clk(clk), .rst(rst), .go(go), .lamp(lamp));
  string presses = "0101000010000";
  initial begin
    #1 clk = 1; #1 clk = 0; rst = 0;
    for (int c = 0; c < presses.len(); c++) begin
      go = (presses[c] == "1");
      #1 $display("cycle %2d go=%b main=%-4s start=%b t=%0d done=%b lamp=%b", c, go, dut.m.name(), dut.start, dut.t, dut.done, lamp);
      #1 clk = 1; #1 clk = 0;
    end
  end
endmodule

Check Yourself

ConceptA flat machine has IDLE, 20 states for one wait and 10 for another. After factoring with a timer, how many states has the main machine?
ConceptWhat does the timer send back to the main machine?
Read the waveformThis main machine leaves ON at the edge after the cycle where done = 1. How many cycles is it in ON?
A timed state and its timer
012345clkmainIDLEONOFFt032101done
Scroll horizontally ↔

One column per cycle.

Predict the outputThe lab's timer is loaded at an edge with len = 5. The program prints t in each following cycle until done. Predict the exact line.
module tb;
  logic [2:0] t, len = 3'd5;
  string s = "";
  initial begin
    t = len - 3'd1;
    s = $sformatf("%0d", t);
    while (t != 3'd0) begin
      t = t - 3'd1;
      s = {s, $sformatf("%0d", t)};
    end
    $display("%s", s);
  end
endmodule
ConceptWhich job belongs in a helper machine?

Common Mistakes

Wrong Load the timer with the length itself.

The timer then reaches 0 one cycle late. Loaded with 3, the lab lamp would stay on for 4 cycles.

Fix Load length minus one, or count up from 0 and finish at length minus one.

Wrong Test done in the same cycle the timer is started.

done still describes the previous count. The idle timer shows done = 1, so the main machine leaves at once.

Fix Start the timer on the arc into a timed state, and test done only in that state.

Wrong Let the main machine leave a timed state one cycle before done.

Every timed state is then one cycle short, and a shared timer starts its next count early.

Fix Leave at the edge that ends the cycle where done = 1, and no sooner.

Wrong Factor a machine into helpers that each make their own decisions.

Two machines that both decide where to go next can disagree. The design is then hard to follow and to test.

Fix Keep the decisions in the main machine. Helpers count or wait and report one fact back, such as done.

Remember

  • States that only count cycles can move into a timer or counter.
  • The main machine decides; a helper counts and answers with one status bit.
  • Start the helper on the arc into a timed state; load length minus one; leave on done.
  • A flat machine grows with every cycle of waiting; the factored main machine does not.

Practice

Report a problem with this page