A lookup table skips Boolean algebra entirely. Instead of computing F from its inputs with gates, you store F's value for every input combination and simply look it up.
- The inputs form an index (a row number).
- The table holds one answer per index.
- The output is the answer stored at that index.
It's a truth table turned into hardware. Two ways to build one appear in this course:
- A multiplexer with the inputs on its selects and constants on its data inputs (multiplexer implementation).
- A ROM, with the inputs on its address lines and the outputs on its data lines. An n-input, m-output function fits in a 2ⁿ × m ROM.
FPGAs are built from thousands of small LUTs, typically with 4 to 6 inputs. Each is a tiny memory whose contents are loaded when the chip is configured, so the same silicon can become any circuit.
The cost: a table with k inputs needs 2ᵏ entries. Each extra input doubles its size, whether or not the function is complicated. LUTs are ideal for small, irregular functions and wasteful for wide ones.
| F | |||
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 0 |