Finite State Machines (FSM)
Finite state machines: Moore versus Mealy, state diagrams and tables, and how to design one step by step.
What Is an FSM? A Finite State Machine is a mathematical model of computation with a finite number of states. At any clock edge, the machine transitions from its current state to a next state based on inputs, and may produce outputs. FSMs are the backbone of all digital control logic - traffic lights, UART controllers, protocol handlers, CPU control units.
Moore vs Mealy - The Two FSM Models
| Property | Moore FSM | Mealy FSM |
|---|---|---|
| Output depends on | Current state only | Current state AND current inputs |
| Output timing | Registered - changes only at clock edge | Combinational - can change immediately when input changes |
| Output glitches | No (registered outputs) | Possible if inputs glitch |
| Number of states | Typically more states needed | Typically fewer states (more compact) |
| Where used | When output stability is critical; safe outputs | When response must be immediate; fewer states needed |
| Verilog style | 3-block style: next-state, state reg, output logic | 2-block style: combined next-state & output, state reg |
FSM Design Procedure
Step 1: State Diagram
Draw circles for each state. Label transitions between states with input conditions. Label outputs (inside circle for Moore, on arrow for Mealy).
Step 2: State Table
Convert the diagram to a table: Current State | Input | Next State | Output. This is a formal specification of all transitions.
Step 3: State Encoding
Assign binary codes to states. Binary encoding (log₂N bits), One-hot encoding (N bits, one FF per state), Gray encoding. One-hot is common in FPGAs.
Step 4: Derive Equations
Use K-maps or Boolean algebra to derive next-state and output equations from the state table. Then implement with flip-flops and combinational logic.
Sequence Detector Example - Detect "1011"
Design a Moore FSM that detects the sequence 1011 in a serial bit stream. Output = 1 when the sequence is detected (overlapping detection allowed).
| State | Meaning | Input=0 → Next | Input=1 → Next | Output |
|---|---|---|---|---|
| S0 | Initial / Reset | S0 | S1 | 0 |
| S1 | Got "1" | S2 | S1 | 0 |
| S2 | Got "10" | S0 | S3 | 0 |
| S3 | Got "101" | S2 | S4 | 0 |
| S4 | Got "1011" | S2 | S1 | 1 |
In state S1 (just received a '1'), if another '1' arrives we stay in S1 (the new '1' could start another sequence). If a '0' arrives, we go to S2 (got "10"). In S4, output=1 signals detection. If '0' arrives in S4, we go to S2 because "10" is a valid prefix - this handles overlapping sequences like "10111011".
Finished reading?
Mark it complete to track your progress through the path.
Go further
New to VLSI? Get the 6-month fresher roadmap and a 16-week study plan.
Get new lessons by email
New lessons, interview prep and real EDA tool workflows. No spam.