11The Lookup Table & ROM

Last chapter you ran a real arithmetic program by hand. You set an address, pulsed a clock, enabled a driver, read the bus, and went around again. Two things nagged. First, the machine never showed you its answer. The result sat in a register as a byte, and you had to decode it in your head. Second, the machine couldn't hold its own instructions. You were the program, punching in each step. Both problems have the same answer, and it's a lovely one: a table baked into wires. A seven-segment display feels like it needs cleverness. Surely something has to know that a "4" lights these bars and not those. It doesn't. Each bar is one boolean equation, so the whole display is a table. Here's the bet for this chapter. By the end you will have built a thing you have owned your whole life, a thing with a name you've heard since you were a kid — ROM — and you will not have used one idea you didn't already have. You own the parts already. A decoder, from the RAM chapter. An OR gate, from long before that. What you don't own yet is what happens when you put them together, and it is not what you would guess from the parts. Build it once here, on a display, and you'll have quietly built the thing that will soon be the brain of the whole CPU.

01The bars that show the answer

Start with the thing itself. A seven-segment display is seven little bars arranged in a figure-eight: a top, two shoulders, a waist, two hips, and a foot. Light the right subset and a numeral appears. That's the whole device. There's no chip inside and no intelligence, just seven bars you can switch on and off on their own. Pick a digit below and watch which bars it calls for.

Notice there's nothing mysterious happening. The "4" isn't drawn, it's selected. Turn on the two shoulders, the waist, and the lower-right hip — four bars — leave the rest dark, and your eye does the rest. So the real job isn't drawing at all. It's answering seven small yes-or-no questions, one per bar: for this number, are you on?

So let's isolate one bar and stare at it. Take the top bar and call it segment a. The trade names all seven, and the labelling costs you nothing to learn because the figure always shows it: start at a, the top, and walk clockwise — b is the upper-right, c the lower-right, d the foot, e the lower-left, f the upper-left — and g is the waist across the middle. Now, as you walk the digits 0 through 9, that single bar blinks on and off on its own private schedule: on for 0, off for 1, on for 2, on for 3, off for 4… It doesn't care what the other six are doing. It is its own 1-or-0.

And that is the crack the whole chapter pours through. A display that seemed to need a designer's touch is really seven separate switches. Each one is a function of the number coming in. We don't have to be clever about "the shape of a 4." For each bar we just answer one honest question — which numbers turn you on? — and wire that answer in gates. Seven questions, seven little circuits, done.

02One number in, sixteen lines out

Here's the snag we have to clear first. The number arriving is a nibble: four bits, 0000 to 1111. But segment a doesn't want the raw bits. It wants to know which digit this is, so it can ask "am I in that digit's list?" So we need to turn one 4-bit code into one wire per digit — sixteen wires, of which exactly one is ever hot. You've built this before, in the RAM chapter. It's the decoder.

Except you don't need a decoder, and you should hear the other road named before we take this one. You could sit down with segment a's list and the four raw bits, and grind it into a handful of AND, OR and NOT gates that light the top bar and nothing else. It works. Real chips have done exactly that for decades. And sixteen AND gates to light one bar should make you wince. So wince — then try the next one. Now do segment g: a fresh puzzle, from scratch. Now do a table you haven't met yet — hex letters, a keyboard map, squares. Fresh puzzle again, every time. The cleverness never transfers. That's the trade this whole chapter turns on. Buy the decoder once, get one wire per input code, and every table after that is only a question of which wires you tap. You are spending gates to buy the right to stop thinking.

Recall the mechanism, because we lean on it hard. Each address bit is fanned out two ways: straight, and through a NOT into an inverted rail (the Ā lines). Then one AND gate per output taps exactly the right mix of straight and inverted rails, so it fires for one code and no other. Here's the 2-to-4 version, with the shared inverted rails laid bare.

Two things carry straight over. First, one inverter per input bit feeds every AND gate that needs the low version. You pay for the rails once and share them. Second, the outputs are one-hot: for any input, exactly one line is high, because only one AND term can be satisfied at a time. Now scale it. Slide the decoder wider and watch the arithmetic march in lockstep: one more address bit, twice as many output lines.

Take it to four input bits and you get 2⁴ = 16 output lines, one for every digit code, 0 through 15. Feed in 0100 and line 4 goes hot while the other fifteen stay cold. We now have exactly what segment a asked for: a dedicated wire that means "the number is 4," another that means "the number is 7," and so on. The nibble has become sixteen labelled digit-lines.

03Every bar is an OR

Back to segment a. Write down its honest answer: the list of digits that light it. Walking 0–9, the top bar is on for 0, 2, 3, 5, 6, 7, 8, 9, and dark only for 1 and 4. That list is segment a's truth table, a function from the 4-bit code to a single bit. Here it is, all sixteen rows, nothing hidden.

Now read that table as an instruction for wiring. Segment a should be 1 whenever the number is 0 or 2 or 3 or 5 or…, and you already have a wire for each of those digits. "This or that or that" points straight at one gate. Let's re-meet it before we lean on it.

