How does it remember? · From Transistor to Browser

Chapter 4
How does it remember?

The browser
The network
Software and languages
The CPU
Memory
Arithmetic
Logic gates
The switch

Figure 4.1: Where we are in the climb from transistor to browser: the memory rung. This chapter gives the machine state: a circuit that remembers a bit, then a word, then a small bank of words.

Chapter 3 built an ALU out of gates: given two numbers it produces a result, instantly and correctly, every time. But send the inputs away and the result is gone. The circuit has no state. It is a pure function. Everything so far has been combinational: the output depends only on the present inputs and on nothing that came before.

Memory changes that. A stored bit is a value that survives after its input disappears. Building one requires something that no combinational circuit has: feedback. The output must be wired back to an input so the circuit can hold itself in a state. This chapter builds that loop from the NOR gates of Chapter 2, then disciplines it with a clock, and finally composes flip-flops into registers and a small RAM.

4.1 The problem of memory

A combinational circuit is like a calculation on paper: you can work it out, read the answer, and then put the paper down. The answer is there only while you look at it. To store the answer you need to write it somewhere, and that writing must persist when you look away.

In digital hardware, “looking away” means removing the input. A gate’s output tracks its inputs with only a tiny propagation delay. Remove the inputs and the output drops to its default. There is nothing to hold a value in place.

Feedback creates the holding force. If a gate’s output is wired back to one of its inputs, the gate can reach a state that it reinforces. Flip the output to HIGH and the feedback path keeps the input HIGH, which keeps the output HIGH. That is the sketch of a latch. The rest of the chapter turns the sketch into hardware.

4.2 The SR latch

The smallest useful feedback loop is the SR latch: two NOR gates with their outputs crossed. The output of the top gate feeds an input of the bottom gate, and the output of the bottom gate feeds an input of the top gate. Figure 4.2 shows the wiring. The yellow feedback wires are the memory: they are what make the latch different from any circuit in the previous chapters.

Three inputs, three behaviours:

S = HIGH, R = LOW: the top NOR is forced LOW, the bottom NOR sees two LOW inputs and goes HIGH. Q is set.
S = LOW, R = HIGH: the bottom NOR is forced LOW, the top NOR goes HIGH. Q is reset.
S = LOW, R = LOW: each gate’s output holds the other gate’s input, and both outputs are stable at their last value. The latch holds.

The hold state is the point. When S and R are both LOW the circuit sits in one of two stable states, each self-consistent. That is exactly one bit of memory.

Example 4-1. SR latch: cross-coupled NOR feedback

def sr_latch(s: int, r: int, q: int) -> int:
    """Next state of a cross-coupled NOR latch currently holding q.

    Set (s HIGH) drives q to HIGH; reset (r HIGH) drives it to LOW; with neither
    asserted the latch holds q. The two NORs are the feedback loop unrolled one
    step: qbar = nor(s, q), then q_next = nor(r, qbar)."""
    qbar = nor_(s, q)1
    return nor_(r, qbar)2

qbar = nor_(s, q): the top gate, which combines the set input with the current output to produce the complement.
return nor_(r, qbar): the bottom gate, combining the reset input with qbar to produce the next value of Q. The two lines unroll the feedback loop one step: they are the two NORs of the figure in sequence.

4.3 The clock and the gated D latch

The SR latch has a problem for practical use: it can be set and reset at any time, asynchronously. Building a system from dozens of such latches is difficult because signals can ripple through the network unpredictably. Real designs need a way to say: only update now, on command. That command comes from the clock, a signal that ticks between 0 and 1 at a steady rate, giving every circuit in the machine the same beat to update on.

The solution is a gated D latch. A single data input d replaces the separate S and R, and an enable input acts as a gate. While enable is HIGH the latch is transparent: Q follows d immediately. While enable is LOW the latch is opaque: Q ignores d and holds its last value.

Example 4-2. Gated D latch: transparent while enabled

def d_latch(d: int, enable: int, q: int) -> int:
    """Next state of a gated D latch. While enable is HIGH the latch is
    transparent and q follows d; while enable is LOW it holds q. That is exactly
    a multiplexer choosing between the held value and the new input."""
    return mux(enable, q, d)1

the whole latch is a multiplexer: when enable is HIGH it selects d; when LOW it feeds the held value q back to itself. Holding is just muxing a wire back to its own input.

The gated D latch is an improvement, but it still has a subtlety. While enable is HIGH, the latch is transparent: any change in d passes straight through to Q. If enable stays HIGH for a whole clock phase, then Q can race through several values during that phase. Any downstream circuit that reads Q while enable is still HIGH may see a changing value instead of a settled one.

This is the transparency problem, and it motivates the next section.

