Chapter 30 of 32

Memory & Programmable Logic Devices (ROM, PLA, PAL)

Until now we built every circuit from individual gates and flip-flops. That works on paper, but a real product might need hundreds of different functions, and wiring separate gate chips for each is slow and expensive. Two ideas changed this. First, a memory can act as a ready-made truth table: store the outputs, use the inputs as the address. Second, a programmable logic device (PLD) is a chip full of uncommitted AND and OR gates whose connections you choose after manufacture.

This chapter covers both: what memories are and how they are organised and expanded, how a ROM implements any combinational function, and how the classic PLDs, the PLA and PAL, implement sum-of-products expressions with fewer resources. We finish with a short look at CPLDs and FPGAs, which grew out of these ideas. Memory technology at the transistor level (SRAM and DRAM cells, refresh, memory hierarchy) belongs to Computer Organisation; here we focus on the logic view.


Memory Basics

Memory: an array of storage locations (words), each holding m bits, selected by an n-bit address. A memory with n address lines and m data lines has 2n words of m bits, written 2n × m, for a capacity of 2n × m bits.

               +---------------------+
 A(n-1)..A0 ──►|  address decoder    |       n address lines  → 2^n words
               |  selects ONE word   |
               |   2^n words x m bits|──► D(m-1)..D0   m data lines
 CS (chip  ───►|                     |
   select)     |                     |
 R/W ─────────►|                     |
               +---------------------+

Examples. A 1K × 8 memory has 1024 = 210 words, so 10 address lines and 8 data lines; capacity 8192 bits. A 64K × 16 memory needs 16 address lines (64K = 216) and 16 data lines.

RAM and ROM

TypeRead/writeVolatile?How it storesTypical use
SRAMRead and writeYesA latch per bit (6 transistors)Fast: caches, registers
DRAMRead and writeYes, and needs refreshCharge on a capacitor (1 transistor + 1 capacitor)Main memory
Mask ROMRead onlyNoPattern fixed at manufactureHigh-volume fixed code and tables
PROMProgram onceNoFuses or antifuses, burnt by the userSmall runs, one-time programming
EPROMErase with UV light, reprogramNoFloating-gate transistors; quartz window in the packageOlder firmware development
EEPROMErase electrically, byte by byteNoFloating gate, electrical eraseSettings, calibration data
FlashErase electrically, block by blockNoFloating gate (or charge trap), block eraseFirmware, SSDs, memory cards

"RAM" stands for random-access memory, meaning any word can be reached in the same time. ROM is also random-access, so the real distinction is read-write vs read-mostly and volatile vs non-volatile.

Memory Expansion

When one chip is too small, combine chips:

  • Word-width expansion (more bits per word): put chips side by side, with all address and control lines shared. Two 1K × 4 chips make a 1K × 8 memory.

  • Word-count expansion (more words): stack chips, share the low address lines and data lines, and use a decoder on the high address lines to drive the chip-select inputs so only one row of chips responds.

Worked example. Build a 16K × 8 memory from 4K × 4 chips.

  1. Chips needed = (16K / 4K) × (8 / 4) = 4 × 2 = 8 chips, arranged as 4 rows of 2.

  2. Address lines: 16K = 214, so 14 lines A13 to A0. Each chip has 4K = 212 words, so A11 to A0 go to every chip.

  3. The remaining A13 and A12 drive a 2-to-4 decoder; output i selects row i.

                     A11..A0 (to all 8 chips)
 A13 ─┐   +---------+   row 0: [4K x 4][4K x 4]   addresses 0000-0FFF (hex)
 A12 ─┴──►| 2-to-4  |──► row 1: [4K x 4][4K x 4]   1000-1FFF
          | decoder |──► row 2: [4K x 4][4K x 4]   2000-2FFF
          |         |──► row 3: [4K x 4][4K x 4]   3000-3FFF
          +---------+          D7..D4   D3..D0  (shared data bus)

