22-Elec-A4 Digital Systems and Computers · December 2018
Question 1 of 6: NAND / NOR gate realizations of a Boolean function
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
22-Elec-A4 Digital Systems & Computers — 2018-Dec (Worked Solutions)
National Exams — December 2018 · 16-Elec-A4 Digital Systems & Computers. Closed book, 3 hours. Six questions, 12 marks each; the rubric requires any five, but all six are solved here as a study resource. Approved Casio/Sharp calculator permitted. A Boolean-identity table and the flip-flop excitation table are supplied with the paper and are used where needed.
Reference texts. M. M. Mano & M. D. Ciletti, Digital Design (6th ed.) — Boolean minimization, NAND/NOR realizations, K-maps, synchronous counters; J. F. Wakerly, Digital Design: Principles and Practices (5th ed.) — counters, PAL/PLA devices; C. Hamacher, Z. Vranesic, S. Zaky & N. Manjikian, Computer Organization and Embedded Systems (6th ed.) — CPU registers, endianness, stacks, parallel I/O; Motorola M68HC11 Reference Manual — big-endian storage, PUSH semantics, Port B addressing.
Question 1: NAND / NOR gate realizations of a Boolean function (12 marks)
Given. The two universal-gate primitives (a)–(b) and the function $g = ((A+B)\overline{C} + B\overline{C}D)\,E\,(A+B)$, to be drawn in three technologies without algebraic simplification.
Find. A NOT and an OR from NAND gates, then gate-for-gate schematics of $g$ in AND/OR/NOT, NAND-only, and NOR-only logic.
Approach. Parts (a)–(b) use the NAND identities; for (c) build the parenthesised structure literally; for (d)/(e) push inversion bubbles through each AND–OR level (De Morgan) so every gate becomes a NAND (resp. NOR), reusing the shared term $(A+B)$.
(a) NOT from one NAND. Tying both inputs of a NAND to the same signal gives $\overline{A\cdot A}=\overline{A}$, so a single two-input NAND with its inputs joined is an inverter.
Part (a): one NAND wired as an inverter, $\overline{A}=\mathrm{NAND}(A,A)$.
(b) OR from NAND. By De Morgan $A+B=\overline{\overline{A}\cdot\overline{B}}=\mathrm{NAND}(\overline{A},\overline{B})$. Invert each input with a NAND-inverter (part a), then NAND the two results — three NAND gates in all.
Part (b): $A+B=\mathrm{NAND}(\overline{A},\overline{B})$ using three NAND gates.
(c) AND / OR / NOT, as written. Realise each bracket directly: one OR forms $(A+B)$ (reused twice), an inverter forms $\overline{C}$, a 2-input AND forms $(A+B)\overline{C}$, a 3-input AND forms $B\overline{C}D$, an OR sums them, and a final 3-input AND multiplies that sum by $E$ and by $(A+B)$.
Part (c): $g$ built literally with AND, OR and NOT gates; the $(A+B)$ OR-gate output feeds both the first AND and the output AND.
(d) NAND only. The middle AND–OR pair maps to the classic NAND–NAND form: $g_1=\mathrm{NAND}(A{+}B,\overline{C})=\overline{(A+B)\overline{C}}$ and $g_2=\mathrm{NAND}(B,\overline{C},D)=\overline{B\overline{C}D}$, then $s=\mathrm{NAND}(g_1,g_2)=(A+B)\overline{C}+B\overline{C}D$. The output AND becomes $\mathrm{NAND}(s,E,A{+}B)$ followed by a NAND-inverter. With $A+B=\mathrm{NAND}(\overline{A},\overline{B})$ that is $\boxed{6}$ NAND gates.
Part (d): NAND-only realization (6 gates). $g_1,g_2$ are the inverted product terms; $\mathrm{NAND}(g_1,g_2)$ performs the OR.
(e) NOR only. Dually, $m_1=\mathrm{NOR}(A,B)=\overline{A+B}$, $t_1=\mathrm{NOR}(m_1,C)=(A+B)\overline{C}$, $t_2=\mathrm{NOR}(\overline{B},C,\overline{D})=B\overline{C}D$, $p=\mathrm{NOR}(t_1,t_2)=\overline{s}$, and $g=\mathrm{NOR}(p,\overline{E},m_1)=s\cdot E\cdot(A+B)$ — $\boxed{5}$ NOR gates, the shared $\overline{A+B}$ feeding both $t_1$ and the output.
Part (e): NOR-only realization (5 gates), using the supplied literal complements $\overline{B},\overline{D},\overline{E}$.
Every wire was checked by truth table: the (c), (d) and (e) networks reproduce $g$ on all 32 input combinations, confirming the bubble-pushing introduced no sign error.
