Sequential Circuits and Flip-Flops

Why This Matters

A single NAND gate has no memory. Tie two NAND gates in a feedback loop and the pair can store one bit until a later input changes it. A 32-bit register is 32 stored bits; a program counter, instruction register, cache valid bit, and pipeline register are all repeated versions of that idea.

A processor does not let every signal update whenever it wants. In synchronous logic, combinational gates compute between clock edges, and flip-flops sample on a clock edge. If the clock period is 1 ns, every path between two flip-flops must finish, including flip-flop delay, gate delay, skew, and setup time, before the next edge.

Core Definitions

Feedback Makes a Bit

A NAND gate computes $\operatorname{NAND}(a,b)=\neg(a \land b)$. With no feedback, the output is forgotten when inputs change. With feedback, the output of one gate becomes an input to another, and the circuit can settle into one of two stable states.

The active-low SR latch built from cross-coupled NAND gates is the canonical example. Let the external inputs be $\overline{S}$ and $\overline{R}$. The bars matter because driving an input low asserts it.

One implementation can be written as simultaneous equations:

$Q=\operatorname{NAND}(\overline{S},\overline{Q})$

$\overline{Q}=\operatorname{NAND}(\overline{R},Q)$

Worked transition from reset to hold:

The forbidden row is more than just a notation problem. When both inputs are low, both NAND outputs become 1, so $Q$ and $\overline{Q}$ stop being complements. If both inputs then return high at nearly the same time, the final state depends on tiny delay differences. That is a race.

Gated D Latch

An SR latch exposes two controls and has a forbidden input combination. A D latch hides that problem by generating set and reset requests from a single data input $D$ and an enable $E$.

For a NAND-based gated D latch, the internal active-low inputs are:

$\overline{S}=\operatorname{NAND}(D,E)$

$\overline{R}=\operatorname{NAND}(\neg D,E)$

When $E=0$, both $\overline{S}$ and $\overline{R}$ equal 1, so the latch holds. When $E=1$, exactly one of the two internal requests is asserted.

This is level-sensitive. If $E$ stays high for 10 ns and $D$ changes after 4 ns, then $Q$ can change after that. The latch is transparent while enabled. That property is useful in latch-based timing, but in the common single-clock model it is harder to reason about than edge-triggered storage.

A compact C model shows the behavior without gate delays:

#include <stdint.h>

typedef struct {
    uint8_t q;
} DLatch;

void d_latch_step(DLatch *x, uint8_t enable, uint8_t d) {
    if (enable) {
        x->q = d & 1;      // transparent while enable is high
    }
}

For input samples (E,D) = (0,0), (1,1), (1,0), (0,1), starting from q=0, the output sequence is 0,1,0,0. The last input has D=1, but the latch is closed.

Edge-Triggered D Flip-Flop

A rising-edge D flip-flop can be built from two D latches in series. The first latch is the master; the second is the slave. On the usual construction, the master is open when clock is low, and the slave is open when clock is high.

The input value is captured at the low-to-high transition because the master closes just as the slave opens. After the edge, changes on $D$ cannot reach $Q$ until the next rising edge because the master is closed.

Example timing with sampled integer bits:

A register is an array of flip-flops sharing a clock. A 4-bit register storing decimal 10 has bit vector 1010 if written most-significant bit first. At the physical flip-flop level it is often better to name bits by index:

This C model updates all bits together, matching edge-triggered behavior:

#include <stdint.h>

typedef struct {
    uint8_t q;             // only low 4 bits are used
} Reg4;

void reg4_rising_edge(Reg4 *r, uint8_t d) {
    r->q = d & 0x0f;       // simultaneous 4-bit sample
}

The assignment is a single state update in the model. In hardware, it is four flip-flops receiving the same active clock edge.

Setup, Hold, and Clock Skew

A flip-flop is an analog device under the digital abstraction. Near a clock edge, internal nodes race toward stable voltages. If $D$ changes too close to the sampling edge, the flip-flop can enter metastability or capture the wrong Boolean value.

The basic synchronous timing inequality for a path from one flip-flop to the next is:

$T_{clk} \geq t_{cq,max}+t_{logic,max}+t_{setup}+t_{skew}+t_{margin}$

Here $t_{cq,max}$ is clock-to-Q delay of the source flip-flop, and $t_{logic,max}$ is the worst combinational delay on the path.

Numeric example. Suppose $t_{cq,max}=80$ ps, $t_{logic,max}=620$ ps, $t_{setup}=70$ ps, clock skew is 40 ps against the path, and margin is 30 ps. Then:

$T_{clk} \geq 80+620+70+40+30=840\text{ ps}$

The maximum clock frequency is about $1/840\text{ ps}=1.19$ GHz.

Hold time is checked near the same edge, not the next one. A common simplified condition is:

$t_{cq,min}+t_{logic,min} \geq t_{hold}+t_{skew}$