ROM as a Combinational Circuit

Look inside a ROM with n inputs and m outputs and you find exactly two layers:

  • an n-to-2n decoder (fixed), which generates every minterm of the address inputs, and

  • an OR array (programmable): each output is the OR of the minterms where that output should be 1.

That is a canonical sum-of-minterms implementation, as in Canonical Forms: SOP & POS, with no simplification at all. So any m functions of n variables fit in a 2n × m ROM: just store the truth table.

ROM 8 x 2 (3 inputs, 2 outputs), "dot" notation:  ● = connection made

          A B C
          │ │ │        decoder outputs = minterms
       +--┴─┴─┴--+
       | 3-to-8  |─ m0 ──●──────────
       | decoder |─ m1 ──┼──────●───
       | (fixed) |─ m2 ──●──────┼───
       |         |─ m3 ──┼──────┼───
       |         |─ m4 ──┼──────●───
       |         |─ m5 ──┼──────┼───
       |         |─ m6 ──●──────┼───
       |         |─ m7 ──┼──────●───
       +---------+     [OR]   [OR]      OR array (programmable)
                         │      │
                         F1     F2
   F1 = m0 + m2 + m6       F2 = m1 + m4 + m7

Worked Example: A Squaring Circuit in ROM

Problem. Implement a circuit that outputs the square of a 3-bit number A2A1A0 using a ROM.

Inputs 0 to 7, outputs 0 to 49, so 6 output bits B5..B0 are needed:

A2A1A0NN2B5 B4 B3 B2 B1 B0
000000 0 0 0 0 0
001110 0 0 0 0 1
010240 0 0 1 0 0
011390 0 1 0 0 1
1004160 1 0 0 0 0
1015250 1 1 0 0 1
1106361 0 0 1 0 0
1117491 1 0 0 0 1

A direct implementation needs an 8 × 6 ROM. But look at the last two columns: B1 is always 0 and B0 always equals A0 (an odd number squared is odd, and every square is 0 or 1 mod 4). Those two outputs need no ROM at all, so an 8 × 4 ROM for B5..B2 is enough. Spotting such simplifications is a favourite exam twist.

Sizing ROMs

For a ROM implementation, count the inputs n and the outputs m; the ROM is 2n × m.

FunctionInputs nOutputs mROM size
4-bit adder with carry-in4 + 4 + 1 = 95 (sum + carry)512 × 5 = 2560 bits
4-bit × 4-bit multiplier88256 × 8 = 2048 bits
BCD to 7-segment decoder4716 × 7 = 112 bits
8-bit binary to BCD (0 to 255)810 (3 digits; hundreds digit only needs 2 bits)256 × 10

The weakness is obvious from the first row: every extra input doubles the ROM. A 16-bit adder would need 233 words. ROMs are great for small, irregular functions (code converters, lookup tables, microprogram stores), not for wide arithmetic.


PLA: Programmable Logic Array

Most functions do not need all 2n minterms; their minimised SOP uses only a few product terms. A PLA exploits this by making both arrays programmable.

PLA (programmable logic array): a PLD with a programmable AND array that generates a limited number of product terms from the inputs and their complements, followed by a programmable OR array that combines any of those product terms into each output. A PLA is specified by its size n × k × m: n inputs, k product terms, m outputs.

  inputs (with complements)
     │ │ │
     ▼ ▼ ▼
  +-----------------+      k product terms      +-----------------+
  |   AND array     | ────────────────────────► |    OR array     | ──► m outputs
  |  (programmable) |                           |  (programmable) |   (optional XOR
  +-----------------+                           +-----------------+    for inversion)

Many PLAs also put a programmable XOR gate on each output, so an output can be F or F̅. That lets you implement whichever of F and F̅ needs fewer product terms.

Worked Example: Two Functions on One PLA

Problem. Implement F1(A, B, C) = Σm(1, 2, 3, 7) and F2(A, B, C) = Σm(2, 3, 5, 7) on a PLA with as few product terms as possible.

