Question 2 of 5: ROM vs. FPGA, PAL16L8 and Decoder Implementation

Question 2: ROM vs. FPGA, PAL16L8 and Decoder Implementation (25 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. Four 4-variable Boolean functions $F_1$–$F_4$ specified by their minterm lists; a PAL16L8 device (programmable AND array, fixed OR array, active-low output buffers, per the Appendix data sheet) and a 74LS138 3-to-8 decoder (active-low outputs, enabled on $E_3{=}1,E_2{=}0,E_1{=}0$) are available.

Find. (a) The principal ROM-vs-FPGA differences; (b) minimized SOPs for $F_1$–$F_4$ and their PAL16L8 fuse programming; (c) a decoder-based realization of $F_4$ using the fewest additional gates.

Approach. Minimize each $F_i$ by K-map, map each product term onto one AND-array row of the PAL16L8 with the fixed OR array summing them. For part (c), decode $(w,x,y)$ with the 3-to-8 decoder (its 3 select lines can only cover 3 of the 4 variables), take the Shannon expansion of $F_4$ about $z$ on each of the 8 decoder lines, and gate each active line with $z$, $z'$, a direct connection, or nothing, before a final OR.

1. Part (a) — ROM vs. FPGA. A ROM (Read-Only Memory) implements a function as a fixed word: $n$ address lines select one of $2^n$ pre-programmed output words, giving a simple, guaranteed-correct realization of any function of $n$ inputs, but with no internal routing and output width/propagation delay fixed by the memory array — it does not scale efficiently to large multi-output combinational designs and has no native support for pipelined/sequential logic beyond an external register. An FPGA (Field-Programmable Gate Array) instead contains thousands to millions of small look-up-table (LUT) based logic cells with embedded flip-flops, block RAM and a rich programmable interconnect fabric, configured (typically from external SRAM, hence reconfigurable at every power-up) to realize arbitrarily large, deeply pipelined combinational and sequential designs, including full processors. FPGAs cost and consume more per gate for small functions but scale to far larger designs and support true in-system reconfiguration of both logic and routing, which a ROM's fixed address-to-data mapping cannot offer.
2. Part (b) — minimize $F_1$–$F_4$ by K-map. Grouping each function's minterms gives $$F_1 = \overline{w}\,\overline{z} + wz\overline{x} + wz\overline{y} + xy\overline{w},$$ $$F_2 = xy\overline{z} + w\overline{x}\,\overline{z} + x\overline{w}\,\overline{z} + \overline{w}\,\overline{x}\,\overline{y},$$ $$F_3 = xyz + x\overline{y}\,\overline{z} + z\overline{w}\,\overline{x} + z\overline{x}\,\overline{y},$$ $$\boxed{F_4 = wxy + xy\overline{z} + z\overline{w}\,\overline{y} + w\overline{x}\,\overline{y}\,\overline{z}}$$
3. Part (b) — program the PAL16L8. Each $F_i$ is assigned its own output pin; the AND array brings every input ($w,x,y,z$ and their complements) to each product-term row, so one row is fused active per product term of the minimized SOP above (every other crosspoint on that row left blown/open), and every unused row feeding that output is left entirely unprogrammed. The fixed OR array sums the fused rows for each output. As on every PAL16L8 output macrocell, the buffer is active-low, so each physical output pin delivers the complement of its function ($\overline{F_1},\overline{F_2},\overline{F_3},\overline{F_4}$); an external inverter (or programming the complementary term set instead) recovers the true function at each pin.

4. Part (c) — Shannon-expand $F_4$ about $(w,x,y)$. Grouping $F_4$'s minterms $\{1,5,6,8,14,15\}$ by their $(w,x,y)$ triple and reading off the value at $z{=}0$ and $z{=}1$ gives the coefficient on each decoder line $D_i$ ($i$ = binary value of $wxy$): $$D_0{:}\ z,\quad D_1{:}\ 0,\quad D_2{:}\ z,\quad D_3{:}\ z',\quad D_4{:}\ z',\quad D_5{:}\ 0,\quad D_6{:}\ 0,\quad D_7{:}\ 1.$$ So $\boxed{F_4 = D_0\cdot z + D_2\cdot z + D_3\cdot z' + D_4\cdot z' + D_7}$. Only 4 AND2 gates (one per non-trivial, non-direct line) and 1 five-input OR gate are needed beyond the decoder itself, since $D_1,D_5,D_6$ need no gate at all (never contribute) and $D_7$ feeds the OR directly (coefficient 1).