Challenge Problems: Programmable Logic Devices
These challenge problems test deeper understanding. Only final answers are provided — work through each problem on your own.
Challenge 1: ROM-Based Multi-Output Function Implementation
Implement the following 4-input, 4-output combinational circuit using a \(16 \times 4\) ROM. Provide the complete ROM contents (all 16 addresses) in both binary and hexadecimal.
- \(F_0(A,B,C,D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)\)
- \(F_1(A,B,C,D) = \sum m(1, 3, 4, 6, 9, 11, 12, 14)\)
- \(F_2(A,B,C,D) = \sum m(0, 1, 2, 3, 8, 9, 10, 11)\)
- \(F_3(A,B,C,D) = \sum m(0, 1, 4, 5, 8, 9, 12, 13)\)
After filling in the ROM table, identify any pattern or simplification relating these outputs to the inputs.
Show Answer
ROM contents:
| Address | \(A\) | \(B\) | \(C\) | \(D\) | \(F_3\) | \(F_2\) | \(F_1\) | \(F_0\) | Hex |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | D |
| 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | E |
| 2 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 5 |
| 3 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 6 |
| 4 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | A |
| 5 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 9 |
| 6 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 2 |
| 7 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | D |
| 9 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | E |
| 10 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 5 |
| 11 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 6 |
| 12 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | A |
| 13 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 9 |
| 14 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 2 |
| 15 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
Pattern identified:
- \(F_0 = C \oplus D\) (XOR of two LSBs)
- \(F_1 = \overline{C \oplus D} = C \odot D\) (XNOR of two LSBs)
- \(F_2 = \overline{B}\) (complement of second input)
- \(F_3 = \overline{C}\) (complement of third input)
- Note that \(F_1 = \overline{F_0}\), and neither \(F_2\) nor \(F_3\) depends on \(A\) or \(D\).
- The output at address \(n\) equals the output at address \(n+8\) for all \(n\), confirming \(A\) is a don't-care for all outputs.
The ROM stores \(16 \times 4 = 64\) bits total, but only 3 input variables actually matter. A ROM with only 3 address lines (\(8 \times 4 = 32\) bits) could implement the same functions by ignoring input \(A\).
Challenge 2: PLA Programming with Shared Product Terms
Design a PLA for the following three functions of four variables. Minimize each function, identify all shared product terms, and provide the final PLA programming table showing the AND-plane and OR-plane connections. State the total number of unique product terms required.
- \(F_1(A,B,C,D) = \sum m(0, 1, 2, 3, 8, 9, 10, 11)\)
- \(F_2(A,B,C,D) = \sum m(0, 1, 4, 5, 8, 9, 12, 13)\)
- \(F_3(A,B,C,D) = \sum m(0, 2, 8, 10) + d(4, 6, 12, 14)\)
Show Answer
Minimized functions:
- \(F_1 = \overline{B}\) (minterms where \(B=0\): 0,1,2,3,8,9,10,11)
- \(F_2 = \overline{C}\) (minterms where \(C=0\): 0,1,4,5,8,9,12,13)
- \(F_3 = \overline{B}\,\overline{C}\) (minterms 0,2,8,10 with don't cares 4,6,12,14 allowing \(F_3 = \overline{C}\) or \(\overline{B}\,\overline{C}\); using don't cares optimally: \(F_3 = \overline{B}\,\overline{C}\), or with all don't cares: \(F_3 = \overline{C}\) shares with \(F_2\))
Taking \(F_3 = \overline{B}\,\overline{C}\) for maximum product term sharing:
Unique product terms:
| Term | Expression |
|---|---|
| \(P_1\) | \(\overline{B}\) |
| \(P_2\) | \(\overline{C}\) |
| \(P_3\) | \(\overline{B}\,\overline{C}\) |
But since \(P_3 = P_1 \cdot P_2\), the PLA AND plane must generate it as a separate product term (PLAs generate SOP, not multi-level).
PLA AND-plane programming:
| Term | \(A\) | \(\overline{A}\) | \(B\) | \(\overline{B}\) | \(C\) | \(\overline{C}\) | \(D\) | \(\overline{D}\) |
|---|---|---|---|---|---|---|---|---|
| \(P_1\) | -- | -- | -- | 1 | -- | -- | -- | -- |
| \(P_2\) | -- | -- | -- | -- | -- | 1 | -- | -- |
| \(P_3\) | -- | -- | -- | 1 | -- | 1 | -- | -- |
PLA OR-plane programming:
| Term | \(F_1\) | \(F_2\) | \(F_3\) |
|---|---|---|---|
| \(P_1\) | 1 | -- | -- |
| \(P_2\) | -- | 1 | -- |
| \(P_3\) | -- | -- | 1 |
Total unique product terms: 3
Alternative (if \(F_3\) uses don't cares to simplify to \(\overline{C}\)): only 2 product terms (\(\overline{B}\) and \(\overline{C}\)), with \(F_3\) sharing \(P_2\) with \(F_2\). This is the better PLA solution since it minimizes product term count.
With \(F_3 = \overline{C}\):
| Term | \(F_1\) | \(F_2\) | \(F_3\) |
|---|---|---|---|
| \(P_1 = \overline{B}\) | 1 | -- | -- |
| \(P_2 = \overline{C}\) | -- | 1 | 1 |
Optimal answer: 2 product terms, with \(P_2\) shared between \(F_2\) and \(F_3\).
Challenge 3: PAL Timing and Fan-In Limitations
A PAL16L8 device has the following specifications:
- 16 inputs (active low outputs, active high inputs)
- 8 outputs, each with a maximum of 7 product terms
- Maximum propagation delay: \(t_{pd} = 25\) ns (input pin to output pin)
- Each AND gate has a fan-in of 32 (16 inputs \(\times\) 2 for true/complement)
A designer needs to implement the function:
[G(A,B,C,D,E,F,H,I,J,K,L,M,N,P,Q,R) = \sum m(0, 1, 2, 3, 65534, 65535)]
This is a 16-variable function. Determine:
(a) Whether this function fits in a single PAL16L8 output. (b) The minimized SOP expression and number of product terms. (c) The maximum frequency at which this PAL can toggle the output.
Show Answer
(a)
The PAL16L8 has 16 inputs with fan-in of 32 per AND gate (16 true + 16 complement), so a product term can reference all 16 inputs. The question is whether \(G\) requires \(\leq 7\) product terms.
(b) Minimized SOP:
\(G = 1\) for minterms 0, 1, 2, 3, 65534, 65535.
-
Minterms 0-3: \(A=B=C=D=E=F=H=I=J=K=L=M=N=P=0\), \(QR \in \{00,01,10,11\}\)
These combine to: \(\overline{A}\,\overline{B}\,\overline{C}\,\overline{D}\,\overline{E}\,\overline{F}\,\overline{H}\,\overline{I}\,\overline{J}\,\overline{K}\,\overline{L}\,\overline{M}\,\overline{N}\,\overline{P}\) (14-literal term, \(Q\) and \(R\) drop out)
-
Minterm 65534 (\(= 2^{16} - 2\)): all 1s except LSB = \(ABCDEFHIJKLMNPQ\overline{R}\)
-
Minterm 65535 (\(= 2^{16} - 1\)): all 1s = \(ABCDEFHIJKLMNPQR\)
These combine to: \(ABCDEFHIJKLMNPQ\) (15-literal term, \(R\) drops out)
Minimized: \(G = \overline{A}\,\overline{B}\,\overline{C}\,\overline{D}\,\overline{E}\,\overline{F}\,\overline{H}\,\overline{I}\,\overline{J}\,\overline{K}\,\overline{L}\,\overline{M}\,\overline{N}\,\overline{P} + ABCDEFHIJKLMNPQ\)
Number of product terms: 2. This fits within the 7-term limit. Yes, it fits in one PAL16L8 output.
Note: The PAL16L8 has active-low outputs (output is inverted). The designer must account for the output inversion, implementing \(\overline{G}\) in the AND-OR array so the inverted output produces \(G\). Since \(\overline{G}\) has \(2^{16} - 2 - 4 = 65530\) minterms, direct implementation of \(\overline{G}\) is impractical. Instead, the designer should implement \(G\) and accept the inverted output, or use a PAL with programmable output polarity.
(c) Maximum toggle frequency:
[f_{toggle} = \frac{1}{2 \times t_{pd}} = \frac{1}{2 \times 25 \text{ ns}} = \frac{1}{50 \text{ ns}} = \mathbf{20 \text{ MHz}}]
The factor of 2 accounts for the output needing one propagation delay to go high and one to go low for a complete toggle cycle.
Challenge 4: CPLD Macrocell Allocation and Product Term Borrowing
A CPLD has 4 function blocks, each containing 8 macrocells. Each macrocell has a base allocation of 5 product terms, and can borrow up to 5 additional product terms from neighboring macrocells within the same function block (at the cost of disabling those neighbors).
A design requires implementing the following 6 outputs:
| Output | Function | Product Terms Required |
|---|---|---|
| \(F_1\) | \(\sum m(0,1,2,3,4,5,6,7)\) | 1 (simplifies to \(\overline{A}\)) |
| \(F_2\) | \(\sum m(1,3,5,7,8,10,12,14)\) | 4 |
| \(F_3\) | \(\sum m(0,2,5,7,8,9,10,11,13,15)\) | 6 |
| \(F_4\) | \(\sum m(1,2,3,4,6,7,9,11,12,13,14)\) | 8 |
| \(F_5\) | \(\sum m(0,1,3,5,6,7,8,10,11,12,14,15)\) | 9 |
| \(F_6\) | \(\sum m(2,3,4,5,6,7,8,9,10,11,12,13)\) | 3 (simplifies to \(B \oplus C\)... requires 3 SOP terms) |
All functions use 4 inputs (\(A\), \(B\), \(C\), \(D\)).
Determine:
(a) Which outputs fit in a single macrocell without borrowing? (b) Which outputs require product term borrowing, and how many extra terms must be borrowed? (c) Can all 6 outputs fit in a single function block (8 macrocells)? Show the macrocell allocation map. (d) What is the minimum number of function blocks required?
Show Answer
(a) Outputs fitting in a single macrocell (≤ 5 product terms):
| Output | Product Terms | Fits without borrowing? |
|---|---|---|
| \(F_1\) | 1 | Yes |
| \(F_2\) | 4 | Yes |
| \(F_3\) | 6 | No (needs 1 extra) |
| \(F_4\) | 8 | No (needs 3 extra) |
| \(F_5\) | 9 | No (needs 4 extra) |
| \(F_6\) | 3 | Yes |
\(F_1\), \(F_2\), and \(F_6\) fit in a single macrocell without borrowing.
(b) Product term borrowing requirements:
| Output | Needed | Base | Borrowed | Donor macrocells disabled |
|---|---|---|---|---|
| \(F_3\) | 6 | 5 | 1 | 1 macrocell (donates up to 5 terms) |
| \(F_4\) | 8 | 5 | 3 | 1 macrocell (donates 3 of its 5 terms) |
| \(F_5\) | 9 | 5 | 4 | 1 macrocell (donates 4 of its 5 terms) |
Total borrowed: 1 + 3 + 4 = 8 product terms from 3 donor macrocells.
(c) Single function block allocation (8 macrocells):
| Macrocell | Assignment | Product Terms Used |
|---|---|---|
| MC0 | \(F_1\) (output) | 1 of 5 |
| MC1 | \(F_2\) (output) | 4 of 5 |
| MC2 | \(F_6\) (output) | 3 of 5 |
| MC3 | \(F_3\) (output) | 5 base + 1 borrowed = 6 |
| MC4 | Donor for \(F_3\) | Lends 1 term → disabled as output |
| MC5 | \(F_4\) (output) | 5 base + 3 borrowed = 8 |
| MC6 | Donor for \(F_4\) | Lends 3 terms → disabled as output |
| MC7 | \(F_5\) (output) — PROBLEM | Needs 5 base + 4 borrowed = 9, but no remaining macrocell to borrow from |
No — all 6 outputs cannot fit in a single function block. \(F_5\) requires borrowing from a donor, but all 8 macrocells are already used (6 outputs + 2 donors). There is no macrocell left to donate to \(F_5\).
(d) Minimum number of function blocks: 1 function block is sufficient with re-arrangement.
Re-allocating: move \(F_5\) (the most demanding output) to get its donor first:
| Macrocell | Assignment | Product Terms Used |
|---|---|---|
| MC0 | \(F_1\) (output) | 1 of 5 |
| MC1 | \(F_2\) (output) | 4 of 5 |
| MC2 | \(F_6\) (output) | 3 of 5 |
| MC3 | \(F_5\) (output) | 5 base + 4 borrowed = 9 |
| MC4 | Donor for \(F_5\) | Lends 4 terms → disabled |
| MC5 | \(F_4\) (output) | 5 base + 3 borrowed = 8 |
| MC6 | Donor for \(F_4\) | Lends 3 terms → disabled |
| MC7 | \(F_3\) (output) | 5 base + 1 borrowed... no donor left |
Still fails. The fundamental issue: 6 outputs + 3 donors = 9 macrocells needed, but only 8 are available per function block.
Minimum: 2 function blocks.
Optimal allocation across 2 function blocks:
Function Block 1 (5 macrocells used):
| MC | Assignment | Terms |
|---|---|---|
| MC0 | \(F_5\) (output) | 9 (5 + 4 borrowed) |
| MC1 | Donor for \(F_5\) | Lends 4 |
| MC2 | \(F_4\) (output) | 8 (5 + 3 borrowed) |
| MC3 | Donor for \(F_4\) | Lends 3 |
| MC4 | \(F_3\) (output) | 6 (5 + 1 borrowed) |
| MC5 | Donor for \(F_3\) | Lends 1 |
| MC6–7 | Unused | — |
Function Block 2 (3 macrocells used):
| MC | Assignment | Terms |
|---|---|---|
| MC0 | \(F_1\) (output) | 1 |
| MC1 | \(F_2\) (output) | 4 |
| MC2 | \(F_6\) (output) | 3 |
| MC3–7 | Unused (available for future expansion) | — |
Total: 2 function blocks, 9 macrocells (6 outputs + 3 donors). The CPLD needs at least a 16-macrocell device (2 function blocks × 8 macrocells).
Challenge 5: PLD Device Selection Comparison
A digital system has the following requirements:
- 20 input signals, 12 output signals
- 8 outputs are combinational functions averaging 6 product terms each
- 4 outputs are registered (sequential, requiring flip-flops)
- The design must power up instantly (no configuration delay)
- Operating frequency: 50 MHz
- Production volume: 500 units
- Budget: $5 per unit for the programmable device
Evaluate each PLD technology (ROM, PLA, PAL, CPLD, FPGA) against these requirements. State which device is selected and justify the decision by completing a comparison matrix.
Show Answer
Requirements summary:
- 20 inputs, 12 outputs (8 combinational + 4 registered)
- Average 6 product terms per combinational output
- Instant power-on (non-volatile configuration)
- 50 MHz operation
- 500 units at $5/unit budget
Evaluation matrix:
| Criterion | ROM | PLA | PAL | CPLD | FPGA (SRAM) |
|---|---|---|---|---|---|
| 20 inputs supported? | No (\(2^{20} = 1\)M words, impractical) | Possible but limited density | Yes (PAL22V10) | Yes | Yes |
| 12 outputs? | Yes (if ROM exists) | Limited (typ. 8-10) | PAL22V10 has 10 | Yes (64+ I/O) | Yes |
| 6 product terms/output? | N/A (ROM stores all minterms) | Yes (shared terms) | Marginal (PAL22V10 has 8-16/output) | Yes | N/A (uses LUTs) |
| Registered outputs? | No (ROM is combinational only) | No (basic PLA) | Yes (PAL22V10 has registered macrocells) | Yes | Yes |
| Instant power-on? | Yes (mask ROM) | Yes (fuse-based) | Yes (fuse-based) | Yes (Flash/EEPROM) | No (needs bitstream load) |
| 50 MHz? | ~25-50 MHz | ~15-30 MHz (slow, two programmable planes) | ~50-100 MHz | ~100+ MHz | ~200+ MHz |
| $5/unit at 500 qty? | No (custom mask cost) | ~$3-8 | ~$2-5 | ~$3-10 | ~$5-50 |
Elimination:
- ROM: Eliminated. 20 inputs means \(2^{20} \times 12 = 12\) Mbit ROM. Commercially impractical and lacks registered outputs.
- PLA: Eliminated. Too slow for 50 MHz. Limited output count. No registered outputs in basic PLAs.
- FPGA (SRAM): Eliminated. Fails instant power-on requirement. Also likely exceeds $5 budget for this design size at 500 units.
- PAL: PAL22V10 has 22 inputs (OK), 10 outputs (not enough for 12). Could use two PAL22V10s but complicates design. Registered outputs available. Speed is borderline at 50 MHz depending on grade.
Selected device: CPLD
Justification:
- Capacity: A small CPLD (e.g., Xilinx CoolRunner-II XC2C64 or Lattice MachXO2-256) provides 64+ macro-cells, easily handling 20 inputs and 12 outputs.
- Product terms: CPLD function blocks provide sufficient product terms per output, with borrowing for outputs needing more than the base allocation.
- Registered outputs: Every CPLD macro-cell contains a configurable flip-flop.
- Instant power-on: CPLDs use non-volatile configuration (Flash or EEPROM). The device is operational within microseconds of power application.
- Speed: CPLDs with deterministic timing easily achieve 50 MHz with margin.
- Cost: Small CPLDs are available for $2-5 at moderate volumes, within budget.
- Development: Standard HDL design flow with free vendor tools.
Final answer: A small Flash-based CPLD is the optimal choice, meeting all requirements with margin on speed, capacity, and cost.