Computer Engineering is coming soon

We're still writing and reviewing the notes for every subject, and we'll open it when every subject is ready. Meanwhile you can practise aptitude, ask Aria about any subject, or see the branches that are ready.

Programmable logic devices: ROM, PLA and PAL

Practical, exam-focused notes on programmable logic devices (PLDs): Read-Only Memory (ROM), Programmable Logic Array (PLA) and Programmable Array Logic (PAL), their architectures, how to implement Boolean functions, and how to choose between them.

Drafted with Aria, reviewed by the AiCanCode.org team · Updated . How we write and check our notes. Spotted an error? Use Give Feedback at the bottom of the page.

Why it matters

PLDs let engineers implement arbitrary digital logic without custom IC fabrication. In computer engineering you use ROM, PLA and PAL when you need fixed combinational logic (like lookup tables, code converters, small state decode logic) with fast turn-around and low NRE cost. Knowing their architectures helps you choose the simplest, smallest and fastest solution for exam problems and real designs.

Key ideas

Exact statement: Given n input variables, a ROM with m output bits implements any function f: {0,1}^n -> {0,1}^m by storing 2^n words each of m bits. It requires no Boolean minimisation; it is essentially a full truth-table storage. Internally, a ROM can be viewed as a fixed n-to-2^n decoder (AND plane generating all minterms) feeding a programmable memory array that effectively acts as the OR plane selecting minterms per output.

What to draw: draw a rectangle labelled ROM. On the left draw n address lines A_{n-1} ... A_0 entering. On the right draw m data output lines D_{m-1} ... D_0 leaving. Under the rectangle write "size = 2^n × m bits".

  • Programmable AND-OR array (PLA) — a two-level programmable logic network. First level is a programmable AND (product-term) plane that can form any required minterms (ANDs of inputs and/or their complements). Second level is a programmable OR plane that sums selected product terms to create each output. PLA can implement any sum-of-products form and is fully programmable in both planes.

    Exact statement: A PLA with n inputs and P product lines can implement up to P distinct product terms (each a conjunction of literals), and each of m outputs is an OR of a programmable subset of those P products.

    What to draw: draw inputs on the left; show each input and its complement available. Draw lines going to a grid (AND plane) with P horizontal product-term wires; draw programmable connections (dots) at intersections. From the P product lines draw vertical lines into an OR plane grid; show programmable dots connecting product lines to output OR gates; label outputs.

  • Programmable Array Logic (PAL) — a restricted PLD similar to PLA but with a programmable AND plane and a fixed (or limited-programmable) OR plane. In the classic PAL architecture the AND plane is fully programmable but each OR output has a fixed set of product-term inputs (or limited fan-in). PAL is optimized for speed and density by hard-wiring the OR gates, reducing programmable interconnect.

    Exact statement: A PAL with P product terms and m outputs has a programmable connection from inputs to each product line, but each output OR gate has a fixed connection matrix (often each OR gate can accept a subset of product lines) — device datasheet specifies exact OR structure.

  • Comparison, when to use which:

    • Use ROM when you need to implement many outputs for small n or you have no desire to minimise logic — ROM size grows as 2^n so it is inefficient for large n.
    • Use PLA when you need flexibility to minimize product terms across outputs (both planes programmable), useful when product sharing reduces hardware.
    • Use PAL when the required OR-plane structure fits device constraints; PALs are cheaper and faster but less flexible than PLAs.
  • Important limits and assumptions used in exam problems: assume ideal gates (zero propagation delay for logic counting unless asked otherwise), enough fan-in for AND/OR unless a device limit is specified, and that complements of each input are available where the architecture provides them.

Formulas

ROM_size_bits = 2^n · m where n = number of inputs (address lines), m = number of outputs (bits stored per address); unit = bits; applies to ROMs storing full truth-table.

n = log2(N) where N = number of distinct addresses (words), n = number of address lines; unit = bits; applies when N is power of two.

P_required ≥ number_of_distinct_product_terms_in_minimized_SOP where P_required is number of PLA product lines needed; unit = product_terms; use after minimisation. In a fully programmable PLA, the approximate fuse count is AND-plane: 2·n·P and OR-plane: P·m.

ROM_required_if 2^n · m < cost_equivalent_PLD (heuristic) — compare total storage with number of gates/product-terms for cost/area trade-off.

OR_selection_configs_from_P_products = 2^P where each output can select any subset of P fixed product terms; unit = count of selection configurations (including the empty sum); this is not the count of all distinct Boolean functions of the original inputs, and different selections can be functionally identical.

Worked examples

  1. Implement two 3-input functions using a ROM and compute ROM size

Given inputs A,B,C (A = MSB). Functions:

  • F1 = 1 for minterms 1,3,4 (decimal), i.e. Σm(1,3,4)
  • F2 = 1 for minterms 2,3,6,7, i.e. Σm(2,3,6,7)

Steps:

  1. n = 3 inputs → number of addresses = 2^3 = 8.
  2. m = 2 outputs (F1,F2).
  3. ROM size = 2^n · m = 8 · 2 = 16 bits.
  4. Truth table (address order A B C = 000 to 111). Fill D0 = F1, D1 = F2 accordingly.

