11.11 FPGA Basics: LUTs, Flip-Flops, Routing, and Configuration Memory
Explain how an FPGA's logic blocks, routing fabric, I/O blocks, clock resources, and configuration memory combine to implement arbitrary digital circuits, and connect this to HDL-described hardware.
A Field-Programmable Gate Array (FPGA) is a programmable logic device built from a large, regular grid of configurable logic blocks connected by a programmable routing fabric, allowing it to implement essentially arbitrary digital circuits — from simple combinational gates up to entire processors — entirely through configuration rather than physical fabrication. Where a PLA/PAL implements a fixed, relatively small number of sum-of-products equations using AND/OR planes, an FPGA takes a fundamentally more general and scalable approach: each logic block is typically built around a small lookup table (LUT) that can implement any Boolean function of a handful of inputs by directly storing its truth table (the same read-only lookup-table concept from the ROM topic, reused here as a tiny reconfigurable function generator), paired with a flip-flop for storing state. Thousands to millions of these LUT+flip-flop blocks are wired together through a programmable routing network, and the entire configuration — every LUT's contents and every routing switch's state — is itself held in configuration memory, which is typically loaded fresh from external nonvolatile storage every time the FPGA powers on, since the configuration memory itself is commonly volatile (SRAM-based) in mainstream FPGA families.
Core concept: LUTs as tiny reconfigurable truth tables
The heart of a typical FPGA logic block is the lookup table (LUT): a small memory (commonly holding 2^k bits for a k-input LUT — a 4-input LUT stores 16 bits, a 6-input LUT stores 64 bits) that directly implements the truth table of whatever Boolean function of its k inputs the configuration data specifies. This is precisely the ROM concept from earlier in this module, shrunk down and repeated millions of times across the chip: the LUT's inputs act as an address, and the LUT's stored configuration bits act as the data — reading out the correct output value for that input combination, exactly like a tiny ROM lookup.
Because a LUT can be configured to compute any function of its inputs simply by changing what is stored in it, an FPGA gains enormous flexibility compared to a PLA/PAL's fixed AND-OR structure — the LUT is not restricted to sum-of-products form at all, it can represent any Boolean truth table directly. Pairing each LUT with a flip-flop lets the same basic block implement either purely combinational logic (using just the LUT) or a piece of sequential logic (registering the LUT's output on a clock edge), giving the building block needed for both combinational functions and state elements like registers and counters, covered earlier in this course.
• LUT (lookup table) — a small configurable memory implementing an arbitrary truth table of a few inputs • Flip-flop — paired with each LUT to register its output, enabling sequential logic • Routing — a programmable interconnect fabric wiring logic block outputs to other logic blocks' inputs • I/O blocks — configurable pads connecting the FPGA's internal fabric to external pins • Clock resources — dedicated low-skew distribution networks for delivering clock signals across the chip • Configuration memory — stores every LUT's contents and every routing switch's state, defining the entire circuit
Step-by-step: from HDL description to running hardware
Step 1: the designer describes the desired hardware behavior in a hardware description language (HDL) such as Verilog — for example, a simple combinational assignment like assign y = a & b; describes a piece of hardware that continuously computes the AND of two signals, not a sequential software instruction executed once. Step 2: synthesis tools translate this HDL description into a network of LUTs, flip-flops, and the connections between them that will implement the described behavior. Step 3: place-and-route tools decide which physical logic block on the FPGA will implement each piece of that network, and program the routing fabric's switches to connect them correctly, respecting timing constraints. Step 4: the resulting bitstream — the full set of LUT contents and routing switch settings — is loaded into the FPGA's configuration memory, typically from external nonvolatile storage at power-up, after which the FPGA's fabric behaves exactly as the original HDL described, with all logic blocks operating in parallel exactly as real dedicated hardware would.
Tricky concept: HDL describes hardware, it does not execute sequentially
The single most important conceptual hurdle for students moving from software to digital design is this: HDL code such as assign y = a & b; is not a sequential instruction that runs once and finishes — it is a description of a piece of hardware (here, an AND gate) that exists continuously and re-evaluates its output the instant either input changes, for as long as the circuit is powered and configured. An entire HDL module describes many such pieces of hardware simultaneously, all operating in parallel, exactly as the many independent logic gates on a real circuit board would — there is no 'line-by-line execution order' the way there is in a software program.
This distinction matters directly for how FPGA logic blocks work: every configured LUT in the fabric is continuously and simultaneously evaluating its stored truth table against its current inputs, all the time, in parallel with every other LUT on the chip — which is exactly why FPGAs can achieve massive parallelism for suitable workloads, and exactly why thinking of an FPGA design as a sequence of steps (the way one would read software) leads to fundamental misunderstandings of how the hardware actually behaves.
FPGA logic block and configuration notation
Basic FPGA logic block (simplified):
k-input LUT → stores 2^k configuration bits (the function's truth table)
Flip-flop → optionally registers the LUT's output on a clock edge
Routing → programmable switches connect this block's output to others' inputs
Configuration memory:
Holds ALL LUT contents + ALL routing switch settings for the whole chip
Commonly SRAM-based → volatile → reloaded from external nonvolatile
storage (e.g. Flash) on every power-upCode Examples
This directly connects the FPGA LUT concept back to the ROM topic: a LUT is functionally a tiny ROM, addressed by its input signals, whose stored contents (here, 4 bits) fully define the Boolean function it implements.
A LUT is a miniature ROM: its inputs form an address, and its stored configuration bits are the looked-up data.
This single line describes a continuously-active piece of hardware — an AND gate — not a one-time software statement. Synthesis tools map this description onto one FPGA logic block's LUT, programming that LUT's 4 configuration bits exactly as shown in the worked example above.
assign y = a & b; describes hardware that exists and operates continuously, evaluated whenever a or b changes.
Common mistake: Reading assign y = a & b; as if it 'runs once' like a software assignment statement — in HDL it describes a persistent, continuously-evaluated hardware connection.
Target function: y = a & b (2-input AND)
A 2-input LUT stores 2^2 = 4 configuration bits, one per input combination:
a b | y (stored LUT content)
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1
Configuration bits loaded into this LUT: 0,0,0,1 (in address order 00,01,10,11)
At runtime: applying (a,b) to the LUT's inputs is exactly a ROM-style address
lookup — the LUT returns the stored bit for that address as output y.assign y = a & b;FPGA fabric overview
Logic blocks (LUT + flip-flop) are the repeated unit; the routing fabric and configuration memory together let the same physical chip implement essentially any digital circuit.
┌────┐ ┌────┐ ┌────┐
│ LB │───│ LB │───│ LB │ LB = Logic Block (LUT + flip-flop)
└─┬──┘ └─┬──┘ └─┬──┘
│ Programmable │
│ routing fabric │
┌─┴──┐ ┌─┴──┐ ┌─┴──┐
│ LB │───│ LB │───│ LB │
└────┘ └────┘ └────┘
▲ ▲
│ I/O blocks (chip pads) │
└──────────────────────────┘
Configuration memory (chip-wide) → defines every LUT's contents
and every routing switch's stateImportant Rules
An FPGA logic block typically pairs a lookup table (LUT) with a flip-flop, supporting both combinational and sequential logic.
A k-input LUT stores 2^k configuration bits and can implement any Boolean function of its k inputs — functionally a tiny ROM.
The programmable routing fabric connects logic block outputs to other logic blocks' inputs, I/O blocks, and clock resources.
Configuration memory holds the entire chip's LUT contents and routing state; in SRAM-based FPGAs it is volatile and reloaded at every power-up.
HDL describes hardware that exists and operates continuously and in parallel — it is not executed sequentially like software.
Where FPGAs are used
FPGAs are used wherever custom digital hardware behavior is needed but a full custom chip (ASIC) is not economical or fast enough to develop: high-speed signal processing, network packet processing, hardware prototyping before committing to an ASIC, video processing pipelines, and reconfigurable accelerators in data centers, all take advantage of the FPGA's ability to be reconfigured for a new circuit design without any physical fabrication change.
Reading HDL code (e.g. assign y = a & b;) as if it executes once, top to bottom, like an ordinary software program.
Understand HDL as describing persistent hardware: every assignment describes a circuit element that continuously re-evaluates whenever its inputs change, with all such elements operating in parallel.
This is exactly the tricky point the source material highlights: 'HDL describes hardware; it is not executed sequentially like ordinary software' — misreading HDL as sequential software logic is one of the most common and consequential misunderstandings for newcomers to digital design.
[tricky] According to the course material's tricky-problem note, what is the key misunderstanding to avoid when reading HDL like assign y = a & b;? A. Thinking the & operator performs a logical (not bitwise) AND B. Thinking that HDL describes hardware that executes sequentially, step by step, like ordinary software, when it actually describes a continuously-operating piece of hardware C. Thinking that assign can only be used for arithmetic operations D. Thinking the FPGA cannot implement AND gates
B. Thinking that HDL describes hardware that executes sequentially, step by step, like ordinary software, when it actually describes a continuously-operating piece of hardware — The source material states this directly: 'HDL describes hardware; it is not executed sequentially like ordinary software.' An HDL statement describes a persistent circuit element that is always active and continuously re-evaluates its output as its inputs change — a fundamentally different execution model from a software program's sequential instruction stream.
[interview] What is the functional relationship between an FPGA's lookup table (LUT) and the ROM concept covered earlier in this module? A. They are unrelated — LUTs use flip-flops, ROMs do not B. A LUT is functionally a tiny ROM: its inputs act as an address, and its stored configuration bits act as the looked-up data, directly implementing a truth table C. A LUT is a programmable AND-OR array, identical to a PLA D. A LUT can only store data, never logic functions
B. A LUT is functionally a tiny ROM: its inputs act as an address, and its stored configuration bits act as the looked-up data, directly implementing a truth table — An FPGA LUT reuses exactly the address-in/data-out lookup-table model introduced with ROM: a k-input LUT stores 2^k configuration bits, and applying an input pattern to the LUT is functionally identical to applying an address to a small ROM — the stored bit at that address is returned as the LUT's output, which is precisely how a LUT implements an arbitrary Boolean truth table.
Explain why a 4-input LUT can implement any possible 4-input Boolean function, and state how many distinct configuration-bit patterns (and therefore distinct implementable functions) a 4-input LUT has.
A 4-input LUT has 2^4 = 16 possible input address combinations, and it stores one output bit for each — a 16-bit truth table. Because every one of those 16 output bits can be independently set to 0 or 1 during configuration, there are 2^16 = 65,536 distinct bit patterns that could be loaded into the LUT, meaning it can be configured to implement any one of the 65,536 possible 4-input Boolean functions — literally every function of 4 binary inputs is representable, since a truth table is the most general possible description of a Boolean function.
Think of the LUT as a tiny ROM: how many address combinations does 4 inputs give, and how many different data patterns can be stored across those addresses?