Part I · Chapter 3

Memory from Feedback

Every circuit we've built so far forgets instantly: change an input and the old answer is gone. In this chapter we do something that looks like a wiring mistake, connecting a gate's output back into its own input, and discover how a computer remembers.

The adders and gates from the last two chapters are combinational circuits: their output depends only on what their inputs are right now. That's useful, but it isn't enough to build a computer. Think about adding up a long list of numbers. You need somewhere to keep the running total between one addition and the next. A computer has to hold on to its numbers, its program, and its place in that program.

Circuits that remember are called sequential circuits, because their output depends on the sequence of things that happened before. And the trick that makes them possible is surprisingly simple: a loop.

The loop that remembers

Take two NOT gates and connect them in a circle: the output of the first feeds the second, and the output of the second feeds back into the first. Call the two wires A and B.

Suppose A is 0. The first gate flips it, so B is 1. The second gate flips that, so A is 0, which is exactly what we assumed. Everything agrees, and nothing will ever change. But the opposite works just as well: if A is 1, then B is 0, and A stays 1. The loop has two stable states, and it will sit in whichever one it's in for as long as the power is on.

Use the buttons to store a 1 or a 0. Then notice that nothing is driving the loop from outside, and still it holds its value. That's one bit of memory.

A circuit with two stable states is called bistable. It's the simplest possible memory, and it's no toy. This exact pair of crossed inverters, plus two transistors that act as doors for reading and writing, is an SRAM cell: six transistors that store one bit. The caches inside your processor are made of billions of transistors arranged this way. We'll meet them again in Part III.

The loop that never settles

What if we use three NOT gates instead of two? Follow the logic around: if A is 1, then B is 0, then C is 1, and so A should be 0. But we said A was 1! There's no way for all three gates to agree. Each one is always busy correcting the one before it.

Each step is one "gate delay": the tiny time it takes a gate to react to its input. Watch the change chase itself around the loop forever.

This is a ring oscillator. Real ones, made of fast transistors, flip billions of times per second, and chips use them to measure their own speed and to generate timing signals. So feedback gives us two gifts: an even loop remembers, and an odd loop ticks. A computer needs both: memory to hold its work, and a steady tick, called the clock, to keep everything in step.

The SR latch

The two-inverter loop holds a bit nicely, but changing it is awkward: you have to overpower both wires at once. Let's make it controllable. Replace each NOT gate with a NOR gate (OR followed by NOT). A NOR outputs 1 only when both of its inputs are 0. The second input of each gate gives us a handle:

S ("set") forces the output Q to 1.
R ("reset") forces Q back to 0.
With both at 0, each NOR acts just like a NOT, and we're back to our loop that remembers.

The second output is always the opposite of Q, so it's called Q̄ ("Q bar", or "not Q").

Switch S on and off again. Q stays 1 even after you let go. Then do the same with R. Finally, try turning S and R on together.

That's a latch: it latches on to whatever you last told it. Just as with the full adder in Chapter 1, from now on we'll draw it as a box and stop worrying about the two gates inside.

Turning on S and R together asks the latch to be 1 and 0 at the same time. Both outputs drop to 0, which breaks the promise that Q̄ is the opposite of Q. Worse, if you could release both at exactly the same instant, the result would depend on which gate happened to be a hair faster. Designers simply never let that happen.

The D latch: a bit, and a moment

Having two inputs and a forbidden combination is clumsy. What we really want is simpler: "here's a bit, store it now." So we add a small front end:

A single data input, D.
An enable input, E, which says when to listen.

Two AND gates sit in front of the latch. When E is 0, both AND gates output 0, so S = R = 0 and the latch just holds. When E is 1, D goes straight to S and its opposite (through a NOT gate) goes to R. Since D and NOT D are never both 1, the forbidden state can't happen.

Below the circuit is a logic analyzer, a tool engineers use to watch signals change over time. Each row is one wire: high means 1, low means 0, and time flows from left to right. These pictures are called timing diagrams, and they're how engineers think about circuits that change over time.

Turn E on and wiggle D: Q follows along. Now turn E off and wiggle D again: Q ignores it and keeps its last value. Watch the waveforms below.

While E is 1, the D latch is transparent: Q copies every change on D, as if the latch weren't there. The moment E drops to 0, it freezes whatever D was at that instant.

Why "transparent" is a problem

Real computers are full of loops: a value comes out of storage, goes through some logic, and the result goes back into the same storage. Think of a counter doing x = x + 1, or a program updating a running total.

Suppose that storage is a transparent latch. We enable it to save the new value of x. But while it's enabled, the new value passes straight through to the output, into the adder, comes out one bigger, and goes straight back in… and again… and again, as fast as the gates can go, for as long as enable is on. It's the ring oscillator all over again.