An OR fires if any of its inputs is high. So the recipe for segment a writes itself: feed the OR the eight digit-lines {0,2,3,5,6,7,8,9}, skip lines 1 and 4, and the output is exactly the bar. When the "4" line is the hot one, none of segment a's eight inputs is live. The OR sits at 0, which is ground, a clean logical zero. The top bar stays dark, which is precisely what a "4" needs.

Drawing that as a fat eight-input OR gate, and then six more beside it, is a mess on the page and wasteful in silicon. So here is the same OR built in wire instead of in gates. Run each digit-line across the page and call it a word-line, because going hot is what selects one whole row of the table. Run one wire down the page per segment and call it a bit-line, because it carries one bit of the answer out. Every place they cross, you have exactly one choice: connect, or don't. Connect through a diode, so current can only shove from the hot word-line onto the bit-line and never backwash into the other rows. Then a hot word-line pulls up every bit-line it's dotted to, and no others. And when none of a bit-line's dotted rows is hot, a pull-down resistor ties it to ground, so it rests at 0 — the same clean zero we just named. That grid of crossings is the OR. Same logic, no gates.

And here's the part that makes it a machine rather than one clever gate: every bar plays the same game on the same sixteen wires. Segment g, the middle waist, has its own list (on for 2,3,4,5,6,8,9; off for 0,1,7). So it's just a different OR tapping a different subset of the exact same decoder lines. Seven bars, seven ORs, one shared decoder feeding them all.

Sit with the shape for a second, because it's the shape of everything that follows. A bank of one-hot lines comes down from the decoder. A grid of ORs reaches across them, each OR picking off the lines it cares about. That grid — a decoder on one axis, ORs on the other — is the whole story. We'll name it properly in a moment.

Before we name it, though, make a prediction — this is the one place in the chapter where guessing first is worth more than reading on. Say you want this exact box to drive a completely different table: which key was pressed, or the square of a nibble, or the hex letters. Stop and decide what has to change inside the machine. Here is the honest answer: nothing. Not the decoder — it only ever says which code came in. Not one OR — an OR has no idea what it's tapping. Not a single gate anywhere. The only thing that changes is which crossings carry a dot. Sit with that, because it's the whole chapter. If the gates are identical for every table, then the gates are not the thing that knows anything. The dots are. The decoder and the ORs are furniture; the dot pattern is the only thing in the box carrying information. Which means you have not built a circuit that works out digits. You've built a circuit that fetches, and the digits are its contents.

04The display decoder, whole

Let's run one number all the way through, slowly, so no step is magic. Feed in 0100. The inverted rails set up, the AND gates resolve, and line 4 goes hot — only line 4. That single hot wire fans into the OR grid. Each segment's OR checks whether line 4 is on its list. The bars that say yes light, the rest stay at ground, and a "4" appears. Step it beat by beat.

That's the entire circuit: nibble → decoder → OR array → bars. Careful with that middle word. The trade calls this whole box a "display decoder" — it decodes a number into a picture, an older and looser use of the word than ours. The decoder in the chain is the strict one: the address decoder, the one-hot part you just built. No memory, no clock, no cleverness — just a pure combinational path from four input bits to seven output bars. It settles as fast as the gates can pass a signal. Now take the wheel. Type any nibble and watch the display draw it live.

Play past 9 and something honest happens. Codes 1010–1111 weren't on anyone's careful list, so the bars light in whatever pattern the wiring happens to give. They still light. The decoder built sixteen lines; only ten were ever thought about, and the other six go hot exactly like their neighbours. Those extra codes are don't-cares: real inputs we simply chose not to design for. But not-designed doesn't mean empty. Something is wired at those crossings, so something comes out — "gibberish" if nobody chose, and here we did choose: those six rows are wired as the hex letters A–F, and that's what you'll see. The circuit isn't broken. It's answering a question we never asked it. A machine like this has no concept of undefined — only of rows.

05A table in silicon

Now step back far enough to see what you actually built, because now it can have its name. Strip away the word "display." What you have is a box where a code goes in and a fixed pattern of bits comes out, and the mapping never changes. Code 4 always yields the same seven-bit word; code 7 always yields its own. That is a lookup table: not a thing that computes, but a thing that remembers an answer for every possible question. The "computation" was done once, by you, when you chose the wiring. One honest note about the grid drawn below: it's shrunk to three address bits and eight rows so the whole thing fits on a page. Yours has four bits and sixteen rows. Nothing else about it changes.

This is the quiet, load-bearing idea of the chapter. Any fixed input→output relationship can be a lookup table instead of a calculation — a display driver, a squaring table, a "which key was pressed" map. You trade cleverness for storage: hold the answer to every input, and you never have to work it out. And a lookup table burned permanently into gates has a name you've heard your whole life without knowing what was inside it — ROM, read-only memory. Cut one open and the "cut" is a joke, because you drew the blueprint an hour ago.