4.4 The D flip-flop

A D flip-flop solves the transparency problem by making Q change only on one instant: the rising edge of a clock signal. Two gated D latches in series produce this behaviour. The arrangement is called master-slave.

Figure 4.3: Master-slave D flip-flop. The master latch (left) is enabled by clk: it is transparent and tracks d while the clock is LOW. The slave latch (right) is enabled by clk: it is transparent and publishes the master’s captured value while the clock is HIGH. The handoff happens at the rising edge, when the master closes and the slave opens simultaneously. Q changes only at that instant.

The master latch receives the inverted clock as its enable: it is transparent while the clock is LOW. The slave latch receives the clock directly: it is transparent while the clock is HIGH. At the rising edge both switch simultaneously. The master closes, locking in the last value of d before the edge. The slave opens, presenting that locked value as the new Q. Between edges neither latch changes Q: the master is opaque while the clock is HIGH, the slave opaque while it is LOW. Q moves at one moment only.

Figure 4.4 shows the timing. Notice how Q tracks the value d held at each rising edge and ignores any changes in d that happen between edges.

Figure 4.4: Flip-flop timing. clk oscillates; d may change at any time; q updates only at the rising edge of clk, capturing the value d held at that moment and ignoring subsequent changes until the next rising edge. Every change in q lines up exactly with a clk rising edge.

Example 4-3. D flip-flop: master-slave, edge-triggered

class DFlipFlop:
    """A positive-edge-triggered D flip-flop: two D latches in master-slave.

    The master is transparent while the clock is LOW, capturing the last input
    before the rising edge; the slave is transparent while the clock is HIGH,
    publishing that captured value. So q changes only on the rising edge. The
    stored bits (master, slave) are this object's state."""

    def __init__(self) -> None:
        self.master = LOW
        self.slave = LOW

    @property
    def q(self) -> int:
        """The output bit: the slave latch's stored value."""
        return self.slave

    def tick(self, d: int, clk: int) -> int:
        """Advance one step at the given clock level and data input, returning q.
        Both latches are read from the start-of-step state, so the slave sees the
        master's old value, as the hardware does."""
        new_master = d_latch(d, not_(clk), self.master)1
        new_slave = d_latch(self.master, clk, self.slave)2
        self.master, self.slave = new_master, new_slave
        return self.q

the master latch: not_(clk) is the enable, so the master is transparent while the clock is LOW and captures the last d before the rising edge.
the slave latch: clk is the enable, so the slave is transparent while the clock is HIGH, presenting the master’s captured value as Q.

Both latches read self.master at the start of the tick call, before either is updated. This is the key to correctness: the slave sees the old master value, exactly as the hardware does when both switches trip at the same rising edge.

4.5 Registers and RAM

A single flip-flop stores one bit. A register stores a word by placing one flip-flop per bit and giving them a shared clock and a shared load line. When load is HIGH, the register captures the data word on the next rising edge. When load is LOW, each flip-flop feeds its own output back to its own input so the word holds.

A RAM (random-access memory) adds an address. The four-word RAM here holds four registers of equal width. To write, you assert the data and address and raise the write line. To read, you supply the address and combinational logic selects the right word instantly, without a clock edge.

The address decoder turns two address bits into four one-hot select lines: exactly one is HIGH, choosing a single register.

Example 4-4. 2-to-4 address decoder: one-hot output

def decoder(a1: int, a0: int) -> list[int]:
    """A 2-to-4 address decoder: four one-hot select lines, exactly one HIGH,
    chosen by the two address bits (a1 the high bit, a0 the low bit)."""
    return [
        and_(not_(a1), not_(a0)),1
        and_(not_(a1), a0),
        and_(a1, not_(a0)),
        and_(a1, a0),
    ]

the first output is HIGH when both address bits are LOW: AND of two NOT gates. The four lines together cover every combination of a₁ and a₀ with no overlaps and no gaps.

Figure 4.5 shows the structure. The decoder on the left selects one register; on a write, only that register’s load line is asserted. On a read, a 4-to-1 mux per bit picks the addressed word combinationally.

Figure 4.5: The 4-word RAM. Address bits a₁ and a₀ enter a 2-to-4 decoder (left) that raises exactly one of four select lines. The selected register loads the data input when the write signal is HIGH. The read path is combinational: a 4-to-1 mux per bit picks the addressed word without waiting for a clock edge.

With logic, arithmetic, and now memory in hand, the next chapter wires the three into a processor.

Exercises

Add an enable line to the register, so it loads a new value only when enabled and holds otherwise.
The memory holds four words. Widen it to eight. What grows, and what stays the same?

Previous Next

Chapter 4How does it remember?