Memory from feedback

Every circuit so far has had no memory. A decoder, an adder, a display driver: their outputs depend only on their inputs right now, and the moment the inputs change, so do the outputs. A computer needs more than that. It has to hold a number while it works on another, remember where it’s got to in a program, and keep a result for later. This page builds memory out of the same gates, with one new idea: feedback, a gate’s output wired back round to its own input.

The timing charts work as on Adding: every gate takes one gate delay to respond, each row is one wire over time, and orange is 1.

1 · Remembering needs a loop

Take two NOT gates and wire them in a ring: the first one’s output into the second, the second one’s output back into the first. If the first gate’s input is 0, its output is 1, so the second gate’s output is 0, which is what the first gate’s input was. Everything agrees, and nothing will ever change. Start it the other way round, with a 1, and that’s just as stable. Two stable states, and the circuit stays in whichever one it’s in: one bit of memory, with no moving parts.

Gates in a ring, with each wire’s level over time below. Two NOT gates hold whichever value they start with. Try three: an odd number can never agree with itself, so a change chases round the ring forever, flipping each wire every three gate delays. Four hold still again, and five oscillate.

An odd ring is useful too: it’s a ring oscillator, and chip makers build them to measure how fast their gates are, since the faster the gates, the faster it oscillates. (A ring of just one NOT gate, its output tied to its own input, is the exception: a real one doesn’t oscillate but settles halfway, in the in-between region of the inverter, so these pages leave it out.)

Two NOT gates in a ring is how the fastest memory in a processor really holds a bit. A cell of static RAM (SRAM) is exactly that pair of inverters, plus two transistors that connect it to the wires for reading and writing: six transistors per bit.

2 · The SR latch

The ring holds a bit, but there’s no way to tell it which. Swap the NOT gates for NOR gates, and each gets a spare input. A NOR gate’s output is 0 whenever either input is 1, so a 1 on a spare input forces that gate’s output to 0, and the ring follows. The two spare inputs are called S (set: make the stored bit, Q, 1) and R (reset: make it 0). With both at 0, each NOR acts as a plain NOT gate, and the ring holds. That’s an SR latch. Its two outputs are Q and its opposite, Q̄.

Click S to set it, then click S again to let go: Q stays 1. That’s memory. Click R to reset it, and let go: Q stays 0. Each change takes two gate delays, one gate after the other. Now set S and R both to 1, then let go of both together.

S and R both at 1 is the latch’s forbidden input. Both NOR gates are forced to 0, so Q and Q̄ are equal, which isn’t a stored bit at all. Worse is what happens when both are let go at the same instant: each gate sees two 0s, so both outputs go to 1; then each sees a 1, so both go to 0; and round again. In this page’s model, where every gate takes exactly the same time, it never stops.

Real gates are never exactly equal, so a real latch does eventually fall one way or the other, but nobody can say which, or how long it will take. That’s called metastability, and it’s the price of building memory from feedback. It comes back on the state machines page, where it can’t be designed away.

3 · The D latch

The easy way to avoid the forbidden input is never to drive S and R separately. Make them both from a single data input, D: S is D, and R is NOT D, so they’re always opposite. Then add an enable input, E, through two AND gates, so that S and R can only be 1 while E is 1.

Click D and E. While E is 1, the latch is open: Q follows D, whatever D does. Set E to 0, and the latch closes: Q keeps the last value it had, and D can do what it likes. The chart below records each of your clicks.

That’s a D latch: “D” for data. While it’s enabled it’s said to be transparent, because D shows straight through to Q. Once it’s closed it holds.

4 · Why a latch isn’t enough

Transparency is a problem as soon as a latch’s output feeds back into its own input through some logic, which is exactly what a processor does all the time: take a register, add 1, put the result back. While the latch is open, the new value goes straight through, round the logic, and back in again, and it keeps going round for as long as the latch stays open.

The simplest case is a latch that stores its own opposite: D wired to Q̄. Each time it’s enabled it should flip once. Instead it flips over and over, as fast as the gates allow, and wherever it ends up when the enable falls is down to the timing.

Two circuits fed their own Q̄, both given the same two clock pulses. The latch flips again and again while each pulse is high. The flip-flop (next section) flips exactly once per pulse, as the clock rises.

5 · The flip-flop: two latches in turn

The fix is to make sure the path is never open all the way through. Put two D latches in a row, and open them alternately: the first while the clock is 0, the second while it’s 1. While the clock is 0, the first latch follows D, but the second is closed, so nothing gets out. When the clock rises, the first latch closes, holding the value D had at that moment, and the second opens to pass it out to Q. While the clock is 1, D can change freely: the first latch is closed. So the output changes only once, at the instant the clock rises, to what D was just before.

Click D and the clock.

Click D and the clock. Each latch lights up while it’s open. Changing D while the clock is 0 moves latch 1 but not Q; Q only changes when the clock rises. Changing D while the clock is 1 does nothing at all.

That’s an edge-triggered D flip-flop: it samples D on the clock’s rising edge and holds it until the next. It takes 11 gates here (two D latches of 5, and a NOT for the clock), and it’s the basic unit of storage in every processor’s logic.

6 · The clock

Flip-flops make a circuit move in steps, all together: every one of them takes its new value at the same moment, the clock’s rising edge, and then everything has until the next edge to settle. The clock is just a signal that goes up and down steadily, usually made by a quartz crystal oscillator, like the one in a quartz watch. Its speed is the number of rising edges per second: the 6502 in many 1980s home computers ran at about 1 MHz, a million ticks a second; a desktop processor today runs at several GHz, billions.

How fast the clock can go is decided by how long the logic between the flip-flops takes to settle, which is the subject of the state machines page.

7 · A register

A register is a row of flip-flops sharing one clock, holding a number: 8 of them hold a byte. Usually it shouldn’t take a new value on every tick, so each flip-flop gets a choice in front of it, a multiplexer like the ones on Combining gates: with load at 1 it passes the new data in; with load at 0, it passes the flip-flop’s own output back round, so the next tick stores what was already there.

Set the inputs and load, then tick the clock.

Set the four input bits and load, then click Clock tick. With load at 1, the register takes the inputs; with load at 0, it keeps what it had, however the inputs change. Each “FF” is a flip-flop from section 5, and each “load?” a two-way multiplexer.

The 6502 has a handful of 8-bit registers like this: A, X and Y, which programs do their work in, a stack pointer and a status register (which holds the flags), and a 16-bit program counter that keeps track of where it is in the program.

Summary

Memory needs feedback: two NOT gates in a ring have two stable states, one bit. (An odd ring oscillates.)
The SR latch is that ring made of NOR gates: S sets, R resets, and with both at 0 it holds. S and R both at 1 is forbidden: let go of both at once and it may never settle (metastability).
The D latch takes one data input and an enable: open, Q follows D (transparent); closed, it holds.
A latch whose output feeds back into it races round while open. The edge-triggered flip-flop, two latches opening in turn, changes only as the clock rises.
The clock makes every flip-flop step together; the logic between them has until the next tick to settle.
A register is a row of flip-flops sharing a clock, each with a load-or-keep multiplexer in front.