By the end of this chapter you should be able to:
- Explain why a ROM addressed by logic signals implements an arbitrary function of its address lines, and compute the ROM size needed for an n-input, m-output function.
- Describe the PLA, in which both the AND and the OR array are programmable, and read or draw a programmed array in the standard dot notation.
- Explain what a PAL gives up by fixing its OR array, and why that loss of flexibility buys speed and a cheaper programming step.
- Implement a given set of Boolean functions on a PLA and on a PAL, and write out the programming table in each case.
- Describe the CPLD as PAL-like blocks of macrocells joined by a central interconnect matrix, and say why its pin-to-pin timing is predictable.
- Explain why a k-input look-up table realises any function of k variables, and describe the flip-flop and routing fabric that surround it in an FPGA.
- Follow a design from HDL source through synthesis, mapping, placement, routing and timing analysis to a configuration bitstream.
Chapter 27 organised storage cells so that any one of them could be reached by an address, and treated the result as memory: you write a word, later you read it back. Look at the same circuit with a designer's eye rather than a programmer's and something else is going on. The address decoder produces one active line for every combination of the address bits, which is exactly the list of minterms of Chapter 7; the storage array decides, for each of those minterms, whether each output bit is 1 or 0. A ROM addressed by logic signals is therefore not remembering anything — it is computing, and it computes whatever function you stored in it.
That observation is the root of every device in this chapter. Once logic can be produced by filling in an array rather than by wiring gates, the interesting question stops being "which gates?" and becomes "which parts of the array should be programmable, and which should be fixed to save silicon and delay?" The answers form a ladder — ROM, PLA, PAL, CPLD, FPGA — along which flexibility is traded against area, speed and cost. This chapter climbs that ladder, sizes each device honestly, programs the same small function set on both a PLA and a PAL, and ends with the flow that turns the text description of Chapter 30 into configuration bits.
1 The ROM as a Look-Up Table
A ROM with \(n\) address lines and \(m\) data lines contains an \(n\)-to-\(2^n\) decoder driving an array of \(2^n\) words of \(m\) bits. Chapter 18 showed that such a decoder asserts exactly one output line for each input combination, and Chapter 7 called those combinations minterms. So the decoder inside a ROM generates every minterm of the \(n\) address variables, all \(2^n\) of them, whether you want them or not. The stored array then selects, for each output bit, which minterms contribute — which is precisely the definition of a sum-of-minterms expression. The word stored at address \(k\) is the row of the truth table for input combination \(k\).
A ROM used this way is called a look-up table: the circuit does no arithmetic and no logic in the ordinary sense, it simply looks up the answer that was written down in advance. Because the decoder is complete, any function of the \(n\) address variables can be stored, and any \(m\) functions can be stored simultaneously, one per output bit. There is no minimisation to do. The K-maps of Chapter 8 and the tabular method of Chapter 9 exist to reduce gate count, and a ROM has no gate count to reduce — a function needing two product terms occupies the same silicon as one needing two hundred.
The size follows immediately. An \(n\)-input, \(m\)-output combinational function needs
The number of inputs sits in the exponent. Each extra input variable doubles the device; four extra input variables multiply it by sixteen.
(a) A circuit accepts a 4-bit unsigned binary number and outputs its square. The largest input is \(1111_2 = 15\) and \(15^2 = 225\), which needs \(\lceil \log_2 226 \rceil = 8\) output bits. With \(n = 4\) and \(m = 8\),
A 128-bit ROM replaces the whole array multiplier of Chapter 17 for this word length, and does it in one access time.
(b) A BCD-to-seven-segment decoder has four inputs and seven outputs, so \(2^4 \times 7 = 112\) bits. Chapter 18 built the same function from gates after a six-way don't-care minimisation; the ROM version needs no minimisation at all, and the six unused codes are simply stored as whatever blanking pattern you prefer.
(c) Now suppose the same style is used for a function of sixteen variables with eight outputs: \(2^{16} \times 8 = 524\,288\) bits, or 64 kB, and a decoder with 65 536 output lines. The function may well be expressible in forty product terms. The ROM does not care, and that is its weakness.
Part (c) is why the rest of this chapter exists. Real logic functions are sparse: a control decoder with sixteen inputs has a few dozen product terms, not 65 536, yet the ROM pays for every minterm because its AND plane was fixed at manufacture as a complete decoder. Program the AND plane instead, so that it produces only the terms actually needed, and the array shrinks from exponential in \(n\) to linear in the number of terms. That is the PLA.
A ROM is a two-level AND–OR network whose AND plane is fixed as a full decoder and whose OR plane is the programmable memory array. It implements any \(m\) functions of \(n\) variables in \(m\,2^{n}\) bits, with a propagation delay equal to the access time and independent of how complicated the functions are.
2 The PLA: Both Arrays Programmable
A programmable logic array keeps the two-level AND–OR structure but makes both planes programmable and, decisively, makes the number of product lines a design parameter rather than \(2^n\). A PLA is specified by three numbers: \(n\) inputs, \(k\) product terms and \(m\) outputs. Every input enters the AND plane in both true and complemented form, so there are \(2n\) vertical lines crossing \(k\) horizontal product lines; in the OR plane those \(k\) product lines cross \(m\) output columns. The number of programmable links is therefore
Linear in every one of \(n\), \(k\) and \(m\). Nothing is exponential, because the designer chooses \(k\) to suit the function rather than being handed \(2^n\).
Compare the sixteen-variable case of Worked Example 28.1(c). A PLA with \(n = 16\), \(k = 48\) and \(m = 8\) has \(2 \times 16 \times 48 = 1536\) AND-plane links and \(48 \times 8 = 384\) OR-plane links, 1920 in all, against 524 288 bits for the ROM — a factor of 273. The PLA wins because it stores the function in the form the function actually has, a short list of product terms, instead of enumerating every input combination.
The second advantage is sharing: a product line is one horizontal wire that may be dotted into as many output columns as you like, so a term used by three output functions costs one product line, not three. In a PAL, as the next section shows, that is impossible.
Programmed arrays are drawn in dot notation because drawing the individual AND and OR gates for a device with fifty product terms would be unreadable. The convention is simple. Each product line is shown as the input of one AND gate and each output column as the input of one OR gate; a dot at a crossing means the link there is intact, so that signal is included in the term, and a bare crossing means the link is absent. A product line with dots at \(A\) and \(B\) is the term \(AB\); the vertical lines it does not touch are simply not in the term. In the OR plane, a dot where product line \(P_2\) crosses output column \(F_1\) means \(P_2\) is one of the terms summed into \(F_1\).
Most PLAs also give each output a programmable inversion, drawn as an XOR gate with one input tied to a fuse. It costs one bit and often saves several product terms, because a function with many 1s has few 1s in its complement, so it is worth minimising both \(F\) and \(F'\) before committing.
Implement
Minimising \(F_2\) on a three-variable map gives \(F_2 = AB + AC + A'B'C'\). Minimising \(F_1\) directly gives \(F_1 = A'B' + A'C' + B'C'\) — three terms that share nothing with \(F_2\), so the pair would need six product lines. But \(F_1\) has four 1s and four 0s, so try the complement. Grouping the zeros of \(F_1\), which sit at 3, 5, 6 and 7, gives
and now \(AB\) and \(AC\) are common to \(F_1'\) and \(F_2\). Storing \(F_1'\) in the array and programming the output XOR of \(F_1\) to invert costs one configuration bit and saves two product lines. The whole job needs four:
| Product term | A | B | C | F1 (C) | F2 (T) |
|---|---|---|---|---|---|
| 1 \(AB\) | 1 | 1 | – | 1 | 1 |
| 2 \(AC\) | 1 | – | 1 | 1 | 1 |
| 3 \(BC\) | – | 1 | 1 | 1 | – |
| 4 \(A'B'C'\) | 0 | 0 | 0 | – | 1 |
This is the standard PLA programming table, and it is what you would hand to the programming software. In the input columns a 1 means the true line is dotted, a 0 means the complemented line is dotted, and a dash means neither — the variable is absent from the term. In the output columns a 1 means the product line is dotted into that output, a dash means it is not. The (T) or (C) beside an output name says whether that output is taken true or complemented.
Check it at \(ABC = 011\): only \(P_3\) is 1, so the array gives 1 on \(F_1\)'s column and the inverting pin delivers \(F_1 = 0\), while \(F_2 = 0\) — and 3 is in neither minterm list.
The device used is a 3 × 4 × 2 PLA: \(2 \times 3 \times 4 = 24\) AND-plane links plus \(4 \times 2 = 8\) OR-plane links, 32 in all. Figure 28.2 shows it programmed.
3 The PAL: A Fixed OR Array
Programmable links are not free. Each one is a fuse, an antifuse or a floating-gate cell sitting in series with the signal, contributing resistance, capacitance and, in the fuse technologies, a voltage drop. A PLA puts two such elements in every signal path, one in the AND plane and one in the OR plane, and the second of them is on the wide-fan-in OR line where the capacitance is already worst. Testing suffers too: an unprogrammed PLA is a blank device whose two arrays must both be verified.
The programmable array logic device, introduced by Monolithic Memories in 1978, removes the second layer. Its AND plane is programmable exactly as in a PLA, but its OR plane is fixed at manufacture: each output OR gate is permanently wired to its own private group of product lines — typically seven or eight of them — and to no others. You choose what each product term is; you do not choose where it goes.
What that costs is sharing. In a PAL a product term belongs to exactly one output, so a term needed by three outputs must be generated three times, occupying three product lines. What it buys is threefold. The signal passes through one programmed element instead of two, so propagation delay falls — classic bipolar PALs achieved 15–25 ns pin to pin where comparable PLAs were nearer 40–50 ns. The die is smaller, because the OR plane is metal rather than an array of programmable cells. And the timing is far easier to characterise, because every path through the device has the same structure: one AND-plane crossing, one OR gate, one output buffer.
Implement the \(F_1\) and \(F_2\) of Worked Example 28.2 on a PAL having three inputs and two outputs, each output OR gate hard-wired to four product lines.
The trick that saved two product lines on the PLA is unavailable, because the two outputs cannot reach the same product line however the array is programmed. Each function must be built from scratch inside its own group, so both are used in true form and minimised separately:
| Output | Product line | A | B | C | Term |
|---|---|---|---|---|---|
| \(F_1\) | 1 | 0 | 0 | – | \(A'B'\) |
| 2 | 0 | – | 0 | \(A'C'\) | |
| 3 | – | 0 | 0 | \(B'C'\) | |
| 4 | 0,1 | 0,1 | 0,1 | unused — all links intact, term = 0 | |
| \(F_2\) | 5 | 1 | 1 | – | \(AB\) |
| 6 | 1 | – | 1 | \(AC\) | |
| 7 | 0 | 0 | 0 | \(A'B'C'\) | |
| 8 | 0,1 | 0,1 | 0,1 | unused — all links intact, term = 0 |
Six product lines are occupied against the PLA's four, and two of the eight available lines are left over. An unused line must not simply be abandoned: with every link blown it would be an AND of nothing, which reads as a permanent 1 and would jam its output high. The convention is the opposite one — leave all links on that line intact, so the term becomes \(A \cdot A' \cdot B \cdot B' \cdot C \cdot C' = 0\) and contributes nothing to the OR. That is why the two unused rows above show every input connected.
The comparison in one line: PLA, four product terms and one output inversion; PAL, six product terms, no inversion needed, and a device that is simpler, cheaper and roughly twice as fast.
Commercial PALs are named by their pin function. A PAL16L8 has up to sixteen array inputs and eight active-Low combinational outputs, with 64 product lines crossing 32 vertical lines (sixteen inputs, true and complement), giving \(64 \times 32 = 2048\) links in the AND array. A PAL16R8 replaces the eight combinational outputs by eight D flip-flops on a common clock pin, which is what lets a PAL hold the state machines of Chapter 26. Later parts wrapped each output in an output logic macrocell whose own bits choose registered or combinational, true or inverted; the erasable version is the GAL, and its macrocell is the direct ancestor of the CPLD macrocell below.
4 CPLD Architecture: Macrocells and the Interconnect Matrix
A PAL runs out of room in two ways at once: it has too few product terms and, long before that, too few pins. Putting four PALs on a board and wiring them together works, but the wiring is fixed and the board is large. The complex programmable logic device puts several PAL-like blocks on one die and — the essential step — replaces the board wiring with a programmable interconnect.
The unit of resource is the macrocell. Each one owns a small cluster of product terms, typically four or five, feeding an OR gate; an XOR that inverts the sum or not under one configuration bit, so both \(F\) and \(F'\) are cheap; a flip-flop configurable as D or T; a multiplexer choosing the registered or the combinational value; a tri-state output buffer with its own product-term enable; and a feedback path back into the interconnect whether or not the value reaches a pin. A macrocell is, in other words, one bit of state plus the logic that computes its next value — the exact unit the state-machine design procedure of Chapter 26 produces.
Macrocells are grouped, typically sixteen at a time, into a logic array block that shares one product-term array. A device with four such blocks has \(4 \times 16 = 64\) macrocells and, at five product terms each, 320 product terms; the classic EPM7128 has eight blocks and 128 macrocells. Because a function occasionally needs more than five terms, blocks provide expander or steering logic that lends unused product terms from neighbouring macrocells, at the cost of one extra pass through the array and so one extra increment of delay.
The blocks are joined by a programmable interconnect matrix, a single large crossbar-like switch that every block writes into and every block reads out of. Its importance is not that it saves wire but that it makes delay predictable. Any signal travelling from any macrocell to any other crosses the matrix exactly once, so the pin-to-pin propagation delay is the same number — the \(t_{PD}\) quoted on the data sheet, say 5 ns — regardless of which macrocells the fitter happened to choose. Compare that with the FPGA of the next section, where a path may cross a dozen switch boxes or two, and the delay is not known until after routing. Deterministic timing is the CPLD's real selling point, and it is why CPLDs still appear as board-level glue, address decoders and power-up sequencers long after FPGAs took over the large designs.
Two practical consequences follow from the technology. CPLD configuration is stored in EEPROM or Flash cells on the die itself, so the device is non-volatile and functional within microseconds of power-up — which matters when the CPLD is what releases everything else from reset. And because every product term is a wide AND across the array, a CPLD draws real static current — tens of milliwatts doing nothing, where the CMOS gates of Chapter 14 would draw almost none.
5 The FPGA: Look-Up Tables, Flip-Flops and Routing
The product-term array does not scale. Doubling the inputs to a wide AND doubles the capacitance on every product line, and the static current of a large array grows with it. The field-programmable gate array, introduced by Xilinx in 1985, abandons the array altogether and goes back to the idea of Section 1 — the look-up table — but shrinks it until it is small enough to replicate thousands of times.
A \(k\)-input LUT is a \(2^k\)-bit memory whose address lines are the \(k\) logic inputs and whose single data output is the function value. Physically it is \(2^k\) SRAM cells feeding a \(2^k\)-to-1 multiplexer — precisely the multiplexer-based function implementation of Chapter 19, with the truth-table column held in configuration cells instead of being wired to \(V_{CC}\) and ground. For \(k = 4\):
The 16 stored bits are the output column of a four-variable truth table. Writing any of the \(2^{16}\) possible columns into them realises the corresponding function, so a single 4-LUT implements every four-variable function there is — including ones nobody has a name for.
The argument is worth stating carefully because students often expect a catch. A function of four variables is defined by its truth table, that table has sixteen rows, and the LUT stores sixteen bits, one per row; presenting \(abcd\) selects the bit for that row. The LUT therefore does not build the function from smaller pieces — it is the function, tabulated. Two consequences follow: no minimisation happens inside a LUT, and the delay is the same for every function, roughly 0.1–0.3 ns, because it is a multiplexer delay and not a gate network's. A four-input XOR, four gate delays in Chapter 5's technology, is one LUT delay here.
Why four? A \(k\)-LUT costs \(2^k\) configuration bits and \(2^k - 1\) multiplexer stages, so cost grows exponentially while the extra logic captured grows slowly. Four gave the best area–delay product for many years; six-input LUTs (64 bits, \(2^{64} \approx 1.8 \times 10^{19}\) functions) became worthwhile once interconnect rather than logic dominated the delay, since a fatter LUT swallows logic that would otherwise need a second LUT and a wire between them.
A LUT alone is combinational, so each logic block pairs it with a D flip-flop and an output multiplexer that selects the registered or the unregistered value under one more configuration bit. That single pairing is enough to build everything in Part 5: the flip-flop holds the state, the LUT computes the next-state and output functions. Real blocks add a dedicated carry chain — a hard-wired ripple path between vertically adjacent blocks — because the carry-look-ahead logic of Chapter 16 built out of LUTs and general routing would be slower than a short dedicated wire, and adders are everywhere.
Between the blocks lies the routing fabric: horizontal and vertical channels of metal segments, connection boxes that attach a block's pins to nearby segments, and switch boxes at the channel crossings that join segments into longer paths. Every one of those junctions is a pass transistor controlled by a configuration bit. The fabric is the reason an FPGA is large and its timing is not known in advance: interconnect typically occupies more than half the die area and contributes the majority of the delay on a critical path, and how much delay depends entirely on where the router put things. It is also why an FPGA design that fits comfortably can still fail to meet its clock period.
SRAM configuration cells are volatile, so an FPGA wakes up blank and must be loaded from an external Flash at every power-up. The bitstream is large: twenty thousand 4-LUTs need \(20\,000 \times 16 = 320\,000\) bits for their contents alone, before one routing switch is counted, and real bitstreams run to tens of megabits.
6 From HDL Description to Configuration Bits
Nobody programs a modern device by filling in a table of links. The design is written in a hardware description language — VHDL, the subject of Chapter 30, or Verilog — and pushed through a tool chain that ends in a file of configuration bits. The stages are worth knowing individually, because each one can fail in its own way and the error messages assume you know which stage produced them.
- Analysis and elaboration. The source is checked for language errors and the component hierarchy is flattened. Errors here are syntax, nothing to do with hardware.
- Synthesis. The description is inferred into a generic netlist of gates, flip-flops, adders and multiplexers. This is the stage that decides your
ifstatement was a multiplexer and yourprocesswas a register, and it is the stage that will silently give you a latch if you write the code badly — Chapter 30 returns to this. - Technology mapping. The netlist is packed into the resources the chosen device has: groups of gates become LUT contents, registers become logic-block flip-flops, wide functions are split across several LUTs. On a CPLD the same step packs logic into macrocells and product terms.
- Placement. Each mapped block is assigned to a physical site on the die. The placer tries to put connected blocks near one another, because on an FPGA distance is delay.
- Routing. The switches that connect the placed blocks are chosen. Routing can fail outright on a congested device even when there is plenty of unused logic.
- Static timing analysis. With real wire delays known, every flip-flop-to-flip-flop path is checked against the setup and hold requirements of Chapter 21 at the declared clock period. It is an exhaustive algebraic check, not a simulation, so it cannot miss a path your test vectors never exercised.
- Bitstream generation. The result is serialised into the device's own format and loaded: into Flash on a CPLD, into SRAM from a configuration memory on an FPGA.
Two inputs sit alongside the source and matter as much. The constraints file declares the clock period, the pin each port appears on and the electrical standard it uses; without a declared clock the timing analyser has nothing to check against and reports success on a design that cannot run. A test bench, also written in the HDL, drives the design in simulation before synthesis and again after routing with real delays back-annotated.
The habit that matters is to treat HDL as a description of hardware rather than as a program: every construct becomes LUTs, flip-flops and wires on a die whose structure this chapter has described. A designer who knows a logic block holds one 4-LUT and one flip-flop can read a synthesis report of "3 412 LUTs, 1 205 registers" and tell at a glance whether the tool understood the design.
7 Summary and Key Results
| Device | AND plane | OR plane | Size or cost | What it is good for |
|---|---|---|---|---|
| ROM as LUT | Fixed: full \(n\)-to-\(2^n\) decoder | Programmable (the stored array) | \(m\,2^{n}\) bits; 16 × 8 = 128 bits for a 4-bit squarer | Any function of a few variables; code conversion; no minimisation needed |
| PLA | Programmable | Programmable | \(2nk + km\) links; 1920 for 16 × 48 × 8 against 524 288 ROM bits | Many outputs sharing product terms; sparse functions of many variables |
| PAL | Programmable | Fixed groups of 7–8 product terms | \(2nk\) links only; PAL16L8 has 64 × 32 = 2048 | Fast two-level logic; one programmed element in the path |
| CPLD | Programmable, per block | Fixed, inside each macrocell | 64–512 macrocells; 4–5 product terms each, expandable | Glue logic and state machines needing guaranteed pin-to-pin delay |
| FPGA | No array at all | No array at all | \(2^{k}\) SRAM bits per \(k\)-LUT; a 4-LUT covers all \(2^{16}\) four-variable functions | Large designs, datapaths, anything needing thousands of registers |
| Sharing | PLA yes, PAL no | — | Example 28.2 needs 4 product terms on a PLA, 6 on a PAL | The single clearest difference between the two architectures |
| Design flow | — | — | HDL → synthesis → mapping → placement → routing → timing → bitstream | Each stage has its own failure mode; timing is checked after routing, not before |
8 Common Mistakes
A ROM has no product terms to count. Its size is set entirely by the number of input variables and output bits, \(m\,2^{n}\) bits, and a function needing three terms occupies exactly as much silicon as one needing three hundred. The corollary trips people the other way as well: minimising a function before storing it in a ROM saves nothing at all, because every minterm has a stored bit whether it is 1 or 0.
Sharing is what the PLA's programmable OR plane is for. In a PAL each OR gate is hard-wired to its own private group of product lines, so a term appearing in two output functions must be generated twice, once in each group. A design that fits a PLA in \(k\) terms may need considerably more than \(k\) on a PAL, and a beginner who assumes otherwise will produce a fitting report that does not match the expectation.
Left with no connections, a product line is an AND gate with no inputs asserted low, which reads as a constant 1 and forces its output permanently High. The convention is the reverse: leave every link on an unused line intact, so the term includes both \(A\) and \(A'\) and evaluates to a constant 0, which contributes nothing to the OR gate it feeds.
9 Chapter Review
1. A circuit takes a 4-bit binary number and a 1-bit mode signal, and produces the number's square when the mode is 0 and its 2's complement when the mode is 1. Size a ROM for it, and compare that with the size if the mode signal were removed.
The inputs are the four data bits plus the mode bit, so \(n = 5\). The widest output is the square, whose maximum is \(15^2 = 225\), needing 8 bits; the 2's complement of a 4-bit number needs only 4 bits and is zero-extended into the same field. So \(m = 8\) and the size is \(2^{5} \times 8 = 32 \times 8 = 256\) bits. Without the mode input, \(n = 4\) and the size is \(2^{4} \times 8 = 128\) bits. One extra input variable doubles the device — the exponential term is in the address, not the data.
2. A PLA has 12 inputs, 50 product terms and 6 outputs. How many programmable links does it contain, and how large a ROM would be needed to implement the same six functions? Comment on the comparison.
The AND plane has \(2nk = 2 \times 12 \times 50 = 1200\) links, the OR plane \(km = 50 \times 6 = 300\), so 1500 in all. A ROM would need \(2^{12} \times 6 = 4096 \times 6 = 24\,576\) bits, about sixteen times as many programmable elements. The PLA wins because it stores only the 50 product terms the functions actually use, whereas the ROM enumerates all 4096 minterms of twelve variables regardless. Note that the comparison reverses for small \(n\): for the 3 × 4 × 2 PLA of Worked Example 28.2 the PLA needs 32 links and the equivalent ROM only \(2^{3} \times 2 = 16\) bits.
3. Implement \(F_1 = \Sigma m(1,3,5,7)\) and \(F_2 = \Sigma m(3,5,7)\) of three variables \(A, B, C\) on a PLA and then on a PAL with three product terms per output. Give both programming tables and count the product lines used.
\(F_1\) is 1 whenever \(C = 1\), so \(F_1 = C\), a single one-literal term. For \(F_2\), the minterms 3, 5 and 7 group as \(BC\) (3 and 7) and \(AC\) (5 and 7), so \(F_2 = AC + BC\). On the PLA three product lines suffice: line 1 is \(C\) with input pattern (–, –, 1) dotted into \(F_1\) only; line 2 is \(AC\), pattern (1, –, 1), dotted into \(F_2\); line 3 is \(BC\), pattern (–, 1, 1), dotted into \(F_2\). On the PAL the outputs cannot share, but here they do not need to: \(F_1\) uses one line of its own group and leaves two unused (all links intact, so those terms are 0), and \(F_2\) uses two of its three. Four product lines are occupied in total against the PLA's three, and the extra line is the duplicate needed because \(F_1\)'s term \(C\) is in a group \(F_2\) cannot reach.
4. Why is the pin-to-pin delay of a CPLD quoted as a single number on the data sheet, while an FPGA data sheet quotes no such figure?
In a CPLD every signal path has the same shape: it leaves a macrocell, crosses the single programmable interconnect matrix exactly once, enters a product-term array, passes through one OR gate and one output buffer. Because there is one hop and only one, the delay does not depend on which macrocells the fitter chose, so a single \(t_{PD}\) characterises the device. In an FPGA a path is stitched together from routing segments through connection and switch boxes, and how many of those it crosses depends on where the placer put the two logic blocks and what the router could find. Interconnect delay dominates and varies from path to path, so the only meaningful timing figure comes from static timing analysis after placement and routing of that particular design.
5. Explain why a 4-input LUT can implement any function of four variables, and state how many configuration bits an FPGA needs for the LUT contents alone if it contains 20 000 such LUTs. Why does that not tell you the size of the bitstream?
A function of four variables is completely specified by the output column of its 16-row truth table. A 4-LUT holds exactly 16 SRAM bits and uses the four inputs as the address of a 16-to-1 multiplexer that selects one of them, so presenting a given input combination returns the stored bit for that row. Any of the \(2^{16} = 65\,536\) possible columns can be written, so any of the 65 536 four-variable functions can be realised, and the delay is the multiplexer delay regardless of which one. For 20 000 LUTs the contents need \(20\,000 \times 16 = 320\,000\) bits. The real bitstream is far larger because it must also set every routing switch in the fabric, every connection-box transistor, the mode bits of every flip-flop and output multiplexer, and the I/O standard of every pin — and on a typical device the routing configuration outnumbers the logic configuration by a wide margin.