Here's the simplest version of that trap: a circuit wired to flip itself, by feeding Q̄ back to D. At the top is a D latch; below it, a D flip-flop, which we'll take apart in a moment.

Turn CLK on and leave it on for a second, then turn it off. The latch keeps flipping the whole time CLK is high; the flip-flop flips exactly once. Then try the automatic clock.

The latch flips as many times as it can manage while CLK is high. How many flips that is depends on how long you hold it and how fast the gates are, which makes it useless. The flip-flop flips once per tick, however long the tick lasts. That's the behavior we want: it only changes at the edge, the instant the clock goes from 0 to 1.

The edge-triggered flip-flop

How do you build something that reacts to an instant rather than a level? With two D latches in a row, which take turns:

The first, the master, is open while the clock is 0. It follows D.
The second, the slave, is open while the clock is 1. It copies the master.

The two are never open at the same time, like the two doors of an airlock. While the clock is low, the master keeps up with D but the slave's door is shut. When the clock rises, the master's door slams shut, holding D's value from that instant, and the slave's door opens to pass that value to Q. Any later change to D is stuck outside the closed master door until the next cycle.

Change D a few times, then flip CLK from 0 to 1. Q only changes at that rising edge. The highlighted box is the latch that's currently open. Turn on the automatic clock to watch it in the analyzer.

This is a positive-edge-triggered D flip-flop, and it's the workhorse of digital design. In diagrams it's drawn as a box with a little triangle (▷) on the clock input, the symbol for "edge-triggered". A typical one takes about 20 transistors.

Look at the flip-flop's output in the self-flipping demo with the automatic clock on. Q flips once per clock cycle, so it goes up and down at exactly half the clock's speed. We've just built a circuit that divides by two, and it's the first bit of a counter. That's where the next chapter starts.

Registers: flip-flops side by side

Put 8 flip-flops next to each other, connect all their clock inputs to the same wire, and you can store a whole byte at once: on each rising edge, all 8 capture their D inputs together. That's a register. Make it 64 flip-flops wide and you have something like rax.

mov  rax, 42       ; at a clock edge, 64 flip-flops capture the bits of 42
add  rax, rbx      ; rax goes through the adder, and the sum is captured back
                   ; into rax on the next edge: the loop is safe because of edges

RISC-V has 32 registers, named x0 to x31. One of them is a fun exception: x0 (also called zero) always reads as 0, and anything written to it simply vanishes. In hardware it doesn't need any flip-flops at all, just wires tied to 0.

Try it yourself

In the SR latch, turn S on and then off again. What is Q, and why doesn't it go back to 0?
Show answer
Q = 1. With S and R both 0, each NOR acts like a NOT, and the two of them hold each other in place: the loop remembers the last thing it was told.
Why does the loop of three NOT gates oscillate, while the loop of two holds still?
Show answer
Going around the loop flips the signal once per gate. With two gates it's flipped twice, back to where it started, so the loop agrees with itself. With three it comes back flipped, contradicting itself, so it can never settle.
In the D latch, with E on, wiggle D several times. Then turn E off and wiggle D again. What does the Q row of the analyzer look like?
Show answer
While E is on, the Q trace copies D exactly. After E goes off, Q is a flat line at whatever D was at that moment, no matter what D does afterwards.
In the flip-flop demo with the automatic clock running, change D just after a rising edge. How long does it take for Q to change?
Show answer
Almost a whole clock cycle. Q only changes at the next rising edge. This delay is the price of predictability, and it's why a CPU does its work in steps, one per clock tick.
In the self-flipping demo with the automatic clock, how does the speed of the flip-flop's Q compare with the clock?
Show answer
It's exactly half. Q flips once per clock cycle, so a full up-and-down of Q takes two clock cycles. The circuit divides the clock's frequency by two.

What we learned

Combinational circuits forget; sequential circuits remember, thanks to feedback.
Two NOT gates in a loop are bistable: they hold one bit. That's the heart of an SRAM cell.
An odd loop never settles: it's a ring oscillator, the seed of a clock.
An SR latch (two crossed NOR gates) can be set, reset, or left to hold.
A D latch stores D whenever enable is on, but it's transparent: changes pass straight through.
A D flip-flop (master + slave latches) only changes on the rising edge of the clock, which makes loops safe.
Flip-flops side by side, sharing one clock, make a register.

We now have memory and a reason to tick. In the next chapter we'll build the clock itself, give registers a "load" switch so they only change when we ask, and wire flip-flops into counters, the circuit that will keep track of where a CPU is in its program.