22-Elec-A4 Digital Systems and Computers · May 2015

Question 1 of 6: Gate-level realisations of a Boolean function

Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)

Notes on this paper

Paper format. National Exams, May 2015 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions are printed and five constitute a complete exam; every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1. A flip-flop excitation table and a Boolean-identity sheet are attached to the paper. All six questions are solved below, so that the set works as a complete study resource.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design, 5th ed. — Ch. 2 (Boolean algebra and gate-level minimisation), Ch. 3 (K-maps, NAND/NOR implementation), Ch. 4 (combinational design: adders and subtractors), Ch. 5 (synchronous sequential logic, state tables and diagrams, Moore vs Mealy).
J. F. Wakerly, Digital Design: Principles and Practices, 4th ed. — Ch. 4 (combinational design practices, bubble-to-bubble logic), Ch. 7 (latches, flip-flops and their excitation tables).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — Ch. 2 (byte order, stacks), Ch. 3 (I/O, interrupt-driven serial transfer).
Freescale/Motorola, M68HC11 Reference Manual (rev. 6) — stack operation of PSHX/PSHY, big-endian storage of 16-bit operands, SCI registers.
TIA/EIA-232-F, Interface Between Data Terminal Equipment and Data Circuit-Terminating Equipment Employing Serial Binary Data Interchange — signal-level definitions used in Question 5(b).

Question 1 (12 marks) — Gate-level realisations of a Boolean function

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. The five-variable function $g=\left(\overline{(A+B)\cdot\overline{C}}+B\overline{C}D\right)\cdot E\cdot(A+B)$, gates of two and three inputs, and — for parts (d) and (e) only — both polarities of every literal ($A,\overline{A},B,\overline{B},\dots$) available as inputs.

Find. (a) an inverter built from a single NAND; (b) a two-input OR built from NANDs; and three gate-level drawings of $g$ — (c) a literal AND/OR/NOT transcription, (d) a NAND-only network, (e) a NOR-only network — with the expression left exactly as printed, unsimplified.

Approach. Use the two universal-gate identities $\overline{X\cdot X}=\overline{X}$ and $\overline{\overline{X}\cdot\overline{Y}}=X+Y$ to get the primitives, then transcribe $g$ operator-by-operator and convert each operator to the target gate by De Morgan “bubble pushing”, never by algebraic simplification.

Build the inverter and the OR from NANDs. Tying both NAND inputs to the same signal gives $\overline{A\cdot A}=\overline{A}$, so one NAND is an inverter. Feeding a third NAND with the two complemented literals gives, by De Morgan, $\overline{\overline{A}\cdot\overline{B}}=A+B$. Three NANDs therefore realise a two-input OR: two as inverters and one as the output stage.
Name the sub-expressions of $g$. Working outwards, write $P=A+B$, $u=P\cdot\overline{C}$, $v=B\overline{C}D$ and $w=\overline{u}+v$, so that $\boxed{g=w\cdot E\cdot P}$. Every drawing below is the same four-node chain; only the gate family changes.
Part (c): the literal AND/OR/NOT circuit. One 2-input OR forms $P$; one inverter forms $\overline{C}$; one 2-input AND forms $u=P\overline{C}$; one inverter forms $\overline{u}$; one 3-input AND forms $v=B\overline{C}D$; one 2-input OR forms $w$; one 3-input AND forms $g=w\cdot E\cdot P$. That is seven gates (2 NOT, 2 OR, 3 AND), with $P$ fanning out to two loads and $\overline{C}$ to two loads.

Question 1(c) — the expression transcribed directly into AND, OR and NOT gates. Note the two fan-out points, $P$ and $\overline{C}$.