Step 1: minimise each function (by K-map; checked with a computer):

F1 = A̅·C + A̅·B + B·C        (m1 only by A̅C, m2 only by A̅B, m7 only by BC:
                             all three terms are essential)
F2 = A̅·B + A·C

Step 2: share product terms. A̅B appears in both functions, so it is generated once. Distinct terms: A̅C, A̅B, BC, AC, so k = 4.

Step 3: write the PLA programming table. In the input part, 1 = true input used, 0 = complemented input used, – = input not connected. In the output part, 1 = the term is connected to that OR gate.

Product termABCF1F2
P1 = A̅C0–11–
P2 = A̅B01–11
P3 = BC–111–
P4 = AC1–1–1

So this is a 3 × 4 × 2 PLA. A ROM for the same job would need all 8 minterms (8 × 2). For functions with many inputs the saving is enormous, because k grows with the number of distinct product terms, not with 2n.

         A  A̅  B  B̅  C  C̅
         │  │  │  │  │  │
  P1 ────┼──●──┼──┼──●──┼──── (A̅C)    ──●───────────
  P2 ────┼──●──●──┼──┼──┼──── (A̅B)    ──●──────●────
  P3 ────┼──┼──●──┼──●──┼──── (BC)     ──●──────┼────
  P4 ────●──┼──┼──┼──●──┼──── (AC)     ──┼──────●────
         AND array (programmable)        OR   OR
                                         │    │
                                         F1   F2

Minimising for a PLA differs from minimising a single function: the goal is the fewest distinct product terms across all outputs. Sometimes using a non-minimal term in one function lets it be shared with another, which saves a row.


PAL: Programmable Array Logic

PAL (programmable array logic): a PLD with a programmable AND array and a fixed OR array. Each output OR gate is permanently connected to its own small group of product terms (for example 7 or 8), which cannot be shared with other outputs.

Why give up flexibility? A programmable OR array costs chip area and adds delay. With a fixed OR array the PAL is cheaper and faster, and most real functions need only a handful of terms per output anyway. PAL devices were introduced by Monolithic Memories in the late 1970s and became hugely popular for "glue logic" on circuit boards.

