22-Elec-A4 Digital Systems and Computers · December 2013

Question 1 of 6: K-map Minimisation and Static Hazards

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

Notes on this paper

Paper format. National Exams, December 2013 — 07-Elec-A4 Digital Systems & Computers. Three hours, closed book (one approved Casio or Sharp calculator). Six questions are printed; any five constitute a complete exam and every question is worth 12 marks, with the per-part split printed in the marking scheme on page 1 (Q1 and Q5 are 3+3+3+3; Q2 is 4+4+4; Q3 and Q6 are 6+6; Q4 is 8+2+2). An excitation table for the RS/JK/T/D flip-flops and a table of 22 basic Boolean identities are supplied on the last page. All six questions are solved below, because this set is a study resource rather than a timed sitting.

Reference texts.

M. M. Mano and M. D. Ciletti, Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog, 6th ed. — Boolean algebra and K-maps (Ch. 2–3), combinational MSI design with multiplexers and decoders (Ch. 4), synchronous sequential logic and flip-flop excitation (Ch. 5), registers and counters (Ch. 6), memory and programmable logic (Ch. 7).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — canonical forms, minimisation and timing hazards (Ch. 3–4), PLD architectures (Ch. 5), counters (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — bus structure and I/O (Ch. 3), polling versus interrupts (§3.2), serial interfaces (§3.5), memory system organisation and chip-select decoding (Ch. 8).

Notation used throughout. A prime and an overbar both denote complement: $\overline{A}$ in the mathematics, A′ in the figures, where SVG text cannot carry an overbar. The variable order in every K-map is the order printed in the question, with the leftmost variable as the most significant bit, so minterm and maxterm indices match the question's numbering exactly.

Question 1: K-map Minimisation and Static Hazards (12 marks)

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 four-variable function specified by its maxterm list, $f(A,B,C,D)=\prod M_i(0,2,6,7,8,10,14,15)$, with $A$ the most significant variable. A maxterm list names the input combinations at which $f=0$; the eight remaining combinations are therefore the minterms at which $f=1$:

$$f = \sum m_i(1,3,4,5,9,11,12,13)$$

Find. The minimum PoS and minimum SoP forms, a justified static-hazard analysis of each, and the smallest hazard-free version of each where a hazard exists.

Approach. Plot the function once on a four-variable K-map, loop the zeros to read the PoS and the ones to read the SoP, then test each two-level form for static hazards by looking for adjacent cells of the same value that no single loop covers, and close each such gap with the corresponding consensus term.

(a) Minimum product-of-sums (3 marks)

Figure 1.1 — the K-map of $f$. Looping the ZEROS into the two largest groups gives the minimum PoS directly; a group of four zeros yields a two-literal sum term.

Plot the eight zeros and group them. The zeros fall into exactly two groups of four. The corner group $\{0,2,8,10\}$ has $B=0$ and $D=0$ throughout while $A$ and $C$ both change; the block $\{6,7,14,15\}$ has $B=1$ and $C=1$ throughout while $A$ and $D$ both change.
Convert each zero-group to a sum term. In PoS a variable that is constant at 0 over the group enters uncomplemented and a variable constant at 1 enters complemented, because the sum term must evaluate to zero on exactly those cells: $$\{0,2,8,10\}:\ B=0,\ D=0 \ \Longrightarrow\ (B+D), \qquad \{6,7,14,15\}:\ B=1,\ C=1 \ \Longrightarrow\ (\overline{B}+\overline{C})$$
Assemble and confirm the cover. Two groups of four cover all eight zeros with no zero left over and no group removable, so this is the minimum PoS: $$\boxed{\,f = (B+D)\,(\overline{B}+\overline{C})\,}$$

Evaluating this expression on all sixteen input combinations reproduces the given maxterm list exactly, which is the check worth doing before any hazard analysis: a hazard-free version of the wrong function earns nothing.

(b) Static-hazard analysis of the PoS form (3 marks)

A two-level PoS network can exhibit a static-0 hazard: the output should stay at 0 across a single-variable change, but momentarily glitches to 1. This happens when the two zero-cells at the ends of that change are covered by different sum terms, because the gate leaving its zero-covering region and the gate entering it switch at slightly different times, and for an instant neither holds the output down.

Search for adjacent zero-cells that share no loop. Comparing every pair of zeros that differ in exactly one variable against the two loops of part (a) leaves two uncovered transitions: $$m_2 = 0010 \leftrightarrow m_6 = 0110 \quad\text{and}\quad m_{10} = 1010 \leftrightarrow m_{14} = 1110$$ Both are changes in $B$ alone, taken with $C=1$ and $D=0$. Cell 2 lies only in $(B+D)$ and cell 6 only in $(\overline{B}+\overline{C})$; likewise for 10 and 14. The minimised expression is therefore not hazard-free.
Identify the consensus sum term. The four cells 2, 6, 10 and 14 share $C=1,\ D=0$, so the implicate that covers both hazardous transitions in one loop is $$C=1,\ D=0 \ \Longrightarrow\ (\overline{C}+D)$$ This is the consensus of $(B+D)$ and $(\overline{B}+\overline{C})$ with respect to $B$, which is exactly the term Boolean identity 18 on the supplied identity sheet declares redundant in value — redundant logically, essential for timing.
Write the hazard-free PoS. Adding the redundant loop leaves the function unchanged but guarantees that some sum term holds the output at 0 throughout each single-variable change: $$\boxed{\,f_{\text{hf}} = (B+D)\,(\overline{B}+\overline{C})\,(\overline{C}+D)\,}$$ Re-running the adjacency search with the third loop present returns no uncovered zero-pair, so three sum terms suffice and no smaller hazard-free PoS exists.

Figure 1.2 — the consensus loop $(\overline{C}+D)$ bridges the 2–6 and 10–14 boundaries, so every single-variable change between two zeros now stays inside one loop.

(c) Minimum sum-of-products (3 marks)

Figure 1.3 — the same map, now looped on the ONES. Two groups of four again suffice.

Group the ones. The eight minterms form two groups of four: $\{1,3,9,11\}$ holds $B=0,\ D=1$ with $A$ and $C$ free, and $\{4,5,12,13\}$ holds $B=1,\ C=0$ with $A$ and $D$ free.
Convert each one-group to a product term. Here the convention reverses: a variable constant at 1 enters uncomplemented and one constant at 0 enters complemented, giving $\overline{B}D$ and $B\overline{C}$. Both groups are prime and both are essential (minterm 1 lies in no other prime implicant, and neither does minterm 4), so $$\boxed{\,f = \overline{B}D + B\overline{C}\,}$$

The two forms are of course the same function; the PoS of part (a) is simply the complement of the minimum SoP of $\overline{f} = \overline{B}\,\overline{D} + BC$, de Morganised.

(d) Static-hazard analysis of the SoP form (3 marks)

The dual failure mode applies to a two-level SoP network: a static-1 hazard, where the output should hold at 1 across a single-variable change but momentarily dips to 0 because the AND gate that was holding it high releases before the incoming one asserts.

Search for adjacent one-cells that share no product term. Two transitions are uncovered: $$m_1 = 0001 \leftrightarrow m_5 = 0101 \quad\text{and}\quad m_9 = 1001 \leftrightarrow m_{13} = 1101$$ Both are changes in $B$ alone with $C=0$ and $D=1$. Cells 1 and 9 belong only to $\overline{B}D$; cells 5 and 13 belong only to $B\overline{C}$. The minimised SoP is therefore not hazard-free either.
Add the consensus product. Cells 1, 5, 9 and 13 share $C=0,\ D=1$, so the covering implicant is $\overline{C}D$ — again the consensus term of the two product terms with respect to $B$: $$\boxed{\,f_{\text{hf}} = \overline{B}D + B\overline{C} + \overline{C}D\,}$$ With the third product present, every pair of adjacent ones lies inside a common loop, so this is the smallest hazard-free SoP.

Figure 1.4 — the consensus product $\overline{C}D$ bridges 1–5 and 9–13. Note the pleasing symmetry with Figure 1.2: hazard removal is a self-dual operation.

Part	Result	Terms
(a) minimum PoS	$f = (B+D)(\overline{B}+\overline{C})$	2
(b) static-0 hazards	present, on $B$ at cells 2–6 and 10–14	—
(b) hazard-free PoS	$f = (B+D)(\overline{B}+\overline{C})(\overline{C}+D)$	3
(c) minimum SoP	$f = \overline{B}D + B\overline{C}$	2
(d) static-1 hazards	present, on $B$ at cells 1–5 and 9–13	—
(d) hazard-free SoP	$f = \overline{B}D + B\overline{C} + \overline{C}D$	3

Topic. Two-level minimisation and the removal of static timing hazards by consensus terms.

Key relations. Consensus identity $AB + \overline{A}C + BC = AB + \overline{A}C$ (identity 18 on the exam's own sheet) and its dual $(A+B)(\overline{A}+C)(B+C) = (A+B)(\overline{A}+C)$; a two-level SoP is free of static-1 hazards iff every pair of adjacent one-cells is covered by a common product term; a two-level PoS is free of static-0 hazards iff every pair of adjacent zero-cells is covered by a common sum term.

Why this works. In a two-level network the only way the output can glitch on a single-input change is if responsibility for holding the output constant is handed from one first-level gate to another. If some single gate covers both endpoints of the change, that gate never switches during the transition and the output is held continuously. The consensus term is precisely the largest implicant (or implicate) spanning the boundary between two loops, so adding it closes the handover gap. It is logically redundant — which is exactly why a minimiser removes it — so a hazard-free design is always larger than the minimum one. Note that this construction removes only static hazards under a single-variable change; simultaneous multi-variable changes can still produce function hazards, which no amount of added redundancy can eliminate.

Common pitfall. Students often check for hazards by looking at the algebra rather than the map, and miss that both maps here have two hazardous transitions, not one; a single consensus loop happens to cover both only because the two pairs differ solely in $A$. The other frequent error is adding the consensus term to the PoS in product form (or vice versa) — a static-0 hazard is fixed by a redundant sum term, a static-1 hazard by a redundant product term.

Source. Wakerly, Digital Design: Principles and Practices, 5th ed., §3.4 (combinational-circuit hazards) and §4.3 (K-map minimisation); Mano & Ciletti, Digital Design, 6th ed., §3.5–3.6.

← Paper overview Next: Question 2 →

Part	Result	Terms
(a) minimum PoS	\(f = (B+D)(\overline{B}+\overline{C})\)	2
(b) static-0 hazards	present, on \(B\) at cells 2–6 and 10–14	—
(b) hazard-free PoS	\(f = (B+D)(\overline{B}+\overline{C})(\overline{C}+D)\)	3
(c) minimum SoP	\(f = \overline{B}D + B\overline{C}\)	2
(d) static-1 hazards	present, on \(B\) at cells 1–5 and 9–13	—
(d) hazard-free SoP	\(f = \overline{B}D + B\overline{C} + \overline{C}D\)	3