Home
12ROM & Programmable Logic
12

Topic 12 of 13

ROM & Programmable Logic

ROM as a lookup table, then PLA and PAL: configurable AND and OR arrays.

StartAll topics

← → move between slides · F full screen · M slide list

Before we start

Why this matters

How did a 1980s arcade machine know exactly which pixel-art villain to throw at you next, with zero software as we'd recognise it today?

It was hard-wired straight into a ROM chip — a lookup table baked into silicon that will never, ever change its mind. This chapter shows you that a ROM is basically a truth table you can buy off a shelf, and how PLAs and PALs let you “program” the wiring yourself instead of begging a chip factory for a custom favour.

Outline

Topics in this chapter

Select a topic to jump to the slide that explains it.

  1. ROM organization
  2. ROM read operation
  3. Address decoder
  4. ROM-based logic implementation
  5. Mask ROM
  6. PROM
  7. EPROM
  8. EEPROM
  9. Flash memory
  10. PLA structure
  11. PAL structure
  12. PLA vs. PAL
  13. ROM vs. PLA
  14. Programmable logic design flow
  15. CPLD and FPGA introduction

Concept 1 of 4

ROM organisation and logic

A 2n × m ROM has n address lines feeding a decoder, and the decoder’s word lines feed OR gates that form the m output bits. A 32 × 8 ROM has 5 inputs and 8 outputs. Reading applies an address, decodes it, selects one word and outputs its bits.

Because the decoder generates every minterm, a ROM implements any combinational function of its address bits. The inputs are the address, and the stored bits are the truth table. A full adder (3 inputs, 2 outputs) fits in an 8 × 2 ROM.

Explore furtherInside the Computer27C256 chip (EPROM)Inside the ComputerBIOS chip

Concept 2 of 4

Types of ROM

TypeProgramming
Mask ROMFixed at manufacture
PROMOnce by the user
EPROMErased with ultraviolet light, then reprogrammed
EEPROMErased and programmed electrically
FlashElectrical, erased in blocks

All are non-volatile.

Explore furtherInside the Computer27C256 chip (EPROM)Inside the Computer24C02 chip (EEPROM)Inside the ComputerW25Q128 chip (flash)Inside the ComputerNAND flash memory

Concept 3 of 4

PLA and PAL

A PLA has a programmable AND array that forms product terms and a programmable OR array that combines them, so it implements sum-of-products directly with only the terms needed. A PAL has a programmable AND array and a fixed (or constrained) OR array: cheaper and faster, less flexible.

DeviceAND arrayOR array
ROMFixed (full decoder)Programmable
PLAProgrammableProgrammable
PALProgrammableFixed

A PLA's size is given as its number of inputs, product terms, and outputs — a typical PLA has 16 inputs, 48 product terms, and 8 outputs. Each input needs a connection to both its true and complemented form in the AND array, so the fuse (or switch) count is higher than a plain product-term count suggests.

Concept 3 of 4

PLA and PAL (cont.)

PLA fuses = 2n × k + k × m + m
ROM fuses = 2ⁿ × m
(n inputs, k product terms, m outputs)
I1I2I3ANDORO1O2ROMI1I2I3ANDORO1O2PLAI1I2I3ANDORO1O2PAL= fixed connection= programmable (fuse) connection
A solid dot marks a fixed connection wired at manufacture; an orange X marks a programmable (fusible) connection you configure. ROM: the AND array (decoder) is fully fixed and only the OR array is programmable; PLA: both arrays are programmable; PAL: the AND array is programmable but the OR array is fixed.

Concept 4 of 4

Design flow

  1. Define the functions.
  2. Simplify the Boolean expressions (don’t-cares help).
  3. Identify product terms, sharing them across outputs.
  4. Map terms to the device.
  5. Program and verify.

Modern programmable logic includes CPLDs and FPGAs, which scale the same idea to thousands of configurable blocks.

Truth tables

Truth tables (1 of 2)

ROM contents: full adder in an 8 × 2 ROM

ABCSumCout
00000
00110
01010
01101
10010
10101
11001
11111

PLA program table: F1 = AB + A′C, F2 = AC + BC

TermABCF1F2
P1 = AB11–1–
P2 = A′C0–11–
P3 = AC1–1–1
P4 = BC–11–1

1 means the true input, 0 the complement, – means not connected.

Truth tables

Truth tables (2 of 2)

ROM, PLA and PAL arrays

DeviceAND arrayOR array
ROMFixedProgrammable
PLAProgrammableProgrammable
PALProgrammableFixed

Interactive

Demo: ROM and PLA

Worked example 1 of 3

Worked example 1

Implement F1 = AB + A′C and F2 = AC + BC in a PLA.
Show the solution
  1. Product terms: P1 = AB, P2 = A′C, P3 = AC, P4 = BC.
  2. AND array: connect A,B to P1; A′,C to P2; A,C to P3; B,C to P4.
  3. OR array: F1 = P1 + P2 and F2 = P3 + P4.
Build it in the demo below.

Worked example 2 of 3

Worked example 2

What ROM size implements a 4-input, 3-output function?
Show the solution
24 words × 3 bits = 16 × 3.

Worked example 3 of 3

Worked example 3

Design a ROM-based circuit that accepts a 3-bit number A2A1A0 and outputs its square as a binary number B5…B0. What is the smallest ROM size that works?
Show the solution
  1. 3 inputs need 23 = 8 words, one per input combination.
  2. Tabulate the squares: 0,1,4,9,16,25,36,49 — the largest, 49, needs 6 bits (B5…B0), so a first guess is an 8 × 6 ROM.
  3. Two output columns turn out to be trivial: B1 is 0 for every row, and B0 always equals A0. Neither needs a stored bit — B1 can be tied to 0 and B0 wired straight from A0.
  4. Only B5, B4, B3 and B2 actually need ROM storage, so the design shrinks to an 8 × 4 ROM plus two wires.
Result: an 8 × 4 ROM, not 8 × 6 — spotting outputs that are constant or that duplicate an input saves storage.

Practice

Practice (1 of 2)

Try each one on paper first, then check your answer.

1. Explain ROM organization.
Show the answer
Address lines feed a decoder. Each decoder output selects one stored word, and the OR gates present that word’s bits at the outputs.
2. Compare PROM, EPROM, EEPROM and Flash.
Show the answer
PROM: programmed once. EPROM: UV erase. EEPROM: electrical erase by byte. Flash: electrical erase in blocks.
3. Describe the PLA architecture.
Show the answer
Inputs and their complements feed a programmable AND array (product terms), which feeds a programmable OR array (outputs).

Practice

Practice (2 of 2)

Try each one on paper first, then check your answer.

4. Compare PLA and PAL.
Show the answer
PLA: both arrays programmable. PAL: only the AND array is programmable.
5. Implement F = AB + A′C with programmable logic.
Show the answer
Two product terms, AB and A′C, both connected to the OR gate of the output.
Practice in Gate Forge

Build a decoder plus OR gates that behaves like a small ROM, and Save it as a component.

Open Gate ForgeGate ForgeA free circuit simulator — place and wire gates, generate truth tables and timing diagrams, and work through 90+ guided problems.

Check yourself

Quiz

Summary

Summary

  • A ROM is a lookup table: decoder plus OR array.
  • Mask, PROM, EPROM, EEPROM and Flash differ in how they are programmed and erased.
  • PLA: AND and OR both programmable. PAL: AND programmable, OR fixed.
  • Share product terms to save resources.
  • CPLDs and FPGAs are the modern versions.
Next topic: ApplicationsAll topics