Finite State Machines
How hardware makes decisions that depend on history: states, transitions, and outputs.
Problem
A combinational circuit's output depends only on current inputs. But many tasks need history: "output 1 only after seeing input sequence 1-0-1." How does hardware track where it is in a process?
How it works
An FSM has a finite set of states, stored in flip-flops. On each clock edge, the machine reads its current state and inputs, computes the next state and outputs via combinational logic, and transitions.
Moore vs Mealy:
• Moore: outputs depend only on the current state. Outputs change one cycle after the input that caused the transition. Simpler, more predictable timing.
• Mealy: outputs depend on current state AND current inputs. Can respond in the same cycle as the input. Often needs fewer states than Moore, but outputs can glitch if inputs change asynchronously.
State encoding:
• Binary: uses ⌈log2(N)⌉ flip-flops for N states. Compact, but next-state logic can be complex.
• One-hot: one flip-flop per state, exactly one is high at a time. Uses more flip-flops but next-state logic is simpler and faster: preferred in FPGAs where flip-flops are abundant.
In practice: FSMs are everywhere in hardware. A traffic light controller, a UART receiver, a cache controller, a CPU's control unit, a matching engine's order processing pipeline: all are FSMs. The implementation is always: flip-flops for state + combinational logic for transitions and outputs.
Moore vs Mealy:
• Moore: outputs depend only on the current state. Outputs change one cycle after the input that caused the transition. Simpler, more predictable timing.
• Mealy: outputs depend on current state AND current inputs. Can respond in the same cycle as the input. Often needs fewer states than Moore, but outputs can glitch if inputs change asynchronously.
State encoding:
• Binary: uses ⌈log2(N)⌉ flip-flops for N states. Compact, but next-state logic can be complex.
• One-hot: one flip-flop per state, exactly one is high at a time. Uses more flip-flops but next-state logic is simpler and faster: preferred in FPGAs where flip-flops are abundant.
In practice: FSMs are everywhere in hardware. A traffic light controller, a UART receiver, a cache controller, a CPU's control unit, a matching engine's order processing pipeline: all are FSMs. The implementation is always: flip-flops for state + combinational logic for transitions and outputs.
Key insightAn FSM is the hardware equivalent of a state machine diagram. Flip-flops store "where am I?", combinational logic answers "given where I am and what I see, where do I go next?" Every sequential circuit, from a simple counter to a CPU, is an FSM.