If $t_{cq,min}=30$ ps, $t_{logic,min}=20$ ps, $t_{hold}=60$ ps, and skew is 10 ps in the bad direction, then $50 \ngeq 70$. The receiving flip-flop might see new data too soon. The fix is not to slow the clock; the fix is to add minimum delay on that short path or change clock distribution.

Synchronous Design Discipline

The standard single-clock discipline is simple. State lives only in flip-flops. All flip-flops use the same active clock edge. Between clock edges, combinational logic computes the next state and outputs.

A synchronous circuit with state register $S$ and input $I$ follows:

$S_{t+1}=F(S_t,I_t)$

$O_t=G(S_t,I_t)$

Or, for Moore output logic:

$O_t=G(S_t)$

One global edge makes the mental model discrete. At cycle $t$, all registers contain old state. After the rising edge, all registers contain the sampled next state. The combinational cloud may glitch between edges, but those glitches do not matter if timing constraints are met and only registered values are sampled.

Worked Examples

A 3-bit binary up-counter uses three flip-flops storing $Q_2Q_1Q_0$. Its next-state function is $Q+1$ modulo 8.

Bit equations for a synchronous incrementer are:

$D_0=\neg Q_0$

$D_1=Q_1 \oplus Q_0$

$D_2=Q_2 \oplus (Q_1 \land Q_0)$

A shift register stores a vector and shifts it one position per edge. For a 4-bit right shift with serial input in, define new bits as:

Start with Q3 Q2 Q1 Q0 = 1011. Feed serial inputs 0, 1, 1.

The byte-level analogy is exact if the register is packed into a low nibble:

#include <stdint.h>

uint8_t shift4_right(uint8_t q, uint8_t serial_in) {
    q &= 0x0f;
    return (uint8_t)(((serial_in & 1) << 3) | (q >> 1));
}

/* 0b1011 -> in 0 gives 0b0101
   0b0101 -> in 1 gives 0b1010
   0b1010 -> in 1 gives 0b1101 */

Finite-State Machines

A finite-state machine adds meaning to the stored bits. The state register holds an encoded state, and combinational logic computes the next encoded state.

A Moore machine output depends only on state. A Mealy machine output depends on state and input. For a serial detector that emits 1 when the suffix 101 has just been seen, a Mealy machine can assert output on the same cycle as the last input bit.

Use states named by the longest matched suffix:

Transition and output table for Mealy detection of 101:

State assignment maps symbolic states to bits. With two flip-flops, choose A=00, B=01, C=10, leaving 11 unused. The next-state table becomes:

The unused state rows are specified to return to A. Leaving them unspecified can make simulation and hardware disagree after reset problems or transient faults.

Key Result

The synchronous abstraction is valid when every register-to-register path meets both a maximum-delay and a minimum-delay constraint:

$T_{clk} \geq t_{cq,max}+t_{logic,max}+t_{setup}+t_{skew}+t_{margin}$

$t_{cq,min}+t_{logic,min} \geq t_{hold}+t_{skew}$

These inequalities are not performance hints. They are the contract that lets a physical network of gates behave like the recurrence $S_{t+1}=F(S_t,I_t)$.

For the counter above, the recurrence is $S_{t+1}=(S_t+1)\bmod 8$. The flip-flops do not update one at a time in the abstract model. All three sample their D inputs on the same rising edge. If one flip-flop receives a delayed clock, the counter can skip states because one bit has sampled an input from a different logical cycle.

Common Confusions

Exercises

References

Canonical:

• Charles Petzold, Code: The Hidden Language of Computer Hardware and Software, 2nd ed. (2022), ch. 10-14, covers relays, feedback, binary addition, and early memory circuits
• David A. Patterson and John L. Hennessy, Computer Organization and Design: The Hardware/Software Interface, 5th ed. (2014), Appendix B, covers logic design, clocking, latches, flip-flops, and finite-state machines
• J. Clark Scott, But How Do It Know? The Basic Principles of Computers for Everyone (2009), ch. 3-8, builds registers, memory, and control from simple gates
• M. Morris Mano and Michael D. Ciletti, Digital Design, 5th ed. (2013), ch. 5, covers synchronous sequential logic and flip-flop timing
• David Money Harris and Sarah L. Harris, Digital Design and Computer Architecture, 2nd ed. (2012), ch. 3, covers sequential logic, registers, counters, and FSMs

Accessible:

• Noam Nisan and Shimon Schocken, The Elements of Computing Systems, 2nd ed. (2021), ch. 3
• MIT OpenCourseWare, 6.004 Computation Structures, lectures on sequential logic and finite-state machines
• Ben Eater, video series on building an 8-bit computer from logic chips

Next Topics

• /computationpath/combinational-circuits
• /computationpath/registers-and-memory
• /computationpath/finite-state-machines
• /topics/modular-arithmetic