Can a circuit change its behavior over time?
“How can a physical circuit of gates and registers follow an orderly sequence of events?”
In Section 4, we learned how flip-flops hold onto bits. But holding static data is only half the story. Real digital systems—from traffic lights to CPU instruction pipelines—must step through complex sequences, react to changing inputs, and evolve their behavior over time. In this section, we will combine combinational logic with memory registers to build the ultimate digital controller: The Finite State Machine (FSM).
What should happen first?
Consider an intersection traffic light. It cannot behave randomly or turn green and red at the same instant. It must follow a strict, predetermined sequence of events.
How does a traffic light follow a sequence?
When the system powers on, it starts in a safe default state: RED (Stop).
After the red phase finishes, what should happen next? The light turns GREEN (Go).
After green? It turns YELLOW (Prepare to stop).
And after yellow? It cycles back to RED.
Why is establishing this strict sequence the first step in circuit design?
Before we write boolean equations or place transistors, we must clearly define the order of operations. This operational order defines the State Transition Sequence of our digital machine.
5.1 What Should Happen First? Establishing State Sequences
A traffic light controller is the canonical real-world example of sequential logic. It cannot behave randomly: it must progress through a strictly defined sequence of events where each step leads inevitably to the next.
What does the circuit need to remember?
To make the sequence work, the circuit must retain information about where it currently is in the cycle.
What is a “State”?
A State is a distinct, uniquely identifiable condition that the circuit holds in its physical memory. For our traffic light, the system has three primary states: RED, GREEN, and YELLOW, plus an optional EMERGENCY state.
How do we accurately represent each state in hardware?
Semiconductor flip-flops only store 0s and 1s. We assign each human-readable state a distinct binary pattern:
• Binary Encoding: 4 states require 2 D Flip-Flops (00₂ = RED, 01₂ = GREEN, 10₂ = YELLOW, 11₂ = EMERGENCY).
• One-Hot Encoding: 4 states use 4 flip-flops where exactly one bit is 1 at any time (0001₂, 0010₂, 0100₂, 1000₂).
5.2 What Does the Circuit Remember? Defining & Encoding States
Silicon transistors do not know what 'RED' or 'GREEN' means. Hardware memory maps distinct operational situations to unique binary patterns stored inside D Flip-Flop registers.
| State | Binary Code | One-Hot Code |
|---|---|---|
| RED | 00₂ | 1000₂ |
| GREEN | 01₂ | 0100₂ |
| YELLOW | 10₂ | 0010₂ |
| EMERGENCY | 11₂ | 0001₂ |
What causes a state change?
Once states are defined, we must determine what forces the circuit to transition from its current state to the next state.
The Four Primary Transition Triggers
In real digital designs, state changes are driven by four distinct factors:
1. System Clock: The global periodic heartbeat that synchronizes state sampling.
2. Internal Timers: Countdown counters that hold a state for a fixed duration (e.g. 30s Red, 40s Green).
3. External Inputs: Asynchronous events from the real world (e.g. a pedestrian pressing a crossing button).
4. Emergency Overrides: High-priority sensor lines (e.g. emergency vehicle siren detection).
How do asynchronous inputs integrate cleanly?
When a pedestrian presses a push-button at an arbitrary instant, the signal is captured into a synchronizing flip-flop on the next clock rising edge (↑), preventing glitches from propagating into the state register.
5.3 What Causes a State Change? Clocks, Timers & External Inputs
State transitions do not happen spontaneously. They are triggered by a combination of internal system clock ticks, duration timers, and external asynchronous sensor events (pedestrian buttons or emergency sirens).
How do we describe all possible behavior?
To build complex controllers without bugs or missing edge cases, engineers use two formal representations: the State Diagram and the State Transition Table.
The Three Core FSM Mapping Questions
For every possible scenario, the state machine answers:
• Current State (Q): Where are we right now?
• Next State (Q'): Based on inputs (X), where should we go on the next clock tick?
• Active Outputs (Y): What control signals should be produced?
Moore vs Mealy Output Architecture
• Moore Machine (Output = f(State)): Outputs depend exclusively on the current state register bits. Outputs are perfectly synchronized to the clock and immune to input glitches.
• Mealy Machine (Output = f(State, Input)): Outputs depend on both the current state and raw input lines. Mealy outputs react immediately within the current clock cycle, but can glitch if inputs fluctuate.
5.4 Describing Behavior: State Diagrams, Tables & Moore vs Mealy
A state machine can be completely described by a visual State Diagram and a State Transition Table. The way outputs are generated separates FSMs into Moore machines (State only) and Mealy machines (State + Input).
| State (Q) | Input (X) | Next State (Q') | Output (Y) |
|---|---|---|---|
| S0 (RED) | 0 | S1 (GREEN) | RED=1 |
| S0 (RED) | 1 | S1 (GREEN) | RED=1 |
| S1 (GREEN) | 0 | S2 (YELLOW) | GRN=1 |
| S1 (GREEN) | 1 | S2 (YELLOW) | GRN=1, PB=1 |
| S2 (YELLOW) | 0 | S0 (RED) | YEL=1 |
| S2 (YELLOW) | 1 | S0 (RED) | YEL=1 |
How do we build it in hardware?
Translating our abstract state bubbles and transition tables into silicon requires three hardware components working together in a closed loop.
The Three Hardware Pillars of an FSM
1. State Register (Memory): A bank of D Flip-Flops that holds the present state bits (Q).
2. Next-State Logic (Combinational): A network of AND, OR, and Inverter gates that calculates the next state bits (D_next) from the current state (Q) and external inputs (X).
3. Output Logic (Combinational): Decoders that convert the present state bits into physical drive signals (e.g. lighting the red, yellow, or green LEDs).
4. Feedback Loop: Wires physically routing the register outputs (Q) back into the input terminals of the next-state logic.
Connecting Sections 2, 3, 4, and 5
Notice what has just happened: An FSM is not mysterious new hardware. It is simply Combinational Logic (Section 3) + Flip-Flop Memory (Section 4) wired into a feedback loop to create Behavior Over Time!
5.5 Building the FSM in Hardware: Registers & Next-State Logic
A Finite State Machine in silicon is constructed from three fundamental blocks: 1) A State Register (D Flip-Flops), 2) Next-State Combinational Logic (deciding next bits), and 3) Output Logic (driving output lines).
Decodes current state bits (Q₁, Q₀) to calculate next inputs (D₁, D₀).
Samples D on clock rising edge (↑), holding current state Q.
Converts current state bits (Q₁, Q₀) into physical control signals.
The Journey: From Real-World Sequences to Silicon State Machines
Defining the strict real-world sequence of events (RED → GREEN → YELLOW).
Mapping situations to binary bit patterns stored in D Flip-Flop registers.
Capturing all transitions and distinguishing Moore vs Mealy output models.
Next-state combinational gates feeding clock-driven state registers in a feedback loop.
If we can build a state machine...
how do we design a complete digital computer?
Understanding a single Finite State Machine is just the beginning.
What happens when we take a master Control Unit FSM, and connect it to a Register File, an ALU Datapath, and a Memory Interface?
All of these building blocks come together to form the ultimate computational architecture: A Complete Digital Machine (Microprocessor).