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

Question 1 of 6: Boolean minimisation, K-map verification and hazard removal

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

Notes on this paper

Paper format. National Exams, May 2017 — 16-Elec-A4 Digital Systems & Computers. Three hours, closed book, one approved Casio or Sharp calculator. Six questions, each worth 12 points; any five constitute a complete exam. A flip-flop excitation table and a list of Boolean identities are printed on the last page. Every one of the six questions is solved below, because the set is intended as a study resource rather than an exam script.

Reference texts. M. Morris Mano & M. D. Ciletti, Digital Design (6th ed.), ch. 3 (map simplification, prime implicants, hazards), ch. 4–5 (combinational and sequential design), ch. 6 (counters); J. F. Wakerly, Digital Design: Principles and Practices (5th ed.), §4.4 (timing hazards and consensus terms), ch. 7 (sequential-circuit design); C. Hamacher, Z. Vranesic, S. Zaky & N. Manjikian, Computer Organization and Embedded Systems (6th ed.), ch. 3 (memory-mapped I/O, program-controlled and interrupt I/O); F. M. Cady, Software and Hardware Engineering: Motorola M68HC11, ch. 8–9 (parallel I/O and handshaking).

Question 1: Boolean minimisation, K-map verification and hazard removal (12 points)

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. A three-variable switching function written in product-of-sums form, $f = (A+B)(B+C)(\bar A + \bar B + C)$, with A the most significant variable and C the least significant.

Find. A direct gate realisation of the POS form; the minimum two-level sum-of-products obtained algebraically and confirmed on a Karnaugh map; and a decision on whether that minimum SoP contains a static-1 hazard, with an economical hazard-free form if it does.

Approach. Multiply out the three sum terms with the distributive and consensus identities to reach a minimum SoP, plot the on-set on a three-variable map to confirm it, then test every adjacent pair of 1-cells for a term boundary — the pair that crosses one is where the hazard lives, and its consensus term is the cure.

Part (a): synthesize the POS form as written. The expression is a product of three OR terms, so it maps directly onto three OR gates feeding one 3-input AND gate, with inverters producing $\bar A$ and $\bar B$ for the third term: $$f = \underbrace{(A+B)}_{\text{OR}}\cdot\underbrace{(B+C)}_{\text{OR}}\cdot\underbrace{(\bar A+\bar B+C)}_{\text{3-input OR}}$$ This literal realisation costs three OR gates, one AND gate and two inverters (eight literals). It is correct but not minimal, which motivates parts (b)–(c).
Part (b): reduce the first two factors. Expanding $(A+B)(B+C)$ and using absorption $B + BC = B$: $$(A+B)(B+C) = B + AC$$ so that $f = (B + AC)(\bar A + \bar B + C)$.
Multiply out and simplify. Distributing and dropping every term containing $B\bar B$ or $A\bar A$: $$f = \bar A B + BC + AC + AB'C$$ The term $AB'C$ is absorbed by $AC$ (since $AC + AB'C = AC$), leaving $f = \bar A B + AC + BC$. Finally $BC$ is the consensus of $\bar A B$ and $AC$ and is therefore redundant for logic: $$\boxed{f = \bar A B + AC}$$ This minimum SoP costs two AND gates and one OR gate (four literals) — half the literal count of the POS form.
Part (c): confirm on a Karnaugh map. Evaluating the original POS at all eight input combinations puts 1s at exactly $$f = \sum m(2,3,5,7)$$ On the three-variable map (rows A, columns BC in Gray order) these four cells form two pairs: $m(2,3)$ groups as $\bar A B$ and $m(5,7)$ groups as $AC$. The map cover reproduces the algebraic result exactly, verifying part (b).
Part (d): test the minimum SoP for a static-1 hazard. A two-level SoP glitches when a single input change moves the output between two 1-cells held by different product terms. Scanning the adjacent 1-cell pairs, the only crossing pair is $$m3 = 0\,1\,1 \quad\text{and}\quad m7 = 1\,1\,1 \quad\text{(they differ only in } A\text{)}$$ with $m3$ covered by $\bar A B$ alone and $m7$ by $AC$ alone. Holding $B = C = 1$ and switching $A$, the departing gate can fall before the arriving gate rises, so the OR output momentarily drops to 0. The honest answer is therefore yes, a static-1 hazard exists.
Supply the economical hazard-free form. Add the consensus term $BC$, which covers both $m3$ and $m7$ and does not depend on the changing variable A, so it holds the output high throughout the transition: $$\boxed{f_{\text{hazard-free}} = \bar A B + AC + BC}$$ Re-running the adjacency test on this three-term cover returns no hazardous pair. The redundant term costs one extra AND gate and two literals — the minimum price of a glitch-free output.

The two halves of the question dovetail: the consensus term that Boolean minimisation discards as redundant is precisely the term hazard-removal needs. Minimality and glitch-freedom pull in opposite directions, and the examiner is checking that the candidate can hold both ideas at once.

Fig Q1.1 — Karnaugh map of f = Σm(2,3,5,7). The green loop is A′B, the blue loop is AC, and the red consensus loop BC bridges the single hazardous adjacency m3–m7.

Question 1 — final results
Quantity	Result
(a) POS realisation	3 OR gates → 3-input AND, plus inverters for A′, B′
On-set of f	Σm(2, 3, 5, 7)
(b)/(c) minimum SoP	f = A′B + AC (2 terms, 4 literals)
(d) hazard present?	Yes — static-1 hazard between m3 and m7 (B=C=1, A changing)
(d) hazard-free SoP	f = A′B + AC + BC

Topic. Algebraic and map-based two-level minimisation, and static-hazard elimination by the consensus theorem.

Key relations. Absorption $B + BC = B$; distribution and complementarity to clear $X\bar X = 0$; the consensus identity $XY + \bar X Z = XY + \bar X Z + YZ$. A static-1 hazard exists between adjacent 1-cells $m_i, m_j$ iff no single product term of the realised expression contains both.

Why this works. A Gray-coded map turns physical adjacency into logical adjacency, so a rectangle of $2^k$ cells is a product term with $k$ variables eliminated by $X + \bar X = 1$. The algebraic reduction and the map must agree because both compute the same cover of the same on-set. The hazard argument, by contrast, is about timing: in steady state both SoP forms realise f identically, but real AND gates have unequal delays, so during a one-variable change the departing gate can switch off before the arriving one switches on. The consensus term is immune to the changing variable, so it stays high across the changeover and pins the OR output up.

Common pitfall. Answering part (d) by reflexively adding every remaining product term. Only the term bridging a genuinely hazardous adjacency is required; where the minimum cover has no crossing adjacency, the correct and fully-credited answer is that the expression is already hazard-free. Always run the adjacency test rather than inferring the hazard from the mere existence of a redundant term.

Source. Mano & Ciletti, Digital Design 6th ed., §3.3–3.5 (map method) and §4.11 (hazards); Wakerly, Digital Design 5th ed., §4.4 (timing hazards and the consensus theorem).

← Paper overview Next: Question 2 →