Question 1 of 5: Combinational Logic — PLD Survey, K-map/NAND Synthesis, Decoder Realization

Question 1: Combinational Logic — PLD Survey, K-map/NAND Synthesis, Decoder Realization (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.

Part (a). A PAL (Programmable Array Logic) is a mask-fixed-OR/user-programmable-AND device: the AND (product-term) array is fuse/antifuse programmable, but the OR array wiring is fixed at fabrication, so each output sums a fixed, small set of product terms — cheap, fast, but limited fan-in per output and no sequential resources beyond an optional output flip-flop. A ROM (Read-Only Memory) used as logic is the dual: its address decoder is a FIXED, fully-populated AND array (every possible minterm is generated), while the OR array (the stored data bits) is fully programmable — so a ROM can realize any function of its address lines with no minimization needed, at the cost of exponential growth (2^n words for n inputs) and no logic minimization benefit. An FPGA (Field-Programmable Gate Array) is architecturally different from both: it is a fine-grained array of small look-up-table (LUT) based logic cells plus flip-flops, connected through a programmable routing fabric, so both the combinational function AND the interconnect are field-configurable; this supports arbitrarily large, deeply sequential, pipelined designs (state machines, arithmetic datapaths) that neither a PAL nor a ROM can hold economically.

Approach (parts b, c). For part (b), minimize each of F1, F2, F3 by K-map, realize each resulting SOP as a two-level AND-OR circuit, then apply the standard double-negation (bubble-pushing) transformation to redraw the same two levels using 2-input NAND gates only. For part (c), decode the three most-significant variables (w,x,y) with the given 74LS138 and combine the needed active-low outputs with z using a handful of extra gates.

1. K-map for F1.

   wx / yz	00	01	11	10
   00	1	0	0	1
   01	1	0	1	1
   11	0	1	0	0
   10	0	1	1	0

   The quad {0,2,4,6} (w=0, z=0, x and y free) gives the essential group w′z′. The remaining minterms {7,9,11,13} each need a pair: {6,7}→w′xy, {9,11}→wx′z, {9,13}→wy′z (minterm 9 is shared by the last two pairs — both are needed since 11 and 13 have no other partner). $$\boxed{F_1 = w'z' + w'xy + wx'z + wy'z}$$
2. K-map for F2.

   wx / yz	00	01	11	10
   00	1	1	0	0
   01	1	0	0	1
   11	0	0	0	1
   10	1	0	0	1

   No quad exists (every 4-cell rectangle picks up a 0). Minterm 1 pairs only with 0 (w′x′y′); the remaining {4,6,8,10,14} are covered by three more pairs: {0,4}→w′y′z′, {6,14}→xyz′, {8,10}→wx′z′. $$\boxed{F_2 = w'x'y' + w'y'z' + xyz' + wx'z'}$$
3. K-map for F3.

   wx / yz	00	01	11	10
   00	0	1	1	0
   01	1	0	1	0
   11	1	0	1	0
   10	0	1	0	0

   Again no quad exists. Minterms 12 and 15 and 9 are each forced onto a single pair — {4,12}→xy′z′, {7,15}→xyz, {1,9}→x′y′z — leaving minterm 3, covered by {1,3}→w′x′z (reusing minterm 1). $$\boxed{F_3 = x'y'z + xy'z' + xyz + w'x'z}$$ All three SOPs were re-verified against their target minterm lists by brute-force truth table.
4. NAND-NAND conversion (2-input NAND only). Each SOP is realized in the standard two stages: (i) every product term is built as a NAND (not a plain AND) — a 2-literal term needs one 2-input NAND, a 3-literal term needs a 2-input NAND on the first pair, an inverter (a NAND with both inputs tied together) to recover the true AND, then a second NAND with the third literal, for 3 gates total; (ii) the term outputs, each already the complement of its product term, are combined by an AND-then-invert tree of 2-input NANDs, whose final stage needs no extra inverter — by De Morgan this exactly reconstructs the OR of the original terms: $$F = \overline{\overline{T_1}\cdot\overline{T_2}\cdots} = T_1+T_2+\cdots$$ CheckAssumes both the true and complemented form of each input variable (w,w′,x,x′,y,y′,z,z′) are available at the circuit boundary — standard for SOP-to-NAND synthesis problems; each complement not otherwise available costs one extra NAND-as-inverter.
5. F1 circuit (fully worked). F1 has one 2-literal term (1 gate) and three 3-literal terms (3 gates each = 9), combined by a 4-input AND-then-invert-tree (5 gates): 1+9+5 = 15 NAND gates.
   F1 realized in 2-input NAND-NAND form (15 gates): each product term built as a cascaded NAND, combined by a final AND-then-invert tree.
6. F2 and F3 circuits (identical method). F2 and F3 each have four 3-literal terms (4×3 = 12 gates) combined by the same 4-input tree (5 gates): 12+5 = 17 NAND gates each.
   F2 realized in 2-input NAND-NAND form (17 gates), identical method.
   F3 realized in 2-input NAND-NAND form (17 gates), identical method.
7. Whole-circuit gate economy. Building F1, F2, F3 independently costs 15+17+17 = 49 NAND gates. Since the question asks for the overall circuit to use a minimum number of gates, the shared literal pair xy is worth flagging: it appears inside F1′s w′xy term, F2′s xyz′ term, and F3′s xyz term. Computing NAND(x,y) and its inverted (true-AND) form ONCE and wiring that single 2-gate sub-circuit to all three consuming stages removes 2 duplicate NAND gates per reuse (4 gates saved across the two extra reuses), a legitimate multi-output economy on top of the per-function minimal SOPs already derived.

Part (c) — Given. F2 = w′x′y′ + w′y′z′ + xyz′ + wx′z′ from part (b); a 74LS138 3-to-8 decoder with active-low outputs Y0–Y7 and enables E1,E2 (active-low) and E3 (active-high).

Find. A realization of F2(w,x,y,z) using the decoder plus the fewest additional gates.

7. Assign decoder inputs and regroup F2 by the top three bits. Tie A2A1A0 = w,x,y (E1=E2=0, E3=1 so the decoder is permanently enabled) and re-examine F2′s minterm list {0,1,4,6,8,10,14} grouped by the (w,x,y) value: wxy=000 covers BOTH z=0 (m0) and z=1 (m1), so line Y0 alone (regardless of z) already satisfies F2 for that group. Each of wxy∈{010,011,100,101,111} (decoder lines Y2,Y3,Y4,Y5,Y7) contributes only its z=0 half (m4,m6,m8,m10,m14) — so those five lines must additionally be qualified by z′. No other wxy group is used. $$\boxed{F_2 = \overline{Y_0} + z'\left(\overline{Y_2}+\overline{Y_3}+\overline{Y_4}+\overline{Y_5}+\overline{Y_7}\right)}$$ (bars denote the decoder’s native active-low sense)
8. Combine the active-low lines. Y0′ needs one inverter to turn the active-low "line 0 selected" pulse into an active-high term. The five-way "any of Y2,Y3,Y4,Y5,Y7 selected" term is exactly a wide NAND of those active-low signals (NAND(Y2,…,Y7) = Y2′+…+Y7′, true precisely when any one of them is LOW/selected) — one 5-input NAND (or an equivalent 2-input gate tree). ANDing that with z′ (one more inverter for z, one AND gate) and ORing the result with Y0′ (one OR gate) completes the realization in 5 extra gates beyond the decoder itself.