23-Mechatronics-A3 Digital Logic and Embedded Systems · December 2018
Question 1 of 6: Gate-level realisation of a Boolean function
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper: National Exams, December 2018 — 16-Mex-A3 Digital Systems & Computers. Closed-book, 3-hour paper (approved Casio/Sharp calculator only). Candidates normally answer 5 of 6 questions; full worked solutions to all six are given below, whichever five a candidate chose.
Reference texts: M. M. Mano & M. D. Ciletti, Digital Design (6th ed.) — Boolean algebra and gate-level design (Ch. 2), combinational logic (Ch. 4), synchronous sequential logic, state tables and counters (Ch. 5), programmable logic (PAL/PLA, Ch. 7); C. Hamacher, Z. Vranesic, S. Zaky & N. Manjikian, Computer Organization and Embedded Systems (6th ed.) — CPU/memory/bus architecture, registers, addressing; Motorola/Freescale, M68HC11 Reference Manual — big-endian byte storage, stack push/pull, port-based I/O (the questions below use Motorola-style conventions throughout, as stated on the paper).
Reading the question. Q1’s function $g$ is printed with an overline whose exact grouping is partly ambiguous. This solution adopts the literal reading $g=\big(\overline{(A+B)\cdot\bar C}+B\bar C D\big)\cdot E\cdot(A+B)$, i.e. the complement bar covers the whole term $(A+B)\cdot\bar C$; every gate network below is verified by truth table against this reading. Per the instruction on the paper, none of the three realisations in (c)–(e) apply Boolean simplification to $g$ itself — they translate the expression as written, gate-for-gate.
Question 1: Gate-level realisation of a Boolean function [2+2+2+3+3 = 12]
Given. $g=\big(\overline{(A+B)\cdot\bar C}+B\bar C D\big)\cdot E\cdot(A+B)$, a function of five literals $A,B,C,D,E$. Define the intermediate signals used throughout: $S=A+B$, $X=S\cdot\bar C$, so the printed expression is $g=(\bar X+B\bar CD)\cdot E\cdot S$.
Find. (a) a NOT gate from a single NAND; (b) a two-input OR from NAND gates only; (c)–(e) three literal, un-simplified realisations of $g$ — in AND/OR/NOT, in NAND-only, and in NOR-only gates.
Approach. (a)–(b) apply the standard NAND-as-universal-gate identities; (c) is a direct transcription of $g$ into AND/OR/NOT; (d) and (e) apply De Morgan bubble-pushing level-by-level, choosing which intermediate signal to carry (true or complemented) so that each gate's native NAND/NOR inversion is used productively instead of being cancelled by an extra inverter.
(a) NOT from one NAND. Tie both NAND inputs to the same signal $A$: $Y=\overline{A\cdot A}=\boxed{\bar A}$, since $A\cdot A=A$ (idempotent law).
Fig. 1(a) — NOT gate: a 2-input NAND with its inputs tied together.
(b) OR from NAND only. By De Morgan, $A+B=\overline{\bar A\cdot\bar B}$. Build $\bar A$ and $\bar B$ with tied-input NAND gates (part (a)), then combine them in a third NAND: $$Y=\overline{\bar A\cdot\bar B}=\boxed{A+B}.$$ Three NAND gates total.
Fig. 1(b) — two-input OR built from three NAND gates.
(c) AND/OR/NOT, as written. Compute $S=A+B$ (OR) and $\bar C$ (NOT); AND them for $X=S\bar C$, then NOT for $\bar X$. In parallel form the 3-input AND $Y=B\bar CD$ (reusing $\bar C$). OR $\bar X$ and $Y$ to get $Z=\bar X+Y$. Finally AND $Z$ with $E$ and $S$ (3-input AND) to obtain $g$. Gate count: 2 OR, 3 AND, 2 NOT — 7 gates, exactly mirroring the expression's parenthesisation.
Fig. 1(c) — $g$ realised directly in AND, OR and NOT gates.
(d) NAND only. With literal complements free, $S=A+B=\text{NAND}(\bar A,\bar B)$ (De Morgan gives the true OR directly from a NAND of complemented inputs). Because the outer bar in $g$'s first term already asks for $\bar X$, a single NAND supplies it for free: $\bar X=\text{NAND}(S,\bar C)$ — no extra inverter needed. $Y=B\bar CD$ needs its complement inverted back: $Y'=\text{NAND}(B,\bar C,D)$, then $Y=\text{NAND}(Y',Y')$. $Z=\bar X+Y=\text{NAND}(X,Y')$, where $X=\text{NAND}(\bar X,\bar X)$ recovers the true value. Finally $g'=\text{NAND}(Z,E,S)$ and $g=\text{NAND}(g',g')$. Eight NAND gates total (two 3-input, six 2-input, two used purely as inverters).
(e) NOR only. Dually, $S'=\text{NOR}(A,B)$ gives $\overline{A+B}$ directly. $\text{AND}(a,b)=\text{NOR}(\bar a,\bar b)$, so $X=S\bar C=\text{NOR}(S',C)$ using $S'$ and the free literal $C$. Invert once for $X'=\text{NOR}(X,X)$. The 3-input AND $Y=B\bar CD$ becomes, by the same identity, $Y=\text{NOR}(\bar B,C,\bar D)$ — direct, no inverter, because all three complemented literals are free. $Z'=\text{NOR}(X',Y)$ gives $\overline{Z}$, and the final AND is $g=Z\cdot E\cdot S=\text{NOR}(Z',\bar E,S')$, reusing $Z'$ and $S'$ directly — no final inverter needed. Only six NOR gates total.
Fig. 1(e) — $g$ realised in NOR gates only, literal complements assumed available.
