Question 1 of 5: Gate-Level Circuit Analysis, NAND Synthesis and PLD Implementation

Question 1: Gate-Level Circuit Analysis, NAND Synthesis and PLD 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. Figure Q1 is a 4-input ($A,B,C,D$), single-output ($Y$) combinational network built from an inverter on $B$, an inverter on $A$, a NAND gate, two XOR gates and a 3-input NOR gate, traced below; a PAL16L8 device (programmable AND array feeding a fixed OR array, per the appendix data sheet) is available for part (c).

Find. (i) The simplified Boolean expression for $Y$; (ii) a NAND-only realization of the same function; (b) the main PAL-vs-FPGA architectural differences; (c) a PAL16L8 fuse programming that realizes $Y$.

Approach. Write the Boolean expression at the output of every gate in signal-flow order, substitute into the final NOR, then simplify with the complement law $1+X=1$ and the absorption law $X'+XY=X'+Y$ before synthesizing the result in NAND-only form and as a PAL16L8 fuse map.

1. Part (a)(i) — trace the three first-stage gate outputs. From the figure, $B$ is inverted to $B'$ and $A$ is separately inverted to $A'$. The three intermediate signals are $$N_1=(A\cdot B')', \qquad N_2 = C\oplus A', \qquad N_3 = A'\oplus D,$$ where $N_1$ is the NAND of $A$ and $B'$, and $N_2,N_3$ are the two XOR gates. All three feed the final 3-input NOR gate, so $$Y=\left(N_1+N_2+N_3\right)' = \Big[(AB')' + (C\oplus A') + (A'\oplus D)\Big]'.$$
2. Part (a)(i) — expand every term with De Morgan and the XOR identity $X\oplus Y=XY'+X'Y$. $$(AB')' = A'+B, \qquad C\oplus A' = CA + C'A', \qquad A'\oplus D = A'D'+AD.$$ Summing the three terms before the final complement, $$S = (A'+B) + (CA+C'A') + (A'D'+AD).$$
3. Part (a)(i) — collect every $A'$ term. $S$ contains $A'$, $C'A'$ and $A'D'$; factoring, $A'+C'A'+A'D' = A'(1+C'+D')=A'$ since $1+X=1$. So $$S = A' + B + CA + AD = A' + B + A(C+D).$$
4. Part (a)(i) — apply absorption $X'+XY=X'+Y$ with $X=A,\ Y=(C+D)$. $A'+A(C+D)=A'+(C+D)$, so $$S = A' + B + C + D.$$ Taking the final complement (the output NOR gate), $$Y = S' = (A'+B+C+D)' = \boxed{A\cdot B'\cdot C'\cdot D'}$$ by De Morgan's theorem.
5. Part (a)(ii) — build the 4-input AND from NAND gates only. $B$, $C$ and $D$ each first pass through a NAND gate tied as an inverter (driving both inputs of a NAND with the same signal $X$ gives $(X\cdot X)'=X'$) to obtain $B',C',D'$; $A$ needs no inversion. A two-input AND is then built from a NAND followed by a second NAND used as an inverter, since $\overline{\overline{AB'}}=AB'$. Cascading three such AND stages, $$A\cdot B' \;\to\; (A\cdot B')\cdot C' \;\to\; \big[(A\cdot B')\cdot C'\big]\cdot D' = Y,$$ realizes the full 4-input AND using 3 inverting NANDs plus $3\times2=6$ AND-building NANDs, i.e. 9 NAND gates in total.

6. Part (b) — PAL vs. FPGA. A PAL (Programmable Array Logic) has a programmable AND array feeding a fixed OR array: the designer blows fuses to select which literals enter each product term, but the OR-array wiring that sums product terms into an output pin is fixed at fabrication, which caps the number of product terms and the total gate count per output. A PAL is one-time (fuse) or electrically reprogrammable (GAL), but is purely combinational-plus-simple-macrocell, with no internal routing fabric — cheap, low-power and fast for small "glue logic" and simple state machines. An FPGA (Field-Programmable Gate Array) instead contains thousands to millions of small look-up-table (LUT) based logic cells together with embedded flip-flops, block RAM and a rich programmable interconnect fabric, all configured (typically from external SRAM, so reconfigurable at every power-up) to realize arbitrarily large combinational and sequential designs, including full datapaths and processors. FPGAs cost and consume more but scale to orders of magnitude more logic than a PAL/GAL and support in-system reconfiguration.
7. Part (c) — program the PAL16L8 to realize $Y=AB'C'D'$. The PAL16L8's AND array brings every input in true and complemented form to each product-term row; only one product term is needed here, so a single AND-array row is fused active at the $A$, $B'$, $C'$ and $D'$ columns (every other crosspoint on that row is left blown/open, contributing nothing), and every other product-term row feeding that output's fixed OR gate is left unprogrammed (logic 0). The fixed OR array then passes the single term straight through. The PAL16L8's output macrocells use an active-low buffer, so the physical pin (an output-only pin per the appendix pin-out, e.g. pin 19) delivers $\overline{Y}=\overline{AB'C'D'}$; an external inverter, or equivalently programming the complementary sum-of-literals term, recovers $Y$ itself. No output feedback path is needed since $Y$ depends only on the four primary inputs.