Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

From state diagrams to hardware implementation

Prerequisites

This tutorial assumes you have completed:

You should also be familiar with:

  • Binary numbers and basic Boolean algebra (AND, OR, NOT)

  • Logic gates and how to combine them into circuits

What is a Finite State Machine?

Finite State Machines (FSMs) are fundamental building blocks in digital design. They model systems that can be in one of a finite number of states, transitioning between states based on inputs.

An FSM consists of:

  • States: A finite set of conditions the system can be in

  • Inputs: External signals that influence state transitions

  • Outputs: Signals produced by the machine

  • Transitions: Rules for moving between states based on inputs

  • Initial State: The starting state when the system powers on

Think of a traffic light: it cycles through states (Red → Green → Yellow → Red), with timing inputs controlling transitions and the light color as output.

State Diagrams: Visualizing FSMs

State diagrams use circles for states and arrows for transitions. Let’s visualize a simple two-state FSM that toggles between ON and OFF based on a button press.

This is a Moore machine — the output (LED on/off) depends only on the current state.

Color convention: Green = output HIGH (LED on), Grey = output LOW (LED off)

Loading...

This FSM has:

  • 2 states: OFF, ON

  • 1 input: button (0 or 1)

  • 1 output: LED (0=off, 1=on) — determined by the current state

    • State OFF → LED = 0

    • State ON → LED = 1

  • Transitions: Toggle state when button=1, stay in current state when button=0

  • Initial state: OFF (indicated by the incoming arrow with no source state)

Understanding transitions:

  • button=1 means: “the button signal was HIGH when sampled at the clock edge”

  • button=0 means: “the button signal was LOW when sampled at the clock edge”

  • State changes occur synchronously on the rising clock edge

Note: This is a Moore machine because the output depends only on which state we’re in, not on the input value.

State Table

State diagrams are visual, but state tables provide a complete, unambiguous specification that maps directly to hardware.

The same FSM can be represented as a table showing all possible transitions:

Current StateInput (button)Output (LED)Next State
OFF00OFF
OFF10ON
ON01ON
ON11OFF

How to read this table (Moore machine):

  • Output column: Shows the LED value while in the current state (before the clock edge)

  • Next State column: Shows where we go after the clock edge based on the input

Example walkthrough:

  • Row 1: In state OFF (LED=0). Input button=0. LED outputs 0, stay in OFF.

  • Row 2: In state OFF (LED=0). Input button=1. LED outputs 0, transition to ON.

    • After clock edge: Now in ON state → LED becomes 1

  • Row 3: In state ON (LED=1). Input button=0. LED outputs 1, stay in ON.

  • Row 4: In state ON (LED=1). Input button=1. LED outputs 1, transition to OFF.

    • After clock edge: Now in OFF state → LED becomes 0

Key insight: The output shown is what the current state produces. After the clock edge, you enter the next state and its output becomes active.

Moore vs Mealy Machines

There are two fundamental types of FSMs, differing in how outputs are determined:

AspectMooreMealy
Output depends onCurrent state onlyCurrent state AND inputs
Output associated withStates (inside circles)Transitions (on arrows)
States neededMore states may be neededFewer states possible
Timing complexitySimplerMore complex
Output changesOnly on clock edges (synchronous)Can change with inputs (asynchronous)
NotationState/OutputInput/Output on arrows
Typical use casesControllers, most general-purpose FSMs, CPU control unitsSequence detectors, protocol handlers, designs requiring minimal states
Adoption in practiceMost common — easier to design, debug, and verify; preferred for synthesis toolsUsed when state minimization is critical or faster response needed

Why Moore is more common:

  • Outputs are glitch-free — they only change on clock edges, avoiding hazards

  • Easier timing analysis — output timing is predictable and synchronous

  • Simpler verification — outputs depend only on state, not input combinations

  • Better for synthesis — HDL tools optimize Moore machines more reliably

