Finite State Machines
Designing digital behavior
How does a traffic light know when to change? How does a UART receiver know it's in the middle of a byte? How does an SPI controller sequence clock edges and data sampling? The answer is always the same: a finite state machine.
FSMs are the backbone of digital control logic. Any circuit that follows a defined sequence of steps uses one.
Traffic Light Controller
Step through the FSM. Each state has a timer, and when it expires, the machine transitions to the next state:
What Is a Finite State Machine?
An FSM has a fixed number of states (that's the "finite" part). At any moment, the machine is in exactly one state. On each clock cycle, it checks its inputs and a set of rules called transitions to decide whether to stay in the current state or move to a different one.
Our traffic light has three states: RED (5 cycles), GREEN (4 cycles), and YELLOW (2 cycles). Each state has a timer. When the timer reaches zero, the machine transitions to the next state.
Moore vs Mealy
In a Moore machine, the outputs depend only on the current state. Our traffic light is Moore: the light color is determined entirely by which state we're in. Outputs change only on state transitions.
In a Mealy machine, outputs depend on both the current state and the current inputs. A Mealy machine can react faster (within the same cycle) but is more complex and can produce glitchy outputs if inputs change asynchronously.
Why This Matters for FPGA Design
- Communication protocols - UART, SPI, I2C controllers are all FSMs
- Bus interfaces - AXI, Wishbone, and other bus protocols use FSMs for handshaking
- Command decoders - parsing packets, interpreting instructions
- Sequencers - initialization sequences, calibration routines, power-up state machines
Frequently Asked Questions
What is a finite state machine?
A finite state machine (FSM) is a circuit that moves between a fixed number of states based on inputs and the current state. At any moment, the FSM is in exactly one state. On each clock cycle, it checks its inputs and decides whether to stay in the current state or transition to a different one. FSMs are used to implement control logic, communication protocols, sequencers, and any circuit that needs to follow a defined sequence of steps.
What is the difference between Mealy and Moore state machines?
In a Moore machine, outputs depend only on the current state, so they change only when the state changes. In a Mealy machine, outputs depend on both the current state and the current inputs, so they can change mid-state if inputs change. Moore machines are simpler and glitch-free but may need more states. Mealy machines can respond faster (one clock cycle earlier) but outputs can glitch if inputs are asynchronous.
Quick Check
Test your understanding of the key concepts from this lesson.