Final answer: ROM required = 16 bits (8 words × 2 bits per word). If address lines are A,B,C then list the 8 output pairs in the order 000→(0,0), 001→(1,0), 010→(0,1), 011→(1,1), 100→(1,0), 101→(0,0), 110→(0,1), 111→(0,1).

  1. Same functions implemented with PLA and PAL — count product terms

Steps (PLA):

  1. Write SOP for each output and minimize (use K-map mentally).
    • For F1 = Σm(1,3,4): minterms are 001,011,100. Group 001 and 011 to get A'·C; 100 remains as A·B'·C'. Therefore F1 = A'·C + A·B'·C'.
    • For F2 = Σm(2,3,6,7): minterms 010,011,110,111. Combine 010 & 011 → A'·B·C' and A'·B·C combine to A'·B. Combine 110 & 111 → A·B·(C' + C) → A·B. So F2 = A'·B + A·B = B.
  2. Distinct product terms found: A'·C, A·B'·C', and B (B is itself a product term). So P_required = 3.
  3. PLA needs at least 3 product lines and each output selects the products it needs: F1 selects (A'·C) and (A·B'·C'), F2 selects (B).

Steps (PAL):

  1. PAL has fixed OR gates — if there are two outputs and the device has sufficient product terms (for example, up to 8 per output on some classic PALs), mapping is identical: a PAL can implement the same product terms in the programmable AND plane and feed the fixed OR per output provided that each OR gate has enough product-term inputs for the required sum; in typical PALs, product terms are allocated per output and are not globally connectable to every OR. If OR-plane has restrictions, you might need extra product duplication.
  2. If a PAL OR gate cannot accept the product A'·C and A·B'·C' together because of limited fan-in, you must create extra product terms or restructure.

Final answers: PLA: 3 product terms required; ROM: 16 bits; PAL: feasible with 3 products if device OR structure allows connecting all P products to each output; otherwise duplicate product terms to meet OR-plane constraints.

  1. Designing the PLA network (model answer style)

Question: Show how to connect inputs in a PLA to implement F1 and F2 above, and label the product terms.

Model answer steps:

  1. List literals available on AND plane inputs: A, A', B, B', C, C'.
  2. Product term P0 = A'·C (connect A' and C); P1 = A·B'·C' (connect A, B', C'); P2 = B (connect B only; tie unused inputs to logic-1 as per device rules).
  3. OR plane: F1 = P0 + P1 (connect P0 and P1 to F1); F2 = P2 (connect P2 to F2).
  4. Draw PLA with three horizontal product lines labelled P0,P1,P2 and two vertical outputs F1,F2 with dots at appropriate intersections.

Final answer: Provide the PLA connection table or diagram as above; note that PLA has fewer product lines than the ROM words and is therefore smaller for this example.

Common mistakes

  • Not counting complemented inputs: forgetting that a PLA/ PAL provides both input and its complement to the AND plane (unless device does not provide complements — check datasheet).
  • Misunderstanding PAL: assuming OR-plane is always fully programmable — many PALs have limited OR fan-in or fixed OR matrix; check device assumptions in the question.
  • Mixing word order in ROM truth table: address bit order must be consistent (specify MSB/LSB) when writing the 2^n words.

For your exam

Kinds of questions you will see:

  • Definitions: define ROM/PLA/PAL and describe their architectures.
  • Short notes: compare ROM vs PLA vs PAL, advantages/disadvantages, typical applications.
  • Derivations: compute ROM size for given n,m; number of product terms required for PLA after minimisation.
  • Numericals: given Boolean functions, calculate ROM bits required; minimise functions and find PLA product-term count; map truth table into ROM contents.
  • Diagrams: draw ROM block with address/data lines; draw PLA grid showing programmable AND/OR connections; label inputs, product lines and outputs.

What full-marks answers include:

  • Clear definitions with bold naming of the device.
  • Correct formula use (e.g., ROM size = 2^n · m) and units (bits).
  • Correct minimisation using K-maps or Boolean algebra with steps shown.
  • A clear, labelled diagram when asked (describe which lines and labels appear).
  • Comment on device constraints where relevant (e.g., PAL OR-plane limitations).

Quick check

  1. For a ROM with 4 inputs and 3 outputs, how many bits must be stored?
  2. In a PLA the first plane forms ____ and the second plane forms ____. Fill blanks.
  3. Given F = Σm(1,2,3) with inputs A,B (A MSB) and C not present (so n=2), is ROM or PLA more efficient? (brief)

Answers: 1. 48 bits (2^4 · 3 = 16 · 3). 2. programmable AND (product-term) plane; programmable OR (sum) plane. 3. Either approach is acceptable: ROM needs 4 bits (2^2 · 1), while a PLA would use 2 product terms (A + B). Without a device-specific cost model you cannot say which is “more efficient”; state both resource counts and choose per the question’s constraints.

Finished this topic? Mark it so your progress, study plan and readiness keep up.

Stuck on something here?