Sequential Circuits and FSMs

Overview

A sequential circuit has outputs that depend on both current inputs and past history (stored state). The state is held in flip-flops. The most general sequential circuit model is a Finite State Machine (FSM), the same state-machine idea you will see in parsers, UI flows, network protocols, and other software engineering systems.

Sequential Circuit Model

Inputs ─►┌──────────────────┐
         │  Next-State      │
         │  Logic (comb.)   │──► Next State
State ──►└──────────────────┘        │
   ▲                                  │
   │              ┌──────┐           │
   └──────────────┤  FFs │◄──────────┘
                  └──────┘
                      │
         ┌────────────────────┐
         │  Output Logic      │──► Outputs
         │  (comb.)           │
         └────────────────────┘

• State register: holds current state (flip-flops)
• Next-state logic: combinational; computes next state from current state + inputs
• Output logic: combinational; computes outputs

Mealy vs Moore Machines

Mealy output equation: Z = f(Q, X) Moore output equation: Z = g(Q)

FSM Design Procedure

1. Understand the specification — describe behavior as a state diagram.
2. State diagram → state table — enumerate all states, inputs, and transitions.
3. State encoding — assign binary codes to states.
4. Next-state logic — K-map or Boolean minimization for each FF input.
5. Output logic — derive output equations.
6. Implementation — select FF type, draw circuit.

State Diagram Notation

         input/output (Mealy)
State A ────────────────────► State B
         input (Moore: output labeled in state circle)

• Circle: state (Moore: output written inside or below)
• Arrow: transition
• Label: input condition / output (Mealy) or just input (Moore)
• Arrow-in (from nowhere): initial/reset state
• Double circle: accepting/final state (automata-theory convention; hardware FSMs rarely use it)

State Table Format

Mealy Machine State Table

Moore Machine State Table

State Encoding

FPGAs typically use one-hot encoding because flip-flops are plentiful and LUT-based logic favors it.

Worked Example: Sequence Detector (101)

Detect the pattern 1→0→1 in a serial input stream. Overlapping allowed.

State Diagram (Mealy)

        0/0                  1/0
       ┌───┐                ┌───┐
       ▼   │                ▼   │
 ──►  S0 ──┘ ────1/0────►  S1 ──┘
       ▲                   ▲ │
       │                1/1│ │0/0
       │        0/0        │ ▼
       └────────────────── S2

On input 1 in S2 the pattern is complete: output 1 and go to S1, because the trailing 1 already starts the next match (overlapping detection).

States: - S0 — reset / waiting for first 1 - S1 — received 1 - S2 — received 10

Transitions: | State | Input | Next | Output | |-------|-------|------|--------| | S0 | 0 | S0 | 0 | | S0 | 1 | S1 | 0 | | S1 | 0 | S2 | 0 | | S1 | 1 | S1 | 0 | | S2 | 0 | S0 | 0 | | S2 | 1 | S1 | 1 |

Binary encoding: S0=00, S1=01, S2=10 (need 2 FFs: Q₁Q₀). The unused state 11 is a don't-care in every K-map below.

Next-state logic (D FF): D₁ = Q₁′·Q₀·X′ → with the 11 don't-care: D₁ = Q₀·X′ (in S1, input 0 → S2) D₀ = Q₁′·Q₀′·X + Q₁′·Q₀·X + Q₁·Q₀′·X = X·(Q₁′ + Q₀′) → with the 11 don't-care: D₀ = X (every input 1 leads to a state with Q₀=1)

Output: Z = Q₁·Q₀′·X → with the 11 don't-care: Z = Q₁·X (in state S2, input 1)

State Minimization

Equivalent states: two states are equivalent if for every input sequence, they produce the same output sequence. Equivalent states can be merged.

Implication table method: 1. List all pairs of states. 2. Mark pairs with different outputs as distinguishable. 3. For each pair, check if their transitions lead to distinguishable pairs → mark as distinguishable. 4. Repeat until no new markings. 5. Unmarked pairs are equivalent → merge.

Timing in Sequential Circuits

Clock period T ≥ t_cq + t_logic + t_setup

Hold time constraint: t_cq + t_logic_min ≥ t_hold

Violation causes hold-time failure (data changes too soon after clock edge) — a wiring/delay problem, cannot be fixed by slowing the clock.

Synchronous vs Asynchronous Sequential Circuits

Virtually all modern digital systems are synchronous. Asynchronous design is specialized (handshake circuits, clock-domain crossing).

Hazards in Sequential Circuits

Critical race: two state variables change simultaneously; the order of changes affects which final state is reached.

Non-critical race: multiple variables change but all orderings lead to the same final state.

Cycle: the circuit cycles through a series of unstable states before settling (hazard).

Elimination: use one-hot encoding or add delays/feedback to resolve races.

Common FSM Patterns

FSM in Hardware Description

// Mealy 101 detector — the worked example above
module seq101 (
    input  wire clk,
    input  wire rst,   // synchronous, active-high
    input  wire x,
    output reg  z
);
    localparam [1:0] S0 = 2'b00, S1 = 2'b01, S2 = 2'b10;

    reg [1:0] state, next_state;

    always @(posedge clk) begin          // state register
        if (rst) state <= S0;
        else     state <= next_state;
    end

    always @(*) begin                    // next-state + output logic
        next_state = S0;
        z = 1'b0;
        case (state)
            S0: next_state = x ? S1 : S0;
            S1: next_state = x ? S1 : S2;
            S2: begin
                next_state = x ? S1 : S0;
                z = x;                   // 101 detected (Mealy output)
            end
            default: next_state = S0;    // recover from illegal state
        endcase
    end
endmodule

Separate the state register (clocked) from combinational logic (always @(*), with defaults assigned before the case) for clean synthesis and no inferred latches.