Programmable Logic and Lookup Tables

Every combinational function built so far in this path — the minimized equations in lesson 2, the muxes and encoders in lesson 3 — has been implemented as custom gates, wired specifically for that one function. Programmable logic takes a different approach: build one fixed, general-purpose piece of hardware once, and specialize it after the fact by configuring which connections are actually present. This lesson looks at that idea at the level every digital design course covers it, then follows it forward to the lookup table (LUT), the structure that makes every modern FPGA a chip made of millions of tiny, independently programmable truth tables.

Reading time: about 8 minutes.

4.1 Two planes, and which one is programmable

Any canonical sum-of-products function, as lesson 2 showed, is an AND-plane producing the minterms, followed by an OR-plane summing the ones that matter. A device built from this shape has exactly two places where a connection can be either present or absent: the connections feeding the AND gates (deciding which input variables, true or complemented, each AND term uses) and the connections feeding the OR gates (deciding which AND-term outputs each OR gate sums). Three classic programmable-logic families differ only in which of these two planes is fixed at manufacture time and which one a designer can still configure.

A PROM's AND plane being fixed is really just another way of saying it generates every minterm of its input width unconditionally, the way an address decoder does — which is why a PROM can implement any function of N inputs at all, but needs 2^N AND gates to do it regardless of how simple the actual function is. A PAL trades that generality for density: letting the designer choose which product terms exist, but committing at manufacture time to a fixed, small number of terms feeding each output, is enough for the great majority of real combinational functions, which rarely need many product terms per output. A PLA keeps both planes programmable and is the most general of the three, but a programmable OR plane costs area and delay that a PAL's fixed one avoids, which is why PALs, not PLAs, ended up as the dominant simple programmable-logic device historically.

4.2 Why this leads to the FPGA LUT

A PROM's defining property — an AND plane that unconditionally generates every minterm, so that the OR plane can be configured to realize literally any function of the input width — is also, looked at differently, a complete truth table with a configurable output column. That observation is exactly what a modern FPGA's basic logic element, the lookup table (LUT), scales down to its smallest practical size and makes fast: a K-input LUT is a tiny piece of configuration memory holding 2^K bits, one output bit per possible input combination, with the K inputs used purely as an address into that memory. There is no AND plane or OR plane left to speak of; the "logic" is just which of the 2^K stored bits matches the input address, exactly the way the ROM module in section 4.3 looks an address up in a stored table.

A 4-input LUT, the size used by older and smaller FPGA families (most current high-end parts use larger, 6-input LUTs), stores 16 configuration bits and can realize any one of the 2^16 possible 4-input Boolean functions simply by loading a different 16-bit pattern — the same AND-plane generality a PROM offered, at a size small enough to tile a chip with hundreds of thousands to millions of them, each independently configured, and wired together by a separately programmable interconnect fabric to build arbitrarily large designs. This is the direct lineage the section's title promises: PROM showed that unconditionally generating every input combination and configuring only the output makes any function reachable; the LUT is that same idea, shrunk to the smallest size that is still useful, repeated across the whole chip.

4.3 ROM-style combinational logic in Verilog

A lookup table implemented in configuration memory inside an FPGA fabric is a piece of hardware this course has no direct way to describe in RTL — it is normally what a synthesis tool maps logic onto. Vendor LUT primitives can be instantiated by name, but that ties the design to one FPGA family, and this course writes portable RTL instead. What a designer can write directly, and what maps naturally onto exactly this idea, is a small combinational ROM: a fixed table of output values selected by an address, written as a case statement.

module rom4x4 (
    input  wire [3:0] addr,
    output reg  [3:0] data
);
    always @(*) begin
        case (addr)
            4'h0: data = 4'h9;
            4'h1: data = 4'h3;
            4'h2: data = 4'hC;
            // ... one line per address ...
            4'hF: data = 4'hB;
            default: data = 4'h0;
        endcase
    end
endmodule

Every one of the sixteen addresses has its own explicit branch, and a default branch is included even though this particular address width leaves no address uncovered — the habit matters more than this one instance, since an incomplete case with no default is the case-statement version of the missing-assignment latch bug from lesson 3: any address not explicitly listed would leave data unassigned on that path, and the synthesis tool would add a latch to hold whatever value it last had. Checked against all sixteen addresses, the simulated output matches the stored table exactly:

OK addr=0 -> data=9
OK addr=5 -> data=0
OK addr=15 -> data=b
ALL TESTS PASSED

Yosys's synthesis of this module shows no sequential cells of any kind — only combinational gates (NAND, AND, OR, XOR and their inverted-input variants, plus one multiplexer) built from the sixteen case branches, confirming the table synthesizes as pure combinational lookup logic, exactly as declaring it inside an always @(*) block with a case on every address promises. On an FPGA target rather than a standard-cell library, a tool would very plausibly map this same case statement directly onto one or more physical LUTs instead of discrete gates — the Verilog does not change; only what it is being mapped onto does.

4.4 Interview questions

What distinguishes a PROM, a PAL, and a PLA? All three share an AND-plane-then-OR-plane structure. A PROM fixes the AND plane (every minterm is always generated) and leaves the OR plane programmable. A PAL leaves the AND plane programmable but fixes the OR plane to a small, constant number of terms per output. A PLA leaves both planes programmable, which makes it the most flexible, but slower and larger per product term than a PAL.

Why can a PROM implement any function of its input width? Because its AND plane unconditionally generates every possible minterm, regardless of which function is actually wanted; the function is selected entirely by which minterms the programmable OR plane happens to sum.

How does a PROM's structure relate to an FPGA's LUT? A LUT is the same idea taken to its smallest practical size: instead of generating every minterm with real AND gates, a K-input LUT stores 2^K configuration bits and uses the K inputs purely as an address into that memory, which is both smaller and faster than a literal AND-plane-then-OR-plane PROM would be at that scale.

What happens if a combinational case statement does not cover every possible address and has no default branch? Any uncovered address leaves the output unassigned on that path, and the synthesis tool infers a latch to hold the previous value instead of the intended combinational logic — the same unassigned-output bug lesson 3 covers for a priority encoder, showing up again in a different syntax.