LUTs and the FPGA Fabric

You have spent two modules writing and verifying RTL — including proving properties about it — for hardware that does not exist yet. This module is where the text finally becomes a working chip, and it becomes one today, on your desk, for the price of a development board. The trick is a device called an FPGA — a field-programmable gate array — and the trick behind the trick is one of the loveliest ideas in digital design: a memory can impersonate any logic gate. An FPGA is a chip built almost entirely out of small memories and programmable wires; load the right bits into them and the chip becomes your circuit. It is, quite literally, RAM pretending to be hardware.

The lookup table: a truth table you can write to

Recall what a truth table is: the complete job description of a logic function. A function of k inputs has 2^k rows, and one output bit per row — the whole function is just those 2^k bits. So here is the idea: build a tiny memory with 2^k one-bit cells, and wire the k inputs as its address. Reading the memory looks up the row; the bit that comes out is the function's answer. That device is a lookup table (LUT), and it can be any k-input function whatsoever — you just fill in a different column of bits.

Work one example by hand. A 2-input LUT holds 2^2 = 4 bits. Fill it with 0,0,0,1 (rows 00, 01, 10, 11) and it is an AND gate. Refill the same four cells with 0,1,1,1 and the same silicon is now an OR gate; with 0,1,1,0 it is XOR. Nothing about the wiring changed — only the stored bits. Count the possibilities: 4 bits give 2^4 = 16 fillings, which is exactly every 2-input Boolean function that exists. In general a k-input LUT covers all 2^{2^k} functions of k inputs — for the LUT6 (six inputs, 64 bits) that modern FPGAs use, that is 2^{64} \approx 1.8 \times 10^{19} different gates one component can impersonate.

How the lookup actually happens

Physically, the "memory read" is a tree of multiplexers. The stored bits sit in a column of SRAM cells; each input variable controls one layer of 2:1 muxes, halving the candidates until a single bit reaches the output. Step through the layers:

Notice that the inputs never touch the stored bits — they only steer. Change the inputs and a different stored bit is routed to y within a couple of gate delays; change the stored bits and the LUT becomes a different gate entirely. That second kind of change is what "programming" an FPGA means, and it happens once, at configuration time.

Be the silicon: one LUT, two circuits

A LUT is a five-line data structure. Here is one in TypeScript, configured first as a 3-input XOR (parity), then as the majority voter from Module 1 — the identical hardware, told to be two different gates:

// A LUT is just a tiny memory: the truth table, one bit per row. class LUT { table: number[]; constructor(table: number[]) { this.table = table; } read(inputs: number[]): number { let addr = 0; for (const bit of inputs) addr = addr * 2 + bit; // the inputs ARE the address return this.table[addr]; } } function printTable(name: string, lut: LUT) { console.log(`${name} a b c | y`); console.log(" ------+--"); for (let a = 0; a <= 1; a++) for (let b = 0; b <= 1; b++) for (let c = 0; c <= 1; c++) console.log(` ${a} ${b} ${c} | ${lut.read([a, b, c])}`); } // The SAME hardware, two different configurations: const xor3 = new LUT([0, 1, 1, 0, 1, 0, 0, 1]); // parity of three bits const majority = new LUT([0, 0, 0, 1, 0, 1, 1, 1]); // the 2-of-3 voter printTable("XOR3", xor3); console.log(""); printTable("MAJ3", majority); console.log("\nSame silicon, two circuits - only the table contents changed.");

Try editing a table — flip one bit of xor3 and rerun. You have just done, in miniature, exactly what a bitstream does to the real chip.

From one LUT to a fabric

One LUT is a gate; an FPGA needs hundreds of thousands, plus state, plus wiring. The architecture stacks up in three layers:

The tile. LUTs are grouped with flip-flops (so each LUT's output can be registered — there is your always_ff) and fast carry chains (dedicated ripple wiring, because building an adder's carry out of general LUTs would be painfully slow). Vendors call the bundle a CLB (configurable logic block) or slice; a typical one holds four to eight LUT6s with their flip-flops.
The routing. Tiles sit in a huge regular grid, and between them runs a programmable sea of wires: horizontal and vertical wire segments meeting at switch matrices — crossroads full of tiny transistor switches, each controlled by its own SRAM bit. Open and close the right switches and any LUT's output can reach any other LUT's input. Here is the number that surprises everyone: most of an FPGA's die area is routing, not logic. The gates are cheap; the universal wiring to connect them any way you like is what you are really paying for.
The configuration. Every LUT bit and every switch bit is an SRAM cell, and all of them are chained together. At power-up the chip shifts in one enormous bitstream — millions of bits, produced by the tools from your RTL — that fills every table and sets every switch. When the last bit lands, the fabric is your circuit, and it runs as genuine parallel hardware: no instructions, no fetch, just gates and wires.

And because those cells are RAM, not ROM, the whole personality is volatile: pull the power and the circuit evaporates, leaving blank fabric that must be reconfigured at next boot (boards keep the bitstream in a little flash chip for exactly this reason). Reconfigure with a different bitstream and the same board is a different machine — that is the superpower the rest of this module builds on.

a k-input LUT is a 2^k-bit truth-table memory addressed by its inputs — it can implement any of the 2^{2^k} possible k-input functions;
a CLB/slice bundles LUTs with flip-flops and carry chains — logic, state and arithmetic in one tile;
tiles sit in a grid threaded by programmable routing (wire segments + switch matrices), which occupies most of the die;
configuration shifts a bitstream into SRAM cells that set every table and every switch: the FPGA is RAM pretending to be a circuit, and forgets it at power-off.

FPGA sizes are quoted in LUT count the way engines are quoted in horsepower: a hobby part has ~20 thousand, a mid-range part a few hundred thousand, and the monster parts used to emulate entire GPUs pass a few million — with price tags to match (the biggest cost more than a car). As for why the industry settled on six inputs: it is a genuine optimisation, not a round number. Table size grows as 2^k, so each extra input doubles the silicon per LUT — but bigger LUTs swallow more logic each, so a signal crosses fewer LUTs (and, crucially, fewer stretches of slow routing) on its way through the circuit. Small-k fabric is cheap but slow; big-k fabric is fast but mostly wasted table bits. Academic studies in the 2000s put the sweet spot at 4–6, and as transistors got cheaper the answer drifted up from the LUT4s of the 1990s to today's LUT6 — where it has now sat for nearly twenty years.

The word "programmable" in FPGA sets a trap. Loading a bitstream is configuration, not execution: the bits do not run — they set switches. There is no processor fetching them, no program counter, no instructions, no "speed" at which the bitstream executes; after configuration the bitstream's job is over, and what remains is a plain electrical circuit whose gates all work simultaneously, exactly like the hand-wired hardware of Module 1. The confusion has real consequences: newcomers ask "how fast does the FPGA run my code?" (it doesn't — it is your circuit, running at whatever clock the logic can sustain) or expect to single-step it like a debugger (you attach a logic analyser instead). When you want something that genuinely executes instructions on an FPGA, you configure a processor circuit into the fabric and run software on that — a delightful trick with its own lesson later in this module.