Introduction to Sequential Logic

A combinational circuit implements a Boolean function `output = f(inputs)` with no internal memory: at every instant, the outputs are fully determined by the inputs present at that instant, and previous inputs leave no trace. Formally, if two input assignments are identical, the outputs must be identical too, regardless of what came before. This is what makes combinational circuits analyzable with truth tables and Boolean algebra alone. A sequential circuit breaks this property on purpose. It contains at least one feedback path: a wire that carries a signal derived from an output (or an internal node) back to an input of the same circuit, possibly after passing through storage elements. Because of this loop, the circuit's output at time `t` can depend on inputs the circuit received at times before `t`, not merely on the input at time `t` itself. The summarized, compressed record of that history — the minimal information needed to predict future behavior given future inputs — is called the state of the circuit. Formally, a sequential circuit is modeled as a tuple `(S, Σ, δ, λ, s₀)`: a set of states `S`, an input alphabet `Σ` (the possible input combinations), a next-state function `δ: S × Σ → S` describing how the state updates, an output function `λ` describing what the circuit outputs, and an initial state `s₀`. If `λ` depends only on the current state, the machine is called a Moore machine; if `λ` depends on both the current state and the current input, it is a Mealy machine. This is precisely the theory of Finite State Machines, and it is not a coincidence — sequential circuits are physical realizations of finite automata, with `δ` and `λ` implemented as combinational logic and `S` held in physical memory elements.

The architectural skeleton of nearly every sequential circuit is the same, and it is worth memorizing as a template: a block of combinational logic computes the next state and the outputs, and a block of state-holding elements (built ultimately from feedback loops, and later refined into latches and flip-flops) stores the current state and feeds it back as an input to the combinational block. ``` STATE-MACHINE-STEP(state, input): // Combinational next-state logic: pure function, no memory next_state ← δ(state, input) // Combinational output logic if Moore: output ← λ(state) // depends only on current state else: // Mealy output ← λ(state, input) // depends on state AND input return (next_state, output) RUN(initial_state, input_sequence): state ← initial_state outputs ← [] for input in input_sequence: (state, out) ← STATE-MACHINE-STEP(state, input) append out to outputs // In real hardware, "state ← next_state" happens // atomically at a clock edge, not gradually. return outputs ``` The crucial detail hidden in that last comment is the timing discipline. In an idealized mathematical automaton, the transition from one state to the next is instantaneous and atomic — there is no in-between. Real circuits are built from gates with nonzero propagation delay, and a feedback wire is a physical loop: a signal change at the output can race back around to the input and change the output again, which can race back around again, and so on. If this loop is not disciplined, the circuit can oscillate, glitch, or settle into a value that depends on unpredictable timing races rather than on a clean logical rule. There are two broad families of sequential circuit that manage this feedback differently:

Asynchronous (unclocked) sequential circuits. State changes happen whenever the feedback loop's logic dictates, with no external timing signal. The simplest example is a cross-coupled pair of NOR (or NAND) gates — the ancestor of the SR latch — where each gate's output feeds the other gate's input. Such circuits can be bistable (settle into one of two stable states, which is exactly what makes them useful as 1-bit memories) but analyzing their behavior requires careful attention to gate delays, and they are prone to a phenomenon called a race condition, where the final state depends on which of two nearly-simultaneous signal changes "wins" the race through the gates.

Synchronous (clocked) sequential circuits. A global clock signal partitions time into discrete steps, and state is only permitted to change at controlled moments (e.g., a clock edge), never in between. This is the discipline used in essentially all large-scale digital systems, because it converts an analog timing problem (managing feedback delays throughout an unruly loop) into a discrete algorithmic one (make sure the combinational logic settles before the next clock edge). The state-holding devices that implement this discipline — latches and, more commonly, edge-triggered flip-flops — are the subject of the next article in this sequence; here we focus on why such a mechanism is needed at all. The figure below shows the generic architecture that every synchronous sequential circuit shares.

The purple clock arrow in the figure is the key addition that a synchronous design makes over a bare feedback loop: the state register is only permitted to load the computed `next_state` at a clock edge, and it holds that value steady in between edges — even while the combinational logic's output may be temporarily glitching as signals propagate through gates. This is what prevents the race conditions of naive asynchronous feedback while preserving the essential idea: state feeds back into logic that computes the next state.

Space. A sequential circuit implementing an `n`-state machine needs at least `⌈log₂ n⌉` bits of state memory, since that many bits are the minimum required to distinguish `n` states. The combinational logic block has size proportional to the complexity of `δ` and `λ` as Boolean functions of `⌈log₂ n⌉` state bits and `⌈log₂ |Σ|⌉` input bits — in the worst case this can be exponential in the number of state bits (as with any Boolean function representation), but for the state machines that arise in practice (counters, sequence detectors, control units) it is typically linear or low-polynomial in the bit width, because these functions have exploitable regular structure.

Time. Per clock cycle, the time required for the combinational block to settle is bounded by its propagation delay, `t_pd`, the worst-case time for a signal change at any input to produce a stable, correct value at every output. This quantity is what ultimately sets the maximum clock frequency of a synchronous circuit (the subject of the Clocks and Timing article): the clock period must exceed `t_pd` plus the setup/hold requirements of the storage elements, or the circuit will sample an unsettled, incorrect value. A sequential circuit executing `k` steps of its automaton therefore requires time `Θ(k · t_pd)` in the synchronous model, since each step is one clock period.

