Digital Design / Module 6: Finite state machines
32. States, transitions and outputs
Translate behaviour into a state diagram.
See it move
The idea
A finite state machine is a design that remembers where it is in a process, and decides what to do next. Protocol controllers, bus interfaces and CPU control units are all FSMs.
It has three parts:
- A state register: flops holding the current state.
- Next-state logic: combinational logic using the state and the inputs.
- Output logic: combinational logic producing the outputs.
How to choose the states
Ask what the machine must remember in order to decide its future. A state should hold exactly that history and nothing more. Two situations that behave identically for all future inputs can share a state.
From description to diagram
For a door controller:
- List the situations: closed, opening, open, closing.
- For each state, consider every input. What if "open" is pressed during closing?
- Decide the output in each state.
- Choose the reset state. Closed is the safe choice here.
The design discipline
Check every state against every input. The missed combination, not the main path, is where most FSM bugs live. Ask "what happens if this arrives now?" for each one. The animation above lets you press the buttons in any order and see each transition.
Safe behaviour
Reset should lead to a harmless state: motors off, doors shut, outputs inactive. If a state could lead to physical danger or corrupted data, design a way out.
Common mistake
Creating a state for every value of something that is really a number. If the machine waits 100 cycles, that shouldn't be 100 states. Use one wait state plus a counter. This idea, separating control from data, appears in the Traffic light lesson.
Key ideas
- List what must be remembered: that is your state set.
- Every state defines every input's transition.
- Define safe reset and unused-state behaviour.
Your exercise
Interview questions
coreWhat belongs in a state?
Exactly the history that future behaviour depends on.
basicWhat are the three parts of a finite state machine in hardware?
A state register, which is a set of flops holding the current state. Next-state logic, which is combinational logic using the current state and inputs to decide the next state. Output logic, which is combinational logic that produces the outputs from the state, and in some machines also from the inputs.
basicHow do you choose the reset state of a state machine that controls something physical, such as a motor?
Choose a state where every output is harmless: motor off, door closed, nothing being driven or written. The reset state is where the machine lands after power-up or any recovery, so it must be safe regardless of what happened before. Then make sure every path out of it is deliberate.
coreA door controller has states CLOSED, OPENING, OPEN and CLOSING, and buttons for open and close. Which question must you answer for every state, and what is a sensible answer for open being pressed while CLOSING?
For every state, decide what happens for every input combination, including staying put and both buttons at once. Most FSM bugs live in the combinations left out. For open pressed during CLOSING, a sensible answer is to go back to OPENING, so the door never closes on someone who asked for it to open.
coreA controller must wait 100 cycles between two actions. Someone draws 100 wait states. Does a counter save flops, and why is it still the better design?
Not much: 100 binary-coded states need 7 flops, and a counter for 0 to 99 also needs 7 bits, plus a small state register. The real gain is in the logic and clarity: one WAIT state plus a counter has a few simple transitions, while 100 states need 100 near-identical transitions. Changing the delay is then just a constant. Keep data, such as a count, in a datapath, and let the FSM handle control.
coreWhen can two states of an FSM be merged into one?
When they give the same outputs and, for every input, go to states that are themselves equivalent. Then no future input sequence can tell them apart, so the machine does not need to remember which one it is in. A state should hold exactly the history that future behaviour depends on.
coreIn this next-state logic, both buttons are pressed at once in the CLOSED state. Which state does the machine go to, and why is this code risky?
always @(*) begin next = state; if (open_btn) next = OPENING; if (close_btn) next = CLOSING; end
It goes to CLOSING. Both if statements run, and in a combinational block the last assignment to next wins, so close silently has priority over open. That may be what is wanted, but it is hidden in the order of two independent if statements. Write the priority explicitly with if-else, or handle the both-pressed case on purpose.
advancedDesign the control for a serial transmitter that sends a start bit, 8 data bits and a stop bit. How would you structure the states?
Use states such as IDLE, START, DATA and STOP, with a 3-bit counter that counts the 8 data bits while in DATA. The alternative of one state per bit needs 11 states with almost identical logic. A baud-rate tick from a separate counter acts as the enable that moves the machine from bit to bit, and the shift register holding the data shifts on the same tick.
advancedA one-hot state machine takes an unsynchronised input straight into its next-state logic. Occasionally it ends up with two hot bits or none. How can that happen?
Each state flop has its own next-state logic, and the input reaches each one through a different path delay. If the input changes close to the clock edge, one flop may see the new value and another the old one, so the machine leaves one state but does not, or does twice, enter the next. The fix is to synchronise the input to the FSM's clock first, so every flop sees the same stable value.