Finite State Machines (FSMs)

Core Idea

A finite state machine (FSM) is a model of a sequential system with a finite number of discrete states. At each clock edge, the system transitions to a next state determined by the current state and the inputs (next-state logic). Outputs are produced either as a function of the current state only (Moore machine) or of both state and inputs (Mealy machine). FSMs are implemented in hardware using flip-flops to hold state and combinational logic for the transition and output functions, and they model everything from traffic lights to CPU control units.

How It's Best Learned

Design FSMs for simple problems like a sequence detector or vending machine controller. Draw the state diagram, derive the state transition table, assign binary encodings, and implement with flip-flops and combinational logic. Verify with timing diagrams.

Common Misconceptions

• Moore and Mealy machines are equally expressive; a Moore FSM can be converted to a Mealy FSM with fewer states, and vice versa.
• State encoding (one-hot vs. binary) is an implementation choice that affects logic complexity and speed but does not change the FSM's behavior.

Explainer

A combinational circuit computes a pure function of its current inputs — it has no memory of what happened before. This is powerful but limiting. Real-world controllers — traffic lights, elevator controllers, CPU control units — need to remember where they are in a sequence. That is exactly what a finite state machine adds: a finite set of discrete states that summarize all the history the system needs.

An FSM is defined by five elements: a set of states, an input alphabet, a transition function (current state + input → next state), an output function, and an initial state. The state diagram is the most intuitive representation: circles are states, arrows are transitions labeled with inputs (and sometimes outputs). When you design an FSM for a problem, you start with the state diagram — drawing out every situation the system needs to distinguish — before thinking about gates.

The two classic variants differ in where outputs are placed. In a Moore machine, each state has a fixed output label; the output depends only on the current state. In a Mealy machine, outputs are labels on transitions; the output depends on both the current state and the current input. Moore machines are easier to reason about and produce glitch-free outputs (since outputs only change at clock edges when state changes). Mealy machines typically require fewer states to achieve the same behavior because a single state can emit different outputs depending on the input. Both models are equally powerful — you can always convert one to the other.

Hardware implementation connects directly to your combinational circuit design knowledge. The FSM has two parts: (1) next-state logic — a combinational circuit that takes the current state bits and inputs and computes what state to move to; and (2) output logic — another combinational circuit (or a direct wiring for Moore outputs) that produces the outputs. The current state is held in a register of flip-flops, one per state bit. At every rising clock edge, the flip-flops capture the next-state logic's output and the system advances to the new state.

When implementing, you must also choose a state encoding — how to represent each state as a binary number stored in the flip-flops. Binary encoding uses the minimum number of flip-flops (⌈log₂ n⌉ for n states), while one-hot encoding uses one flip-flip per state (exactly one flip-flop is 1 at all times). Binary encoding is more compact; one-hot encoding produces simpler next-state logic because checking "are we in state X?" is just reading a single flip-flop. The choice affects the complexity of your combinational logic but not the FSM's observable behavior.