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.
- Cycle 1
go = 1 in IDLE. The main machine raises start with len = 3 for the edge that enters ON.
- Cycle 2
The timer loaded 3 - 1 = 2 at that edge. done is 0 while it counts down.
- Cycle 4
t = 0: done = 1 in the third ON cycle. The main machine moves to OFF and starts a 2-cycle count.
- 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.
| On, dark (cycles) | Flat machine states | Main machine states | Timer bits |
|---|---|---|---|
| 3, 2 | 6 | 3 | 2 |
| 10, 5 | 16 | 3 | 4 |
| 30, 20 | 51 | 3 | 5 |
| 100, 50 | 151 | 3 | 7 |
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.
- I/O
- Control / FSM
- Storage
- Control
- Request
On an arc into a timed state, the main machine raises start for one cycle and puts the length on len.
- Count
At that edge the timer loads len - 1. Then it counts down, one per edge, to 0.
- 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.
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.
| Rule | In the lab | If broken |
|---|---|---|
| Load length - 1 | len 3 loads t = 2: ON lasts 3 cycles | Loading 3 makes ON last 4 cycles |
| Leave on done | ON leaves at the end of the cycle with t = 0 | Leaving at t = 1 cuts every time by one |
| Test done after starting | done is read in ON, after the load | In the start cycle done still shows the old count |
Each rule, and the timing bug its break causes.
Asked in interviews
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.
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.
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.
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=0Read 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
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.