There it is: a ROM is an address decoder feeding an OR array. The address picks one hot word-line. The OR array reads off the bit-pattern wired into that line, and that pattern is the stored word. The seven-segment driver was a 4-bit-address, 7-bit-word ROM the entire time. You just called it a display. This should feel familiar for a deeper reason: it's almost exactly the RAM you built two chapters ago. Look at them side by side.

Same decoder turning an address into one hot line, same array reading out the selected word. The only thing ROM removes is the write path: no data-in, no write-enable, no clocked latches. RAM's contents are set by the wiring of switchable cells you can rewrite. ROM's contents are set by the wiring of the OR array, fixed at manufacture. That shared skeleton is also why both are "random access": any address costs the same as any other, because every one takes the identical decode-then-read path. There's no winding to slot 800 past slots 1 through 799.

That claim deserves one more minute, because at block level you have to take it on trust, and at the cell you can check it. So go down to one cell. In RAM, a cell is a flip-flop, and its bit is ANDed onto the column when its word-line goes hot: the line asks, and the AND valve answers with whatever the loop is holding. Now freeze that flip-flop forever. Frozen at 0, the AND puts nothing on the column no matter which line is hot — a cell that can never contribute is indistinguishable from a missing wire. Frozen at 1, the AND passes the word-line straight through — which is just a wire from the line to the column. Either way, the flip-flop and its valve evaporate. What's left at the crossing is a dot, or nothing. That's the whole deletion: same decoder, same per-column OR, and the storage cell has collapsed into the wiring.

Pull any address and the cost is one decode plus one OR fan-in, whether you asked for line 0 or line 15. That flat, order-free access is what "random access" means, and both machines have it. So the names are a trap. RAM, Random Access Memory, is named for how you reach a slot. ROM, Read-Only Memory, is named for what you may do once you're there. Two different questions — so the pair never sat on one scale. ROM is random-access too. Its name just never mentions it.

06Burning it in, and showing it off

Removing the write path buys something RAM can never have. A RAM cell holds its bit in a feedback loop that only survives while the power is on. Cut the supply and the loop collapses, so the bit is gone. That's volatile. A ROM's bits aren't held by anything active; they are the wiring. Kill the power, restore it, and the answers are exactly where you left them. They were never "held" — they were built. That's non-volatile, and it's why your machine's start-up instructions live in ROM and not RAM. One more thing about that dot, because you're about to meet it wearing several different coats. The idea is only ever "this crossing is connected, or it isn't." Connected can be a diode, a blown fuse, a metal link, or a trapped charge that behaves like one. The decoder and the ORs never ask which. That's the point, not a complication: the picture survives every change of material.

Of course, "fixed at the factory" is a nuisance if you're the one designing the table and you get it wrong. So the family grew a ladder of ever-more-forgiving ways to set those bits. PROM — program it once yourself, by blowing tiny fuses, and then it's permanent. EPROM — erasable, its cells cleared by a dose of ultraviolet light through a little quartz window on the chip. EEPROM — electrically erasable, rewritten in place with no window and no lamp, the ancestor of the flash memory in every phone and drive today. The read structure stays the same the whole way up; only the write-and-erase gets kinder.

One last piece to make the display useful. The nibble reaching our decoder can't be whatever the bus happens to be doing this instant, or the bars would flicker through every intermediate value as the machine works. So we put a register in front of the display. On the clock edge it latches the byte the bus is carrying, and holds it steady while the display decoder reads its low nibble and the OR array draws it. It's the same edge-triggered register you already built — eight flip-flops on a shared clock — doing one dedicated job.

Latch a byte, and the display holds it up to the light until the next tick overwrites it. That's the machine finally showing its answer — the first of the two problems we opened with, solved. Now look back at the little bus computer from last chapter, and its hand-written timing program on the wall.

Look back at the timing table on the wall. Every control-line choice on it comes off a row, and the row is picked by the beat number: this beat asserts these lines, the next beat those. That's a fixed function of the beat — an answer for every case, decided in advance, by you. Beat number in, control lines out. That is an address and a word, and it is nothing else. So the chart on the wall is a table. A table with an answer for every case is a lookup table. Which is a ROM. Which you just built. The human at the control panel is about to be replaced by a pile of decode-and-OR gates — the same pile, pointed at the machine's own controls instead of at a display. That's the brain, and it's furniture you already own.

And that's Chapter 11. You turned "cleverness" into a table, and a table into silicon. A seven-segment display was seven boolean equations. Those equations were a decoder feeding an OR array. That array, frozen, was a ROM — the very RAM you knew, with the writing sawn off, keeping its bits through a power-cut because the bits are the wiring. The machine can show its answer now. But a display is a small use for a table that can map any situation to any response. Point that same table at the machine's own control lines and it runs itself. First, though, the bytes in RAM have to stop being mere numbers and start being commands. That reinterpretation is the next rung: where 00010010 stops meaning "eighteen" and starts meaning "load from address 2."