When to use Mealy:

  • Need one clock cycle faster response (output changes immediately with input)

  • State count matters (limited flip-flops, or very complex state space)

  • Designing protocol interfaces where fast acknowledgment is critical

Example: Sequence Detector

Let’s visualize both for the same problem: detecting when input X has been 1 for two consecutive clock cycles. Output Z goes HIGH when we’ve seen two 1s in a row.

Color convention: Blue = pattern not found yet (Z=0), Green = two consecutive 1s detected (Z=1)

Loading...

Key observation from this example:

Notice how the Mealy machine achieves the same detection with only 2 states compared to Moore’s 3 states. This is because Mealy’s output depends on both state and input, allowing more information to be encoded per state. However, this comes at the cost of more complex timing analysis since outputs can change asynchronously with inputs.

State Tables

Now let’s look at the formal state table representations for both Moore and Mealy versions of our sequence detector.

Moore Machine State Table

For the sequence detector Moore machine:

Current StateInput (X)Output (Z)Next State
S000S0
S010S1
S100S0
S110S2
S201S0
S211S2

This table follows the Moore machine format: outputs depend only on the current state, and state transitions occur on clock edges.

Mealy Machine State Table

For the Mealy version:

Current StateX=0 (Next/Out)X=1 (Next/Out)
S0S0/0S1/0
S1S0/0S1/1

How to read this table (Mealy machine):

  • Notation: “NextState/Output” shows both next state and output for that input

  • Output timing: Output is produced combinationally (changes as soon as input changes, independent of the clock)

  • Key difference: Output can change before the clock edge when input changes (asynchronous to state transitions)

Example: Row 2, column “X=1” shows “S1/1” means: currently in S1 with input X=1, output Z=1 is produced combinationally (immediately when X becomes 1, not waiting for a clock edge), and we’ll stay in S1 after the next clock edge.

Moore vs Mealy timing:

  • Moore: Output changes only on clock edges (when state changes) — synchronous

  • Mealy: Output changes immediately when input changes (combinational logic) — can be asynchronous to clock

Implementing the Sequence Detector in Hardware

Now let’s walk through how to translate our sequence detector state diagram into actual digital hardware. This involves two main steps:

  1. State Encoding — Assign binary codes to each state

  2. Derive Boolean Equations — Use Karnaugh maps to find minimal logic expressions

We’ll use the 3-state Moore machine from the sequence detector example above.

Step 1: State Encoding

To implement an FSM in hardware, we need to assign binary codes to states. The number of flip-flops required is:

Number of flip-flops=⌈log⁡2(number of states)⌉\text{Number of flip-flops} = \lceil \log_2(\text{number of states}) \rceil
(1)

For our 3-state Moore machine: ⌈log⁡2(3)⌉=2\lceil \log_2(3) \rceil = 2 flip-flops.

Why? 2 flip-flops can represent 22=42^2 = 4 distinct states, which is the minimum needed for 3 states. With only 1 flip-flop we’d have 21=22^1 = 2 states (insufficient). The 4th state (binary 11) will be unused in our design—we call this a “don’t care” state.

Common Encoding Schemes

Loading...

Choosing an encoding:

  • Binary: Minimizes flip-flops; good for resource-constrained designs

  • Gray code: Adjacent states differ by one bit; reduces glitches in outputs

  • One-hot: One flip-flop per state; simplifies next-state logic, common in FPGAs

For our sequence detector, we’ll use binary encoding:

StateQ₁Q₀
S000
S101
S210

Encoded State Table

Now we create the complete state table with binary-encoded states. This table shows:

  • Current state encoding (Q₁, Q₀)

  • Input (X)

  • Output (Z) — for Moore machines, depends only on current state

  • Next state encoding (D₁, D₀) — the values we need to feed to the flip-flops

Q₁Q₀XZD₁D₀Notes
000000S0, X=0 → stay S0
001001S0, X=1 → go to S1
010000S1, X=0 → back to S0
011010S1, X=1 → go to S2
100100S2, X=0 → back to S0
101110S2, X=1 → stay S2
11----Unused state (don’t care)

