A finite state machine (FSM) is a computational model that describes a system as a fixed set of discrete states, a set of inputs, and defined rules (transitions) for moving between those states. At any moment, the system occupies exactly one state; inputs or events trigger transitions, and outputs are produced either as a function of the current state alone (Moore type) or of the current state and current inputs (Mealy type).
In practice
FSMs appear constantly in embedded firmware: parsing serial protocols (UART framing, Modbus, USB descriptors), debouncing buttons, managing power states, sequencing motor control steps, and driving menu-driven UIs. Even simple tasks like detecting a start byte followed by a payload followed by a checksum are cleanly expressed as a state diagram and then coded directly. The structure makes control flow explicit and auditable in a way that deeply nested if/else logic does not.
In C, FSMs are commonly implemented as an enum for the state variable combined with a switch statement, or as a table of function pointers indexed by state (and optionally input). Table-driven FSMs are faster to extend and easier to unit-test because each transition is a data entry rather than a code change. For more complex machines with many orthogonal behaviors, a hierarchical state machine (HSM) — as described by Miro Samek's Quantum Platform framework — adds nested states and entry/exit actions without exploding the transition count.
On FPGAs and CPLDs, FSMs are a primary design primitive. Logic synthesis tools recognize FSM coding styles (one-hot, binary, gray-code encoding) and can optimize them automatically. The choice of state encoding directly affects timing closure and resource usage on a given device, which is not usually a concern on MCUs but becomes significant when implementing an FSM in programmable logic. The EmbeddedRelated post "State Machine 'v' Micro in a FPGA" discusses the trade-offs between implementing a pure FSM versus a small soft-core microcontroller when logic resources are constrained.
A common pitfall is letting the state variable grow to cover combinations of conditions that should instead be separate orthogonal state machines running concurrently. A large, flat FSM with dozens of states is hard to verify and often hides implicit states in auxiliary flags. Splitting behavior into multiple cooperating FSMs, each with a small state count, tends to produce more reliable and maintainable code. Another pitfall is failing to define transitions for every (state, input) combination, leaving the machine in an undefined state on unexpected inputs — defensive designs add an explicit error or reset state reachable from anywhere.
Learn this in FPGA Fundamentals
Discussed on FPGARelated
Frequently asked
What is the practical difference between a Moore FSM and a Mealy FSM in firmware?
In a Moore machine, outputs depend only on the current state, so they are stable for the entire time the machine remains in that state. In a Mealy machine, outputs also depend on the current inputs, which can produce faster reactions (output changes within the same clock cycle or event loop iteration as the triggering input) but can make timing analysis harder on synchronous digital designs. In
FPGA RTL, the distinction affects registered vs.
combinatorial output paths. In software-only firmware, the difference is mostly organizational: Moore machines are slightly easier to reason about because each state has a well-defined output regardless of how it was entered.
Should I implement an FSM with a switch statement or a transition table?
Both work; the choice is mostly about maintainability at scale. A switch statement is readable for small machines (fewer than roughly 10 states) and is zero overhead on any compiler. A function-pointer table or a 2D array of (next-state, action) pairs scales better when the number of states or inputs is large, because adding a new input means adding a column to the table rather than editing every case block. Table-driven FSMs are also easier to generate from a state-diagram tool. The downside is slightly more indirection and a larger read-only data footprint, which matters on very constrained 8-bit devices.
How does a hierarchical state machine (HSM) differ from a flat FSM?
An HSM allows states to be nested: a child state inherits transitions defined on its parent, so common behavior does not have to be duplicated across every sibling state. Entry and exit actions fire in a well-defined order as the machine moves through the hierarchy. This is the basis of UML statecharts and frameworks like Quantum Leaps QP. Flat FSMs become unwieldy as state count grows because every shared transition must be repeated. HSMs trade that duplication for a more complex execution model, which requires a disciplined framework or careful manual implementation to get right.
Can FSMs be used for communication protocol parsing, and what does that look like?
Yes, protocol parsing is one of the most common FSM applications in embedded work. A typical UART framing parser might have states like IDLE, GOT_START_BYTE, ACCUMULATING_PAYLOAD, and VERIFYING_CHECKSUM. Each incoming byte is an input event that drives a transition. This structure handles partial packets naturally (the state persists across calls) and makes error recovery explicit (a bad checksum transitions to a known error or flush state rather than leaving local variables in an ambiguous condition).
What is a microprogrammed state machine and when is it worth the complexity?
A microprogrammed state machine replaces the hardwired next-state logic with a small program stored in ROM or RAM, where each microinstruction encodes the current outputs, the next address, and branch conditions. This makes adding or changing behavior a data edit rather than a logic redesign, at the cost of a sequencer that fetches and decodes those microinstructions. On FPGAs with limited
flip-flop resources, this approach can implement complex control logic in a fraction of the
LUTs a fully hardwired FSM would require. The EmbeddedRelated posts 'Use a Simple Microprogram Controller (MPC) to Speed Development of Complex Microprogrammed State Machines' and 'Use Microprogramming to Save Resources and Increase Functionality' cover this technique in detail.
Differentiators vs similar concepts
FSM (finite state machine) vs. HSM (hierarchical state machine): a flat FSM has no nesting; every state is a peer. An HSM allows states to contain sub-states, enabling inherited transitions and shared entry/exit behavior. UML statecharts are a notation for HSMs. Moore vs. Mealy: both are FSM variants. Moore outputs depend only on current state; Mealy outputs depend on current state AND current inputs. Mealy machines can react one step faster but produce
combinatorial outputs that complicate synchronous digital design. FSM vs. microprogrammed sequencer: a microprogrammed state machine stores its next-state and output logic in a ROM/RAM table fetched by a small sequencer, making it reconfigurable without rewiring logic. A hardwired FSM encodes that logic directly in gates or software conditionals.
