Digital Design / Module 6: Finite state machines
37. Traffic light and vending machine
Design control logic from a real specification.
See it move
The idea
Real controllers rarely need many states, as long as you separate control from data. An FSM decides what to do next, while counters and registers hold the numbers.
Vending machine
An item costs 15, and the machine accepts coins of 5 and 10. The only history that matters is the credit so far, so three states are enough: 0, 5 and 10.
| State | Coin 5 | Coin 10 |
|---|---|---|
| Credit 0 | Credit 5 | Credit 10 |
| Credit 5 | Credit 10 | Vend, credit 0 |
| Credit 10 | Vend, credit 0 | Vend, return 5, credit 0 |
If prices or coin values grow, the state count explodes. The better design then holds the credit in a register, with a small FSM controlling it.
Traffic light
The sequence is north-south green, north-south yellow, east-west green, east-west yellow. Each phase lasts some number of cycles. Without a timer, a 60-cycle green requires 60 states. With a counter, the FSM has just four:
always_ff @(posedge clk)
if (rst) begin
state <= NS_GREEN;
timer <= GREEN - 1;
end else if (timer == 0) begin
case (state)
NS_GREEN: begin state <= NS_YELLOW; timer <= YELLOW - 1; end
NS_YELLOW: begin state <= EW_GREEN; timer <= GREEN - 1; end
EW_GREEN: begin state <= EW_YELLOW; timer <= YELLOW - 1; end
default: begin state <= NS_GREEN; timer <= GREEN - 1; end
endcase
end else
timer <= timer - 1'b1;Changing the timing now means changing a number, not redesigning the machine.
Common mistake
Missing cases that a real user would hit. What if a 10 coin is inserted during vending? What happens at the instant of reset: are both directions red? Walk through odd sequences, not just the expected one. Designs fail on the sequences their authors never imagined.
One more to try
Key ideas
- Timers pair with FSMs through a counter.
- Accumulated value can be separate data rather than extra states.
- Separating control and datapath keeps state count low.
Your exercise
Find the bug
This code has one deliberate bug. Read the symptom, then click the line you think is wrong.
The fix
else if (total >= 5'd15) begin
Why it failed
> needs more than 15, so exactly the right money doesn't vend. The correct condition is "at least the price". Boundary values are where comparison bugs hide, so always test the exact value, as well as the values either side of it.
Interview questions
coreWhen should you add a datapath counter instead of states?
When the value would multiply your states, such as a timer's count.
basicA traffic light has a 60-cycle green and a 5-cycle yellow for each direction. How many states does it need without a timer, and how many with one?
Without a timer, each waiting cycle needs its own state: 2 x (60 + 5) = 130 states. With a separate down-counter, the FSM needs only the four phases: NS green, NS yellow, EW green, EW yellow. The counter must hold values up to 59, which needs 6 bits. Changing the timing then means changing a number, not redesigning the machine.
basicA vending machine sells a 15-unit item and takes coins of 5 and 10. Why are three states enough?
The only history that matters is the credit so far, and before a sale it can only be 0, 5 or 10. Reaching 15 or more triggers a vend and returns to credit 0, with 5 back as change if the credit reached 20. Which coins made up the credit doesn't affect what happens next, so it doesn't need its own state.
coreA phase controller loads its timer with GREEN and counts down, changing phase when the timer reaches 0. The green phase comes out one cycle too long. Why?
NS_GREEN: begin state <= NS_YELLOW; timer <= YELLOW; end NS_YELLOW: begin state <= EW_GREEN; timer <= GREEN; end // timer counts down; phase changes when timer == 0
The phase includes the cycle in which the timer equals 0, so loading N gives N + 1 cycles: N, N-1, ..., 0. Loading GREEN - 1 gives exactly GREEN cycles. In simulation with GREEN = 5 and YELLOW = 2, loading the full value gave phases of 6 and 3 cycles, and loading value minus one gave 5 and 2. Off-by-one errors like this are typical of counters paired with FSMs, so check a boundary value in simulation.
coreIf the vending item cost 40 instead of 15, with the same 5 and 10 coins, how many credit states would a pure FSM need? What is the better design?
Before a sale, the credit can be 0, 5, 10, ... 35, which is 8 states, and the table of transitions grows with every price or coin change. The better design holds the credit in a small register, adds each coin to it, and compares it with a PRICE parameter. The control logic then stays tiny, and a price change is a parameter change.
coreShould the traffic light outputs (the lamp drives) be Moore or Mealy outputs? Why?
Moore, decoded from the state or taken from registers. Lamp outputs should change only on clock edges and should not glitch when inputs, such as a sensor, change mid-cycle. A Mealy output reacts to inputs combinationally and could flicker or briefly show a wrong combination. A wrong combination of lights is exactly what this controller must never show.
coreThe traffic controller's reset puts it straight into north-south green. What would a careful reviewer ask about this?
They would ask what the lights must show at reset, and while reset is held, since a controller may restart while cars are moving. Many specifications want both directions red for a clearance period before any green. That can be an extra ALL_RED state as the reset target. The point is to walk through unusual moments such as reset, not just the normal cycle, because that is where real controllers fail.
advancedA pedestrian button gives a one-cycle pulse at any time, and the controller should serve it at the end of the current green. How do you make sure the request is never lost?
Capture the pulse in a sticky request flop: set it when the pulse arrives, and clear it only when the FSM actually serves the request. The FSM then reads the held flag at the phase change, whatever state it was in when the pulse came. If the FSM sampled the raw pulse directly, a pulse arriving during the wrong phase would be gone for good. If set and clear can happen in the same cycle, define which one wins.
advancedThis register-based vending logic loses money in one case. Find it.
always @(posedge clk) if (rst) credit <= 0; else if (credit >= 15) credit <= credit - 15; // vend else if (coin5) credit <= credit + 5; else if (coin10) credit <= credit + 10; assign item = (credit >= 15);
When credit is 15 or more, the vend branch takes priority and ignores the coin inputs, so a coin inserted in the vend cycle is never added. In simulation, paying 10, 5, 10, 5 (30 in total) gave only one vend with 5 credit left, because the second 10 arrived in the vend cycle. The fix is to subtract the price and add the coin in the same update, for example credit <= credit - 15 + coin_value. Also decide what happens if both coin inputs are high together, since this code silently counts only the 5.