ROMs and PLAs: programmable logic

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• Decoder outputs are? from Lesson 5.2.2
• Any function from a decoder needs which extra gate? from Lesson 5.2.2
• Minimal SOP shares terms how? from Lesson 4.1.2

1 · The Hook

🎣

Instead of wiring gates for each new function, why not store the truth table in a memory and look the answer up? That is a ROM. If the truth table is huge but the function has few product terms, a PLA stores only the product terms. GATE asks the size of the ROM needed for a function, and how many product terms a PLA needs.

2 · Predict First

🤔

A function has 4 inputs and 3 outputs. If we store its whole truth table in a memory, how many rows and how many bits per row?

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

2⁴ = 16 rows, 3 bits per row (48 bits in all).

🗣️

In plain words

A ROM is a decoder (making every minterm) followed by a programmable OR array: each output ORs the minterms where it is 1. Its size depends only on the number of inputs and outputs. A PLA has a programmable AND array (making just the product terms you need) followed by a programmable OR array, so it is small when the functions share a few product terms.

1. ROM

• n inputs, m outputs → 2ⁿ words of m bits (a 2ⁿ × m ROM).
• Any functions of the n inputs fit, no minimisation needed.
• Example: a ROM that outputs the square of a 4-bit number needs 4 inputs and 8 output bits (15² = 225 < 256) → 16 × 8.
• Example: an 8-bit + 8-bit adder with carry-in as a ROM: 17 inputs, 9 outputs → 2¹⁷ × 9: lookup tables grow exponentially.

2. PLA (programmable logic array)

• Programmable AND array (product terms) + programmable OR array (sums).
• Size is described as inputs × product terms × outputs; product terms can be shared between outputs.
• To use few product terms, minimise the functions together and reuse common terms (sometimes a function's complement is cheaper).

Example: F₁ = AB + AC, F₂ = AB + BC → distinct products AB, AC, BC: 3 product terms (AB shared).

3. PAL (programmable array logic)

Programmable AND array, fixed OR array (each output gets its own few product terms; no sharing). Cheaper and faster than a PLA, less flexible.

4 · Visual

The common shape of ROM, PLA and PAL: which array is fixed and which is programmable makes the difference.

5 · Worked Examples

Example 1 Easy

What size ROM implements 3 functions of 5 variables?

Solution

2⁵ × 3 = 32 × 3.

Example 2 Medium

F₁ = AB + A'C and F₂ = AB + BC' are put in a PLA. How many product terms are needed?

Solution

AB, A'C, BC' → 3 (AB shared).

Example 3 GATE

A ROM converts a 4-bit binary number into its 2-digit BCD form (0–15 → 00–15). What size is it?

Solution

4 inputs. The tens digit is only ever 0 or 1 (1 bit) and the units digit needs 4 bits, so 5 output bits → a 16 × 5 ROM.

6 · GATE Traps

⚠️

• ROM size depends on inputs and outputs only: 2ⁿ × m.
• PLA counts distinct product terms across all outputs.
• PAL's OR array is fixed: no sharing of product terms between outputs.
• ROM never needs minimisation.

7 · Memory Hook

🧠

"ROM: fixed AND (all minterms), programmable OR, 2ⁿ × m. PLA: both programmable, share products. PAL: OR fixed."

8 · Connect the Dots

Phase 5 is complete: every combinational building block. Phase 6 adds memory: latches and flip-flops, then counters and state machines, where outputs depend on the past as well as the present.

9 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markROM size

How many bits does a ROM implementing 4 functions of 6 variables store?

Numerical answer: ________

Q2NAT2 marksROM squarer

A ROM gives the square of a 5-bit unsigned input. How many output bits does each word need?

Numerical answer: ________

Q3NAT2 marksPLA

F₁ = AB + AC and F₂ = AB + BC are realised in a PLA. How many product terms?

Numerical answer: ________

Q4MCQ1 markDevices

Which device has a programmable AND array and a fixed OR array?

• (A) ROM
• (B) Decoder
• (C) PLA
• (D) PAL

Q5MCQ1 markROM

A ROM's AND part is:

• (A) a priority encoder
• (B) a multiplexer tree
• (C) a full decoder generating every minterm
• (D) a programmable set of product terms

10 · Rule Card

• ROM: fixed AND (decoder), programmable OR; size 2ⁿ × m bits.
• PLA: programmable AND and OR; count distinct product terms; share terms between outputs.
• PAL: programmable AND, fixed OR (no sharing).

11 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

read-only memory as logicROM sizelookup tablesprogrammable logic arrayproduct-term sharingprogrammable array logicfixed vs programmable arrays

12 · Answer Vault