Key columns:

  • D₁, D₀: The next-state values — these become the K-map outputs

  • Z: Output is 1 only in state S2 (Q₁=1, Q₀=0) — Moore machine property

Step 2: Derive Boolean Equations Using Karnaugh Maps

We use Karnaugh maps to derive minimal Boolean expressions for D1, D0, and Z from the encoded state table above (Step 1).

Understanding K-Map Structure

For each output (D1, D0, or Z), we create a K-map with:

  • Rows: Q1Q0 combinations in Gray code order (00, 01, 11, 10) - adjacent rows differ by only one bit

  • Columns: X values (0, 1)

Let’s see how to fill these K-maps from the state table:

Filling the K-Map for D1 (Next Q1)

To fill the D1 K-map, we transfer each value from the D1 column in the encoded state table to the corresponding K-map cell:

Process:

  1. For each row in the state table, find its K-map location using Q1Q0 (row) and X (column)

  2. Copy the D1 value (0, 1, or -) to that K-map cell

  3. Repeat for all rows

The rows where D1=1 are highlighted because these 1s are what we’ll group for Boolean minimization.

Filling the K-Map for D0 (Next Q0)

To fill the D0 K-map, we look at the “D0 (Next Q0)” column in the encoded state table.

Example: Row with Q1=0, Q0=0, X=1 → D0=1, so K-map cell at row “00”, column “1” contains 1

Notice that only one cell has D0=1. Most cells are 0.

Filling the K-Map for Z (Output)

To fill the Z K-map, we look at the “Z” column in the encoded state table.

Key insight for Moore machines: Z depends only on the current state (Q1, Q0), NOT on input X.

Example: Rows with Q1=1, Q0=0 → Z=1, so K-map cells at row “10” contain 1 for BOTH X=0 and X=1

This is why the entire row has the same value!

Grouping Adjacent 1s for Minimization

Once all K-maps are filled, we look for rectangular groupings of adjacent 1s. These groupings help us derive minimal Boolean expressions.

Grouping rules:

  • Group 1s in powers of 2 (1, 2, 4, 8 cells)

  • Groups can be rectangular (rows, columns, or blocks)

  • Larger groups = simpler equations

  • Don’t cares (‘-’) can be included in groups to make them larger

Let’s see the complete K-maps with groupings:

Final Boolean Equations:

D1=Q0⋅X+Q1⋅X=X⋅(Q0+Q1)D_1 = Q_0 \cdot X + Q_1 \cdot X = X \cdot (Q_0 + Q_1)
(2)
D0=Q1‾⋅Q0‾⋅XD_0 = \overline{Q_1} \cdot \overline{Q_0} \cdot X
(3)
Z=Q1Z = Q_1
(4)

These equations can be implemented with AND, OR, and NOT gates to create the next-state and output logic for our FSM.

The General FSM Architecture

Every synchronous FSM follows this pattern:

  1. State Register: Flip-flops store the current state (Q values)

  2. Next-State Logic: Combinational circuit computing D inputs from current state and inputs

  3. Output Logic: Combinational circuit computing outputs

    • Moore: Output depends only on Q (current state)

    • Mealy: Output depends on Q and inputs

  4. Clock: Synchronizes state transitions

Complete Example: Traffic Light Controller

Let’s design a simplified traffic light controller for a single intersection. The light cycles through:

  • Green (30 time units)

  • Yellow (5 time units)

  • Red (30 time units)

For simplicity, we’ll use a timer_done input signal that goes high when the current phase should end.

Loading...

State Table for Traffic Light Controller (Binary Encoding)

We’ll use binary encoding for the three states:

StateQ1 Q0
GREEN0 0
YELLOW0 1
RED1 0

Why binary encoding? For 3 states, we need only ⌈log₂(3)⌉ = 2 flip-flops. Binary encoding is efficient for this small state space.

