Sequential Logic

Part of Boolean Logic and Gates

Circuits with memory — outputs depend on both current inputs and stored state, enabling counters, shift registers, and finite state machines.

Why This Matters

Combinational logic circuits are stateless — the output depends only on the current inputs, and nothing is remembered between moments. Sequential logic introduces time and memory. The output depends on both current inputs and the circuit’s history (its stored state). This is what makes it possible to count, sequence operations, decode protocols, and implement control logic.

Every non-trivial digital system is sequential. A CPU is a sequential machine — it executes instructions one after another, maintaining state in registers and program counter. A traffic light controller is sequential — it moves through green, yellow, red in order. A UART receiver is sequential — it detects a start bit and then collects 8 data bits in order.

Understanding sequential logic is understanding how digital systems do anything more than instantaneous computation. It is the bridge from gates to machines.

The State Concept

A sequential circuit has state — a snapshot of all the values stored in its flip-flops at a given moment. The state captures everything relevant about the circuit’s history that will affect its future behavior.

The state transition describes how the state changes on each clock edge, given the current state and inputs. This is formalized as:

Next_state = f(Current_state, Inputs) Outputs = g(Current_state, Inputs) [or g(Current_state) for Moore machines]

A sequential circuit is completely characterized by its state transition table (or state diagram) plus the combinational logic that implements the next-state function.

Mealy vs. Moore Machines

Two models of sequential circuits:

Moore machine: outputs depend only on the current state, not directly on inputs. Output logic: Output = g(State).

Mealy machine: outputs depend on both current state and current inputs. Output logic: Output = g(State, Input).

Both are equivalent in computational power, but differ in behavior timing and state count:

• Moore machines need more states but have synchronous, glitch-free outputs (outputs change only at clock edges).
• Mealy machines can respond to inputs within the same clock cycle (one cycle faster), but outputs can glitch if inputs change asynchronously.

For most practical control circuits, the choice is a tradeoff between state count and output timing requirements.

State Diagram and State Table

A state diagram represents states as circles and transitions as arrows. Each arrow is labeled with the input condition that causes the transition. Moore machine outputs are written inside the state circles; Mealy machine outputs are written on the arrows.

Example: a simple 2-bit synchronous counter has states S0 (00), S1 (01), S2 (10), S3 (11). Transitions: S0→S1→S2→S3→S0 on each clock edge (no input). Outputs are the state bits themselves.

A state table formalizes this as a truth table:

Current State	Input	Next State	Output
S0 (00)	—	S1 (01)	00
S1 (01)	—	S2 (10)	01
S2 (10)	—	S3 (11)	10
S3 (11)	—	S0 (00)	11

From the state table, derive the Boolean equations for the next-state flip-flop inputs and implement with combinational logic plus flip-flops.

Designing a Sequential Circuit

The systematic design process:

Step 1: Define the state diagram. Identify all states the system must remember and all valid transitions between them.

Step 2: Encode states in binary. Assign a binary code to each state. With K states, you need at least ⌈log₂(K)⌉ flip-flops.

Step 3: Build the state table. Fill in next-state and output for every (current state, input) combination.

Step 4: Write next-state equations. For each flip-flop’s D input, write the Boolean equation for its next value (the column in the state table). Use Karnaugh maps to minimize.

Step 5: Write output equations. Similarly, Boolean equations for each output bit.

Step 6: Implement. Build the combinational logic for next-state and output equations, plus the flip-flops for state storage. Connect flip-flop Q outputs back to the combinational logic inputs.

Synchronous vs. Asynchronous Sequential Circuits

Synchronous: all flip-flops share a common clock. State changes happen only at clock edges. This is the dominant design style because it is predictable, easy to analyze, and immune to hazards in the combinational logic (as long as logic settles before the next clock edge).

Asynchronous: no shared clock. State changes occur immediately when inputs change, propagating through the circuit like waves. More complex to design and debug — hazards in the combinational logic can cause spurious state transitions. Used in very high-speed circuits where the synchronous clock penalty is unacceptable.

For any new digital design, use synchronous design. The clock is your friend. It ensures all state changes happen at known, controlled instants.

Practical Example: Traffic Light Controller

States: GREEN, YELLOW, RED, RED_YELLOW (for some European traffic systems) Transitions: GREEN → YELLOW → RED → RED_YELLOW → GREEN Timer input: when T=1, advance to next state on clock edge.

Encode states: GREEN=00, YELLOW=01, RED=10, RED_YELLOW=11 Two flip-flops (S1, S0) needed.

Next-state equations (Moore machine, T=timer enables transition):

• S1_next = NOT-S1 AND S0 AND T, OR S1 AND NOT-S0 (partial — derive from full state table)
• S0_next = NOT-S1 AND NOT-S0 AND T, OR S1 AND S0 (partial)

Output equations:

• Red_light = S1 (states 10 and 11)
• Yellow_light = S0 (states 01 and 11)
• Green_light = NOT-S1 AND NOT-S0 (state 00)

Implement combinational logic, connect to two D flip-flops, add a timer input. The traffic light sequence runs automatically, advancing states on each timer pulse.