Why feedback is necessary, not incidental. This can be argued directly from the definition of a function. A combinational circuit realizes a fixed Boolean function: same input, same output, always. A device such as a 1-bit memory cell must, by specification, produce different outputs (0 or 1) for the same control input (say, "read") depending on what was last written. No fixed function of the current inputs alone can do this — a function cannot map one input tuple to two different outputs. Therefore any circuit with this behavior must have an internal node whose value depends on the past, and the only way for a node's present value to depend on the past, in a circuit with no separate memory technology, is for that node to be wired, directly or indirectly, back into itself: a feedback loop. This is a proof by contradiction that feedback (in some form) is necessary for any circuit that stores state using ordinary logic gates — it is not an incidental engineering choice but a logical requirement.

Why synchronous discipline is correct. The correctness argument for clocked sequential circuits rests on an invariant maintained across clock cycles: Invariant: At every clock edge (and only at that instant), the value latched into the state register equals `δ(previous_state, input)`, computed from values that were stable and correct throughout the preceding clock period. This invariant holds by induction on clock cycles, provided the timing constraint `T_clock ≥ t_pd(logic) + t_setup(register)` is respected (guaranteeing the combinational logic has finished computing, and the register has enough setup time to reliably capture the result, before the next edge arrives). Given the invariant, the physical circuit's sequence of states is exactly the sequence produced by the abstract automaton `δ`, so reasoning about the circuit reduces entirely to reasoning about the finite-state machine — a purely discrete, timing-independent model. This is the deep payoff of synchronous design: it converts a continuous-time, analog correctness problem (avoiding races in feedback loops) into a discrete, combinatorial one (get the clock period long enough, then just verify the automaton).

Tradeoffs. Synchronous design buys this clean correctness argument at a real cost: the clock period is dictated by the slowest path in the whole circuit, so a single slow combinational block throttles every other part of the system, and clock distribution itself (routing one signal to every storage element with low skew) becomes a nontrivial engineering problem at scale. Asynchronous design avoids this by letting each part run at its own local pace, potentially yielding higher performance and lower power, but at the cost of far harder correctness reasoning, since race conditions must be ruled out by careful timing analysis rather than a simple global inequality.

Consider a minimal but genuinely non-trivial sequential circuit: a 1-bit up counter modulo 4, i.e., a 2-bit binary counter that cycles `00 → 01 → 10 → 11 → 00 → …` on each clock tick, with no external input other than the clock itself. This is small enough to trace completely, yet large enough to show state changing in a way a combinational circuit fundamentally cannot replicate. State is a pair of bits `(Q₁, Q₀)` representing the count in binary. The next-state logic (pure combinational Boolean algebra) computes: ``` next_Q0 = NOT Q0 next_Q1 = Q1 XOR Q0 ``` Let's verify this really implements modulo-4 counting by tracing every reachable state:

The trace confirms the cycle closes correctly after exactly 4 steps and repeats identically thereafter — exactly the behavior of a mod-4 counter, and exactly the kind of periodic, history-dependent output that a stateless combinational circuit cannot produce (a combinational circuit with no inputs can only ever emit one fixed constant output, never a sequence). Notice the essential role of feedback: `next_Q1` and `next_Q0` are computed from `Q1` and `Q0`, the very same bits that are about to be overwritten. Without the feedback wires carrying `Q1` and `Q0` back into the XOR/NOT gates, there would be nothing to compute a "next" value from at all — the "next state = f(current state)" relationship is only expressible because the circuit's own stored output is wired back in as its own input. Every clock edge, the state register captures the freshly computed `(next_Q1, next_Q0)`, holds it steady through the entire following period (during which the combinational XOR/NOT gates use it to compute the next next-state), and the cycle repeats — precisely the atomic-update behavior the correctness invariant in the previous section requires.

The conceptual leap from "circuit as function" to "circuit with memory" did not arrive fully formed; it emerged from a convergence of automata theory, relay engineering, and early computer design.

Mealy and Moore's formalization deserves special emphasis: it gave engineers a rigorous, general-purpose vocabulary (states, transitions, next-state and output functions) that applies equally to a hand-drawn vending-machine diagram and to the control unit of a modern out-of-order processor. This is the theoretical backbone that made it possible to design sequential hardware systematically rather than by trial and error with ad hoc feedback loops.

Sequential logic is the substrate of essentially every stateful digital system in existence. Processors use sequential circuits for the program counter (which must remember which instruction comes next), the register file, and the pipeline control logic that tracks which instructions are in flight. Memory systems, from SRAM cells built on cross-coupled feedback loops to DRAM refresh controllers, are sequential circuits at their core. Communication protocols implemented in hardware — a UART, an Ethernet MAC, a USB controller — are literally finite-state machines realized as clocked sequential logic, tracking whether a device is idle, transmitting, or waiting for acknowledgment. Digital controllers in cars, appliances, and industrial equipment (traffic lights, elevator controllers, vending machines, washing-machine cycle sequencers) are textbook Moore or Mealy machines in physical silicon or microcontroller firmware. Even FPGAs, which are reconfigurable fabrics of combinational lookup tables plus flip-flops, are structured explicitly around the combinational-logic-plus-state-register template this article describes — because that template is, in a precise sense, the only way to build a synchronous machine with memory out of logic gates.

Ask the tutor: How does an SR latch built from cross-coupled NOR gates actually implement this feedback idea at the transistor/gate level?