Part (d): NAND only. The key economy is that $\overline{u}$ is already a NAND output: $N_2=\overline{P\cdot\overline{C}}=\overline{u}$ needs no extra inverter. Then $N_1=\overline{\overline{A}\cdot\overline{B}}=P$, $N_3=\overline{N_2\cdot N_2}=u$, $N_4=\overline{B\cdot\overline{C}\cdot D}=\overline{v}$, and $N_5=\overline{N_3\cdot N_4}=\overline{u\cdot\overline{v}}=\overline{u}+v=w$. Finally $N_6=\overline{w\cdot E\cdot P}$ and $N_7$ inverts it, giving seven NAND gates.

Question 1(d) — NAND-only realisation, seven gates. $N_2$ produces the complemented term of $g$ for free.

Part (e): NOR only. Here the OR nodes come for free instead. $M_1=\overline{A+B}=\overline{P}$; $M_2=\overline{\overline{P}+C}=P\cdot\overline{C}=u$ (De Morgan on the printed complemented term); $M_3=\overline{M_2+M_2}=\overline{u}$; $M_4=\overline{\overline{B}+C+\overline{D}}=B\overline{C}D=v$; $M_5=\overline{\overline{u}+v}=\overline{w}$; and $M_6=\overline{\overline{w}+\overline{E}+\overline{P}}=w\cdot E\cdot P=g$. That is six NOR gates — one fewer than the NAND version, because the final AND-of-three collapses into a single NOR fed by complemented literals.

Question 1(e) — NOR-only realisation, six gates. $M_6$ absorbs the whole output AND by De Morgan.

Question 1(a) and 1(b) — the two universal-gate primitives the rest of the question is built from.

Question 1 — final results
Part	Result	Gate count
(a) NOT from NAND	$\overline{A\cdot A}=\overline{A}$ (inputs tied together)	1 NAND
(b) OR from NANDs	$\overline{\overline{A}\cdot\overline{B}}=A+B$	3 NAND
(c) AND/OR/NOT	$P\to u\to\overline{u}$, $v$, $w$, $g=wEP$	7 gates (3 AND, 2 OR, 2 NOT)
(d) NAND only	$N_1\dots N_7$ as drawn	7 NAND
(e) NOR only	$M_1\dots M_6$ as drawn	6 NOR

Topic. Functional completeness of NAND and NOR, and bubble-to-bubble conversion of a multi-level network.

Key relations. $\overline{X\cdot X}=\overline{X}$; $\overline{X+X}=\overline{X}$; $\overline{\overline{X}\cdot\overline{Y}}=X+Y$; $\overline{\overline{X}+\overline{Y}}=X\cdot Y$; and the general De Morgan pair $\overline{X_1X_2\cdots}= \overline{X_1}+\overline{X_2}+\cdots$.

Why this works. A NAND is an AND followed by an inverting bubble, and a NOR is an OR followed by a bubble. Converting a multi-level AND/OR network to a single family is therefore purely a matter of pushing bubbles: insert a pair of bubbles on every internal wire (which changes nothing, since $\overline{\overline{X}}=X$), then absorb one bubble into the driving gate and one into the receiving gate. Because the exam supplies both polarities of every literal, the bubbles that reach a primary input cost nothing at all, which is exactly why the NOR version needs only six gates. The instruction “do not simplify” matters: minimising $g$ first would give a smaller but structurally different circuit and would not demonstrate the conversion skill being tested.

Common pitfall. Converting an OR node to NAND by simply relabelling the gate. $\overline{X\cdot Y}\neq X+Y$; the inputs must be complemented first. The second pitfall is forgetting that a complemented sub-expression already sitting in the printed formula, such as $\overline{(A+B)\overline{C}}$, is a free NAND output and does not need an inverter after the AND.

Source. Mano & Ciletti, Digital Design, 5th ed., §2.6–2.8 (Boolean identities, De Morgan, canonical forms) and §3.7 (NAND and NOR implementation, multi-level conversion); Wakerly, Digital Design, 4th ed., §4.2 (bubble-to-bubble logic design).

← Paper overview Next: Question 2 →