# ROM and PLA: logic as a lookup

*Building a function from memory instead of gates*

A ROM or PLA implements a combinational logic function as stored data rather than gates: a ROM keeps the whole truth table (the output word at every input address), while a PLA keeps only the product terms of the function's sum-of-products form.

Group: Memory
URL: https://digiwleea.wleeaf.dev/learn/rom-pla/

Everything in the [Gates](https://digiwleea.wleeaf.dev/learn/karnaugh/) track pointed at one idea: a combinational function **is** its [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/), and a [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/) shrinks that table into the fewest gates. But gates are not the only way to build the function. Because the truth table already lists an output for every input, you can simply **store** that table in memory and **look the answer up**. Feed the inputs in as an **address**, read the stored output back out. No AND, no OR, no minimization: the logic lives in the stored bits. Two devices do exactly this, a **ROM** and a **PLA**, and they reframe a theme that runs through the whole course: memory and logic are the same thing seen from two sides.

## A ROM is a truth table you can address

A **ROM** (read-only memory) is a grid of stored words: give it an address and it returns the word kept there. Used as a *logic element*, the wiring is beautifully direct. The function's inputs become the **address lines**, and the word stored at each address is that row's **output**. An n-input, m-output function becomes a `2^n x m` ROM: `2^n` addresses (one per input combination, the same `2^n` rows a [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/) has) and an m-bit word at each (one bit per output). Inside, a [decoder](https://digiwleea.wleeaf.dev/learn/decoder/) turns the address into a one-hot line that selects a single stored word, exactly the addressing you built for [RAM](https://digiwleea.wleeaf.dev/learn/ram/). The only difference is that the contents never change: they encode the function.

> **TIP:** Picture a printed **multiplication table** on the wall. You do not compute `7 x 8` by adding sevens; you run your finger to row 7, column 8, and read `56`. A ROM is that table cast in silicon: the inputs pick the cell, and the stored value is the answer. The work was done once, when the table was written, so every lookup afterward is free. A precomputed table used this way is called a **lookup table**, or **LUT**.

## Worked example: the full adder as an 8 x 2 ROM

Take the [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/): three inputs `A`, `B`, `CIN`, and two outputs `SUM` and `COUT`. That is a 3-input, 2-output function, so it fits in a `2^3 x 2 = 8 x 2` ROM: eight addresses, a 2-bit word at each. Here is its truth table, with the inputs read as a 3-bit address `A B CIN` counting up from `000` to `111`:

| A | B | CIN | SUM | COUT |
| --- | --- | --- | --- | --- |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |

_The full adder's truth table. SUM is the odd-parity output (A XOR B XOR CIN); COUT is 1 when at least two inputs are 1. To store this as a ROM, each row's [SUM, COUT] pair becomes the 2-bit word at that row's address._

Read the two output columns down as `[SUM, COUT]` words and you have the ROM's contents, one word per address. Check each against the table:

- Address `0` (`000`): word `00`. Nothing set, so no sum bit and no carry.
- Address `1` (`001`): word `10`. One input set: `SUM = 1`, no carry.
- Address `2` (`010`): word `10`. One input set.
- Address `3` (`011`): word `01`. Two inputs set: the sum wraps back to `0` and a carry `1` is produced.
- Address `4` (`100`): word `10`. One input set.
- Address `5` (`101`): word `01`. Two inputs set: carry out.
- Address `6` (`110`): word `01`. Two inputs set: carry out.
- Address `7` (`111`): word `11`. All three set: `SUM = 1` and `COUT = 1`.

So the eight stored words, in address order, are `00, 10, 10, 01, 10, 01, 01, 11`. Every one matches the [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/), bit for bit: the ROM **is** the truth table. No gates were designed and no algebra was done; the answers were simply written down once and are read back forever.

## A PLA stores the product terms, not every row

A ROM is simple but wasteful: it keeps a word for **every** address, even the many addresses that share structure. A **PLA** (programmable logic array) is the smarter cousin. It builds the function as a [sum of products](https://digiwleea.wleeaf.dev/learn/canonical-forms/), the exact form a [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/) hands you, but directly in silicon as two stacked planes:

1. The **AND plane** forms **product terms**. Each row of this plane ANDs together a chosen set of the inputs (each true or inverted) to make one product term, a minterm or a merged group of minterms.
2. The **OR plane** sums them. Each output ORs together just the product terms it needs, and one product term can be reused by more than one output.

Both planes are **programmable**: you choose which inputs feed each AND, and which ANDs feed each OR (a **PAL** is the common variant where only the AND plane is programmable and the OR plane is fixed). Either way this is sum of products cast straight into hardware, which is why the [SOP](https://digiwleea.wleeaf.dev/learn/canonical-forms/) expression from [Karnaugh](https://digiwleea.wleeaf.dev/learn/karnaugh/) minimization is exactly what you program into a PLA.

Program the same full adder into a PLA. `COUT` is the majority function, and a [Karnaugh map](https://digiwleea.wleeaf.dev/learn/karnaugh/) already minimized it to three product terms; `SUM` is odd parity, which does **not** simplify, so it keeps all four of its minterms:

```
COUT = A·B + A·CIN + B·CIN
```

```
SUM  = A'·B'·CIN + A'·B·CIN' + A·B'·CIN' + A·B·CIN
```

That is seven distinct product terms in the AND plane (three for `COUT`, four for `SUM`, none shared in this case). The OR plane wires `COUT` to its three and `SUM` to its four. Now contrast the two builds of the *same* function: the ROM stored `8` words no matter what, while the PLA stores `7` product terms, and it would store far fewer for a function that minimized better.

_Circuit diagram: COUT = A·B + A·CIN + B·CIN built as a PLA: the AND plane forms the three product terms (the three AND gates) and the OR plane sums them (the OR tree). This is the sum-of-products COUT half of the full adder, the same majority circuit a Karnaugh map produces. Open it in the lab and sweep all eight input rows: COUT is high whenever at least two inputs are high._

## ROM vs PLA: store everything, or store what you use

The two devices trade off the same way every time:

- A **ROM** stores one word per address, always `2^n` of them. It is dead simple and perfectly regular (you just fill in the words), but its size **doubles with every input you add**, whether the function needs it or not. A 16-input function is a `65,536`-word ROM even if it is nearly trivial.
- A **PLA** stores one row per product term. For a **sparse** function (few `1`s, or one that minimizes to a handful of terms) that is dramatically smaller, but a nasty function with many un-mergeable terms can need almost as many rows as a ROM has words.

The gap is starkest for a sparse function. Suppose you must detect one specific 4-bit code: the output is `1` only for input `1010` and `0` for the other fifteen. A ROM needs all `2^4 = 16` words (fifteen `0`s and a single `1`). A PLA needs **one** product term, `A·B'·C·D'`, true for exactly that code. Sixteen stored words versus one term, for the identical function. That is why irregular control logic (which is mostly sparse) tends to be built from PLAs, while big regular tables suit a ROM.

> **WARN:** **Common mistakes.** A ROM used as logic is **combinational**, not clocked storage: the address changes and the output follows, with no clock and nothing remembered between lookups. Do not confuse it with the [RAM](https://digiwleea.wleeaf.dev/learn/ram/) that holds a running program. Its size is set by the **input** count, not the output count: `n` inputs always means `2^n` addresses, so adding one input **doubles** the ROM, while adding an output only widens each word by one bit. And a PLA is only compact if the function **minimizes**: an XOR-heavy or parity function barely shrinks (our `SUM` kept all four minterms), so a PLA is not automatically smaller than a ROM. Size the device to the function.

> **KEY:** This is the idea that ties the [Gates](https://digiwleea.wleeaf.dev/learn/karnaugh/) track to [memory](https://digiwleea.wleeaf.dev/learn/ram/): **any** combinational function can be a lookup instead of a gate network, because the truth table is the function. It is not a curiosity. A modern **[FPGA](https://digiwleea.wleeaf.dev/learn/fpga/)** computes logic exactly this way. Its cells are small **lookup tables** (typically 4-input or 6-input LUTs), and each LUT is really a tiny ROM whose contents are loaded when the chip is configured, so changing the stored bits changes the logic the cell performs. When you later describe hardware in [VHDL](https://digiwleea.wleeaf.dev/learn/vhdl-intro/) and target an FPGA, your gates become LUT contents. Memory holding logic, logic living in memory: the same silicon, read two ways.

**Q (Try it):** You need a 3-input majority voter: `F = 1` when at least two of `A`, `B`, `C` are `1`. Sketch it two ways. (a) As a ROM: how many addresses, how wide is each word, and what are the eight stored bits in address order? (b) As a PLA: how many product terms, and what are they?

**A:** **(a) ROM:** 3 inputs means `2^3 = 8` addresses; 1 output means a 1-bit word, so it is an `8 x 1` ROM. Its stored bits, address `000` to `111`, are `0, 0, 0, 1, 0, 1, 1, 1`: a `1` exactly at addresses `3, 5, 6, 7`, the rows with two or more `1`s. **(b) PLA:** three product terms, `F = A·B + A·C + B·C`, the minimized majority function from the [Karnaugh](https://digiwleea.wleeaf.dev/learn/karnaugh/) lesson. The ROM stores eight bits; the PLA stores three terms. Both compute the identical function, which is also the `COUT` of a [full adder](https://digiwleea.wleeaf.dev/learn/fulladder/).

### FAQ

**Q:** What is the difference between a ROM and a PLA?

**A:** Both implement a combinational function as stored data instead of a gate network. A **ROM** stores the whole truth table, one output word at every one of its `2^n` input addresses, so it is simple and regular but grows exponentially with the input count. A **PLA** stores only the function's [sum-of-products](https://digiwleea.wleeaf.dev/learn/canonical-forms/) product terms in a programmable AND plane feeding a programmable OR plane, so it is far smaller for sparse or well-minimizing functions but needs many rows for a function that does not simplify.

**Q:** How can a memory implement a logic function?

**A:** A combinational function is completely defined by its [truth table](https://digiwleea.wleeaf.dev/learn/truth-tables/), so you can store that table in a ROM and *look up* the answer: wire the function's inputs to the ROM's address lines, and the stored word at each address is the output for that input combination. An n-input, m-output function becomes a `2^n x m` ROM. This precomputed table is called a **lookup table (LUT)**, and it uses no AND or OR gates at all.

**Q:** What is a lookup table (LUT)?

**A:** A lookup table is a small memory that stores the output for every input combination of a logic function, so the circuit computes by reading the stored answer at the address formed by its inputs rather than by evaluating gates. A k-input LUT is a `2^k`-word memory holding the function's truth table. Modern [FPGAs](https://digiwleea.wleeaf.dev/learn/fpga/) are built from LUTs: each is a tiny writable ROM whose contents are loaded at configuration to define the logic the cell performs.

**Q:** Why do FPGAs use lookup tables instead of fixed gates?

**A:** An [FPGA](https://digiwleea.wleeaf.dev/learn/fpga/) has to become *any* circuit after it is manufactured, and a lookup table can be reprogrammed to any function of its inputs just by changing its stored bits, whereas fixed gates cannot. Each logic cell is a small LUT (commonly 4 or 6 inputs), a tiny ROM whose contents are loaded when the chip is configured, so the same silicon implements different logic depending on what you store.