Magnitude Comparators, Parity Generators & Programmable Logic (PROM, PLA, PAL)
“Cascaded comparator delays, even/odd parity generation, and architectural differences between PROM, PLA, and PAL.”
1.Programmable Logic Structures & Comparators
§ 3.1.Programmable Logic Devices (PLDs) allow digital systems to be fabricated using standard off-the-shelf chips programmed by the engineer rather than fixed gate layouts.
Architectural Comparison Matrix:
1. PROM: Contains an n-to-2^n decoder (fixed AND array generating every minterm) feeding into a programmable OR array. A PROM can implement any function of n variables, but cannot share product terms and scales exponentially.
2. PLA (Programmable Logic Array): Both the AND array (which forms product terms) and the OR array (which sums product terms) are fully programmable. Multiple outputs can share the exact same product term, making PLAs extremely space-efficient for multi-output minimization.
3. PAL (Programmable Array Logic): The AND array is programmable, but the OR array is completely fixed (each output OR gate receives a fixed group of product terms, e.g., 4 or 8 terms). PALs are faster and cheaper to manufacture than PLAs because only one array of fuses is programmable.
Magnitude Comparators: Compare two n-bit numbers A and B and generate three outputs: A > B, A = B, and A < B. Equality is computed as \prod_{i=0}^{n-1} (A_i \odot B_i). Greater-than condition evaluates from MSB down to LSB: A > B if A_{n-1} > B_{n-1}, or (A_{n-1} = B_{n-1} and A_{n-2} > B_{n-2}), etc.
Only PLAs can share product terms between outputs. If output F_1 = AB + CD and F_2 = AB + EF, a PLA requires only 3 AND gates (AB, CD, EF). A PAL requires 4 AND gates because the AND terms feeding F_1's OR gate cannot connect to F_2's OR gate.
2. Worked Analysis: PLA Capacity & Product Term Sharing
Optimize multiple outputs simultaneously to maximize shared product terms.
Problem Statement (Modeled on GATE Pattern):
Determine the minimum number of product terms (AND gates) required in a PLA to implement the two functions:
F1(A, B, C) = Sigma m(1, 2, 3, 5, 7)
F2(A, B, C) = Sigma m(1, 3, 4, 5)
Step 1: Simplify F1 individually:
Minterms: 1 (001), 2 (010), 3 (011), 5 (101), 7 (111).
Combine (1, 3, 5, 7) -> C.
Combine (2, 3) -> A'B.
F1 = C + A'B. (Product terms: C, A'B).
Step 2: Simplify F2 individually:
Minterms: 1 (001), 3 (011), 4 (100), 5 (101).
Combine (1, 3, 5) -> C with 1 and 3? (1, 3) = A'C; (1, 5) = B'C.
Combine (4, 5) -> AB'.
F2 = B'C + AB' (or A'C + AB').
Step 3: Analyze potential shared product terms:
Can F2 use C? If F2 uses C, minterms 1, 3, 5 are covered, but 3 is included (which is in F2). However, C also covers minterm 7, which is NOT in F2!
So F2 cannot use the lone term C.
What if F1 uses B'C? Notice C = B'C + BC.
If F1 is expressed as: F1 = B'C + BC + A'B = B'C + (B)(C + A') = B'C + BC + A'B.
Alternatively: can F1 and F2 share B'C?
For F1: covers 1, 5 (B'C). Remaining minterms in F1 are 2, 3, 7: covered by A'B (2, 3) and BC (3, 7).
Terms: {B'C, A'B, BC}. (3 terms for F1).
For F2: minterms 1, 5 (covered by B'C), 4 (covered by AB' with 5), 3 (covered by A'C with 1).
Total unique terms needed: C (for F1), A'B (for F1), B'C (for F2), AB' (for F2). Total = 4 AND gates.
Result: A PLA requires a minimum of 4 product terms to implement both functions.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
The most thorough digital logic series — textbook quality at no cost.
GATE-focused digital logic with exam-style numericals.