22-Elec-A4 Digital Systems and Computers · Undated paper
Question 1 of 6: K-map minimisation and hazards (12 pts)
Nivaar worked solution (AI-drafted; not reviewed by a licensed engineer)
Notes on this paper
Paper format. National Exams, 22-Elec-A4 — Digital Systems and Computers. Closed book; non-programmable calculator permitted; 3 hours. Six questions, each worth 12 points; “any five constitute a complete paper,” so all six are solved here as a study resource.
Reference texts. M. M. Mano & M. D. Ciletti, Digital Design, 5th/6th ed. (Pearson) — K-maps, hazards, PLA/PAL, flip-flop excitation and synchronous-counter design (ch. 3–6); J. F. Wakerly, Digital Design: Principles and Practices (static hazards, memory decoding); Motorola/Freescale M68HC11 Reference Manual (address decoding and memory-mapped I/O for Q5). Boolean identities and the flip-flop excitation tables printed on the exam cover sheet are used throughout.
Note on the figures. Where a single wire or junction in the Q4 figure is genuinely ambiguous, the reading used is stated and the alternative is flagged in a check callout, per the exam’s own instruction to “submit a clear statement of any assumptions made.”
Question 1 — K-map minimisation and hazards (12 pts)
Given. A four-variable function specified by its maxterm list $\Pi M(0,3,6,7,8,10,14,15)$ ($A$ the most-significant variable). Equivalently the on-set (where $f=1$) is $\Sigma m(1,2,4,5,9,11,12,13)$.
Find. The minimal PoS and SoP covers and, for each, whether the two-level realisation contains a static hazard (and the redundant term that removes it).
K-map for the PoS cover: the four maxterm groups (0-cells) give the four sum terms.
Approach. Group the 0-cells for the PoS and the 1-cells for the SoP on the same map, then test each cover for adjacent same-valued cells that do not share a common implicant (the signature of a static hazard).
Plot the map. The maxterms $0,3,6,7,8,10,14,15$ are the 0-cells; the remaining eight cells are 1s. The four largest 0-groups are $\{0,8\},\{3,7\},\{8,10\},\{6,7,14,15\}$.
(a) Minimal PoS. Each 0-group is one sum term (De Morgan of the group’s product): $\{0,8\}\!\to\!(B+C+D)$, $\{3,7\}\!\to\!(A+\overline C+\overline D)$, $\{8,10\}\!\to\!(\overline A+B+D)$, $\{6,7,14,15\}\!\to\!(\overline B+\overline C)$:$$\boxed{\,f=(B+C+D)(A+\overline C+\overline D)(\overline A+B+D)(\overline B+\overline C)\,}$$
(b) Hazard test of the PoS. A static-0 hazard exists when two adjacent 0-cells are not both inside one sum term. Cells $m_{10}=1010$ and $m_{14}=1110$ are adjacent (they differ only in $B$) yet no single sum term above covers both, so a static-0 hazard is present. It is removed by adding the redundant consensus sum term covering that pair, $ACD^{\,\prime}\!\to\!(\overline A+\overline C+D)$:$$\boxed{\,f_{\text{HF-PoS}}=(B+C+D)(A+\overline C+\overline D)(\overline A+B+D)(\overline B+\overline C)(\overline A+\overline C+D)\,}$$so the minimal PoS of (a) is not hazard-free.
Hazard-free PoS: the orange consensus loop $(\overline A+\overline C+D)$ bridges the adjacent 0-cells $m_{10},m_{14}$.
K-map for the SoP cover: the four 1-groups give the four product terms; every adjacent 1-pair already lies inside a loop, so this cover is hazard-free.
(c) Minimal SoP. Grouping the 1-cells gives $\{2\}\!\to\!\overline A\,\overline B C\overline D$, $\{9,11\}\!\to\!A\overline B D$, $\{1,5,9,13\}\!\to\!\overline C D$, $\{4,5,12,13\}\!\to\!B\overline C$:$$\boxed{\,f=\overline A\,\overline B\,C\,\overline D+A\,\overline B\,D+\overline C\,D+B\,\overline C\,}$$
(d) Hazard test of the SoP. Checking every pair of adjacent 1-cells, each pair is already contained in one product term of the cover (e.g. $m_1,m_5$ in $\overline C D$; $m_5,m_{13}$ in $B\overline C$; $m_9,m_{11}$ in $A\overline B D$; the lone cell $m_2$ has no same-valued neighbour outside its own term). No adjacent 1-pair straddles two different terms, so the minimal SoP is already hazard-free — no extra term is required.