To implement F1 and F2 above on a PAL, each output simply uses its own AND gates: F1 uses 3 terms, F2 uses 2 terms, so A̅B is built twice (once in each output's group). The total is 5 AND terms instead of 4, but nothing needs to be shared.

Two practical features of real PALs:

  • Feedback: outputs can be fed back into the AND array. If a function needs more terms than one output group has, compute part of it in one output and use that output as an input of another (at the cost of extra delay).

  • Registered outputs: many PALs have a D flip-flop after the OR gate, with feedback into the array. That makes a complete state machine (like the ones in Sequence Detector Design) fit in one chip.

The GAL (generic array logic, from Lattice), for example the 16V8 and 22V10, is an electrically erasable PAL whose output cell (OLMC, output logic macrocell) can be configured as combinational or registered, with either polarity. A GAL can replace most of the older PAL part numbers.


ROM vs PLA vs PAL

All three are two-level AND-OR structures. They differ only in which array is programmable:

DeviceAND arrayOR arrayProduct termsStrengthWeakness
ROM / PROMFixed (full decoder, all 2n minterms)ProgrammableAll mintermsAny function, no minimisation neededSize doubles per input; cannot use don't-cares to save space
PLAProgrammableProgrammablek, shared by all outputsMost flexible; sharing termsTwo programmable arrays: slower, more expensive
PALProgrammableFixedA fixed number per output, not sharedFast, cheap, simple to programLimited terms per output; no sharing

A one-line memory aid: PROM = fixed AND, PAL = fixed OR, PLA = nothing fixed.


Beyond PALs: CPLDs and FPGAs

  • CPLD (complex PLD): many PAL-like blocks (macrocells) on one chip, linked by a programmable interconnect. Timing is predictable and configuration is non-volatile, so CPLDs suit control and glue logic that must work immediately at power-up.

  • FPGA (field-programmable gate array): a large grid of small logic blocks, each built around a look-up table (LUT) and a flip-flop, connected by programmable routing, plus hard blocks such as RAM, multipliers and transceivers. A k-input LUT is simply a 2k × 1 memory, so it can implement any function of k inputs, which is the ROM idea from this chapter shrunk to a tiny cell and repeated many thousands of times. Most FPGAs store their configuration in SRAM, so it is reloaded from a flash memory at power-up.

Today, designers describe the logic in an HDL (Verilog, SystemVerilog or VHDL), and synthesis tools map it to LUTs or macrocells automatically. The hand methods in this chapter are what those tools do underneath.


Common Mistakes

  • Mixing up which array is fixed. PROM: AND fixed. PAL: OR fixed. PLA: neither.

  • Counting ROM size from minterms used. A ROM always has 2n words, however few minterms the function uses.

  • Forgetting to count shared terms once in a PLA, or assuming terms can be shared in a PAL.

  • Wrong address-line count. Address lines = log2(number of words), not log2(bits). A 4K × 8 memory has 12 address lines.

  • In memory expansion, sending high address bits to every chip. They go to the decoder for chip selection; only the chip's own address bits go to every chip.

  • Missing easy output simplifications such as B0 = A0 in the squarer, which shrink the ROM.


GATE and Interview Questions

Q1. How many 1K × 4 RAM chips are needed for an 8K × 16 memory, and what size of decoder selects the rows?

(8K / 1K) × (16 / 4) = 8 × 4 = 32 chips, in 8 rows of 4. 8 rows need a 3-to-8 decoder on the top 3 address bits (A12, A11, A10); A9 to A0 go to every chip.

Q2. What size of ROM is needed to implement a full adder? And a 2-bit comparator with outputs A>B, A=B, A<B?

Full adder: 3 inputs, 2 outputs: 8 × 2. Comparator: 4 inputs, 3 outputs: 16 × 3.

Q3. A PLA has 6 inputs, 10 product terms and 4 outputs. How many programmable connections does it have, ignoring output inverters?

Each product term can connect to all 6 inputs and their complements: 10 × 12 = 120 in the AND array. Each output OR can connect to all 10 terms: 4 × 10 = 40 in the OR array. Total 160.

Q4. Which PLD would you choose for a function whose outputs share many product terms, and why?

A PLA, because its programmable OR array lets one product term feed several outputs. A PAL would have to duplicate each shared term in every output's fixed group.

Q5. Why can a ROM implement any Boolean function of its inputs without minimisation?

Its fixed decoder produces every minterm, and the programmable OR array can select any subset of them. Any function is a sum of minterms (canonical SOP), so storing its truth table is enough.

Q6. How many address lines and data lines does a 256K × 32 memory have?

256K = 218, so 18 address lines and 32 data lines.


Summary

  • A 2n × m memory has n address lines and m data lines. RAM (SRAM, DRAM) is volatile; ROM, PROM, EPROM, EEPROM and Flash are non-volatile.

  • Expand word width by placing chips side by side; expand word count with a decoder on the high address bits driving chip selects.

  • A ROM = fixed decoder (all minterms) + programmable OR array, so it implements any m functions of n inputs in 2n × m bits.

  • A PLA (n × k × m) has programmable AND and OR arrays; product terms are shared, so minimise for the fewest distinct terms.

  • A PAL has a programmable AND array and a fixed OR array: faster and cheaper, but no term sharing. GALs are reprogrammable PALs with configurable macrocells.

  • CPLDs combine many PAL-like blocks; FPGAs use LUTs (tiny ROMs) plus flip-flops and programmable routing.

  • Next, Logic Families: TTL & CMOS looks at the electrical side: the voltages, currents and delays of the gates inside all these chips.