The complete state table with encoded states:

Current StateQ1 Q0timer_doneRYGNext StateD1 D0
GREEN0 00001GREEN0 0
GREEN0 01001YELLOW0 1
YELLOW0 10010YELLOW0 1
YELLOW0 11010RED1 0
RED1 00100RED1 0
RED1 01100GREEN0 0

How to read this table:

  • Current State & Q1,Q0: The state we’re in and its binary encoding

  • timer_done: Input signal (1 = time to advance to next light)

  • R, Y, G: Output signals while in the current state (Moore machine - depends only on current state encoding)

  • Next State & D1,D0: Where we transition after the clock edge, and the flip-flop input values needed

Note: This reads naturally left-to-right: “In [current state] with [input], outputs are [R,Y,G], then transition to [next state]”

Boolean Equations

From the state table:

D1=Q0⋅T+Q1⋅T‾D_1 = Q_0 \cdot T + Q_1 \cdot \overline{T}
(5)
D0=Q1‾⋅Q0‾⋅T+Q0⋅T‾D_0 = \overline{Q_1} \cdot \overline{Q_0} \cdot T + Q_0 \cdot \overline{T}
(6)
R=Q1,Y=Q0,G=Q1‾⋅Q0‾R = Q_1, \quad Y = Q_0, \quad G = \overline{Q_1} \cdot \overline{Q_0}
(7)

where TT = timer_done.

Timing Analysis

Understanding FSM timing is critical for correct operation. Let’s trace through our sequence detector.

About the input sequence: The X pattern [0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0] was carefully chosen to demonstrate:

  1. First detection (cycles 1-3): Two consecutive 1s → S0→S1→S2, Z becomes 1

  2. Reset mid-sequence (cycle 3-4): X=0 breaks the streak → back to S0

  3. Second detection (cycles 4-7): Three consecutive 1s → detects at cycle 6, stays in S2 for cycle 7

  4. Double reset (cycles 7-8): Two 0s in a row → confirms we’re back at S0

  5. Third detection (cycles 9-11): Another pair of 1s → detection at cycle 11

Why this pattern is instructive:

  • Shows multiple detections in one trace

  • Demonstrates that Z=1 persists while X=1 continues (cycles 6-7)

  • Shows immediate reset to S0 on X=0 from any state

  • The 0s at different points show the FSM properly restarting

Reading the timing diagram:

  1. State changes occur at the rising edge of the clock

  2. The new state depends on the current state and input at the clock edge

  3. In a Moore machine, output Z changes only when the state changes

  4. Detection (Z=1) occurs when we reach state S2, which happens after seeing two consecutive 1s

Common FSM Design Patterns

Pattern 1: Sequence Detector

Detects a specific bit pattern in a stream. We built one above.

Pattern 2: Counter

Cycles through states in order. Each state represents a count value.

Pattern 3: Controller

Orchestrates multi-step operations. States represent phases of an operation (like the traffic light).

Pattern 4: Arbiter

Manages access to shared resources. States track which requester has access.

Loading...

Key Takeaways

  1. FSMs are the foundation of sequential digital design — nearly every digital system contains FSMs

  2. Moore vs Mealy is a fundamental design choice:

    • Moore: Simpler timing, outputs change only on clock edges

    • Mealy: Potentially fewer states, faster response to inputs

  3. State encoding affects implementation complexity:

    • Binary minimizes flip-flops

    • One-hot simplifies combinational logic

  4. The general architecture is always:

    • State register (flip-flops)

    • Next-state combinational logic

    • Output combinational logic

    • Clock: Synchronizes state transitions

  5. Design process:

    1. Draw state diagram from requirements

    2. Create state table

    3. Choose state encoding

    4. Derive Boolean equations

    5. Implement with gates and flip-flops (or HDL)

FSMs are everywhere in digital design — from simple button debouncers to complex CPU control units. Master them, and you have a powerful tool for any sequential logic problem.

Digital Design Notes
Timing Diagrams