A finite state machine is a model that describes a system through states and transitions triggered by its inputs.
We have seen individual components: logic gates that make instantaneous decisions and Flip-Flops that remember data. We have built counters that advance linearly (1, 2, 3…).
But, how do we create a system that thinks? How do we design a controller for an elevator, a vending machine, or a communication protocol? It is not a linear sequence; it depends on what the user does.
For this, we need the most powerful concept in digital design: the Finite State Machine or FSM.
Today we will cover the necessary theory to model digital controllers before translating them into hardware.
What is an FSM?
An FSM is a mathematical model of computation. It sounds complex, but it is very intuitive. It is based on the idea that a system can only be in one of a series of predefined modes or “states” at any given moment.
Imagine a Subway Turnstile:
- Initial State: Locked.
- Event: You insert a coin.
- Transition: The turnstile moves to the Unlocked state.
- Event: You push the barrier.
- Transition: The turnstile returns to the Locked state.
If you push while it is locked, nothing happens (it remains in the same state).
Components of an FSM
To define any machine, we need to identify:
- States: The “situations” the system can be in (e.g., Idle, Reading, Writing, Error). Physically, this is stored in a register.
- Inputs: The external signals that cause changes (e.g., Button pressed, Sensor activated, Timer expired).
- Transitions: The logic that decides: “If I am in State A and receive Input X, I move to State B.”
- Outputs: What the system does at each moment (e.g., Turn on motor, turn off LED).
Visual Representation: The State Diagram
Before writing a single line of Verilog, it is advisable to draw the behavior. We use circles for states and arrows for transitions. Each arrow has the condition that triggers it written on it.
This diagram is the map we will later translate directly into case code.
Moore and Mealy
When designing how the outputs of our machine behave, there are two classic architectures. Understanding the difference is important because it affects the speed and stability of your FPGA.
Moore Machine
In a Moore Machine, the outputs depend only on the Current State.
- It doesn’t matter what is happening on the inputs right now; if the machine is in the “ALARM” state, the siren sounds.
- Behavior: The output logic depends only on the state. If that state is registered, changes occur after a clock edge.
- Advantages: It is easy to reason about and reduces direct dependence on asynchronous inputs. If you need glitch-free outputs, you can also register them.
- Disadvantages: It reacts with a one clock cycle delay relative to the input.
Mealy Machine
In a Mealy Machine, the outputs depend on the Current State AND the Inputs.
- Imagine you are in the “WAIT” state. In Moore, the output would be 0. In Mealy, you can say: “I am in WAIT, but while you press the button, the output is 1”.
- Behavior: The output can change in the middle of a clock cycle if the input changes.
- Advantages: Immediate reaction (in the same cycle). Typically requires fewer states.
- Disadvantages: A noisy input or a poorly timed combinational path can reflect on the output. Requires more attention to synchronization and glitches.
Comparison between Moore and Mealy
| Characteristic | Moore | Mealy |
|---|---|---|
| Output Dependency | State Only | State + Inputs |
| Output Change | On clock edge | Immediate (Asynchronous) |
| Glitches | Less dependent on inputs; not impossible | Higher risk in combinational outputs |
| Reaction Speed | Slow (+1 cycle) | Fast (Combinational) |
| Complexity | Usually requires more states | Usually requires fewer states |
If you are just starting out, Moore is usually easier to debug.
Mealy remains a correct choice when you need an immediate combinational response and have good control over inputs and timing.
State Encoding
Physically, states are stored in Flip-Flops. But how do we store “IDLE” or “RUN” in bits? We have to assign a binary code to each state.
Several strategies exist, but two stand out for FPGAs:
- State 0:
00 - State 1:
01 - State 2:
10
Uses few Flip-Flops, but more combinational logic for decoding.
- State 0:
0001 - State 1:
0010 - State 2:
0100 - State 3:
1000
Uses more flip-flops and can simplify decoding. The resulting area, frequency, and power consumption depend on the device and the specific machine.
Generally, we will let the synthesizer choose the encoding. If timing or area are critical, we will compare the synthesis results before forcing a strategy.
