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

Question 1 of 6: Truth Table, Canonical Form, Minimisation and Static Hazards

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

Notes on this paper

Paper format. National Exams, May 2014 — 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 given in the page-1 marking scheme (Q1 is 3+3+3+3; Q2 is 6+3+3; Q3 is 6+6; Q4 is 3+3+6; Q5 and Q6 are 4+4+4). A flip-flop excitation table for the RS/JK/T/D types 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, canonical forms and K-maps (Ch. 2–3), combinational MSI decoders and demultiplexers (Ch. 4), synchronous sequential design and flip-flop excitation (Ch. 5), registers and counters (Ch. 6).
J. F. Wakerly, Digital Design: Principles and Practices, 5th ed. — minimisation and static timing hazards (Ch. 3–4), counters and shift registers (Ch. 8).
C. Hamacher, Z. Vranesic, S. Zaky and N. Manjikian, Computer Organization and Embedded Systems, 6th ed. — the four essential subsystems and bus structure (Ch. 1–3), serial interfaces and UART framing (§3.5), the processor register set and addressing modes (Ch. 2).
M. A. Mazidi, R. McKinlay and D. Causey, PIC Microcontroller and Embedded Systems — port-driven multiplexed seven-segment displays and LED current limiting (Ch. 12).

Notation used throughout. A bar and a prime both denote complement: $\overline{A}$ in the mathematics and A′ in the figures, where SVG text cannot carry an overbar. In every K-map the leftmost variable is the most significant bit, so the minterm indices printed in the cells match the question’s own variable ordering.

Question 1: Truth Table, Canonical Form, 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 switching function of $A,B,C,D$ written as a five-term sum of products, with $A$ the most significant variable and $D$ the least. Two of the five terms are three-literal products, one is a four-literal product, and none of them is a minterm on its own, so the expression is in ordinary (non-canonical) SoP form.

Find. The 16-row truth table, the canonical $\Sigma m_i$ list, the minimum two-level SoP realisation, and whether that realisation can glitch on a single-input change — with the smallest hazard-free SoP if it can.

Approach. Expand each product term into the minterms it covers, read the canonical form directly off the resulting truth table, minimise on a four-variable K-map, then test every pair of adjacent 1-cells to see whether both members lie inside a common product term — the algebraic test for a static-1 hazard.

Expand each product term into its minterms. A product of $k$ literals in four variables covers $2^{4-k}$ minterms, obtained by letting the absent variables take both values:$$\overline{A}CD=\{m_3,m_7\},\quad A\overline{B}C=\{m_{10},m_{11}\},\quad ABD=\{m_{13},m_{15}\}$$and, for the remaining two terms, $\overline{A}\,\overline{C}D=\{m_1,m_5\}$ and $\overline{A}\,\overline{B}C\overline{D}=\{m_2\}$. The union of the five sets is what matters: any minterm produced by more than one term is counted once, by the idempotent law $X+X=X$.
Assemble the truth table. Setting the union of the minterms above to 1 and every other row to 0 gives the complete behaviour of $f$:
Truth table (rows where the function is 1 are shaded)
Minterm i A B C D f
0 0 0 0 0 0
1 0 0 0 1 1
2 0 0 1 0 1
3 0 0 1 1 1
4 0 1 0 0 0
5 0 1 0 1 1
6 0 1 1 0 0
7 0 1 1 1 1
8 1 0 0 0 0
9 1 0 0 1 0
10 1 0 1 0 1
11 1 0 1 1 1
12 1 1 0 0 0
13 1 1 0 1 1
14 1 1 1 0 0
15 1 1 1 1 1
Read the canonical sum-of-products (part b). The canonical form lists exactly the shaded rows:$$\boxed{f(A,B,C,D)=\Sigma m(1,2,3,5,7,10,11,13,15)}$$There are nine minterms, so the canonical two-level circuit would need nine four-input AND gates feeding one nine-input OR gate — the motivation for minimising.

Truth table (rows where the function is 1 are shaded)
Minterm i	A	B	C	D	f
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

Plotting those nine minterms on a four-variable K-map with $AB$ on the rows and $CD$ on the columns exposes the prime implicants. Every group must be a rectangle whose side lengths are powers of two, and the map wraps around in both directions.

K-map of f with the three prime implicants that form the minimum cover. Cell labels are minterm indices; the shaded loops are A′D (blue), B′C (green) and BD (red).

Extract the minimum cover (part c). The complete set of prime implicants is $\overline{A}D,\;\overline{B}C,\;BD,\;CD$. The first three are essential — $m_1$ is covered only by $\overline{A}D$, $m_2$ and $m_{10}$ only by $\overline{B}C$, and $m_{13}$ only by $BD$ — and together they already cover all nine 1-cells, so $CD$ is redundant for the logic:$$\boxed{f=\overline{A}D+\overline{B}C+BD}$$Three two-input AND gates and one three-input OR gate replace the ten gates of the canonical form.
Test the minimised expression for static hazards (part d). A two-level SoP circuit exhibits a static-1 hazard when two adjacent 1-cells — cells differing in exactly one variable — are not both contained in a single product term of the realisation. Sweeping all adjacent 1-pairs of the map, every pair lies inside one loop except one: $m_{11}=1011$ and $m_{15}=1111$. Here $m_{11}$ is held up only by $\overline{B}C$ and $m_{15}$ only by $BD$.
Show why that pair glitches. Fix $A=1,\,C=1,\,D=1$ and let $B$ change. Before the change $\overline{B}C=1$ holds the output high; after it $BD=1$ does. Because the $B$ input reaches the $BD$ gate directly but reaches the $\overline{B}C$ gate through an inverter, the falling term switches off before the rising term switches on, and the OR output dips to 0 for roughly one inverter delay $t_{pd}$. The minimised expression of step 4 is therefore not hazard-free.

The cure is the classical consensus (redundant-implicant) fix: add the prime implicant that covers both offending cells and does not depend on the changing variable. That implicant is exactly the one the minimisation discarded.

The same map with the consensus term CD (purple) added. Every pair of adjacent 1-cells now shares at least one loop, so no single-input change can glitch the output.

State the smallest hazard-free SoP (part d). Adding $CD$ keeps the output high throughout the $B$ transition, since $CD$ is independent of $B$ and equals 1 at both $m_{11}$ and $m_{15}$:$$\boxed{f_{\text{hf}}=\overline{A}D+\overline{B}C+BD+CD}$$Re-running the adjacency test on this four-term cover returns no unshared pair, and no smaller SoP can do it: any hazard-free cover must contain a product covering the $(m_{11},m_{15})$ pair, and $CD$ is the only prime implicant that does. The cost is one extra two-input AND gate and one more OR input.

Question 1 — final results
Part	Quantity	Result
(a)	Truth table	16 rows; $f=1$ on nine of them (shaded above)
(b)	Canonical SoP	$f=\Sigma m(1,2,3,5,7,10,11,13,15)$
(c)	Minimum SoP	$f=\overline{A}D+\overline{B}C+BD$ (3 terms, 6 literals)
(d)	Hazard present?	Yes — static-1 hazard between $m_{11}$ and $m_{15}$ ($A=C=D=1$, $B$ changing)
(d)	Smallest hazard-free SoP	$f=\overline{A}D+\overline{B}C+BD+CD$

Topic. Canonical and minimal two-level forms, and static hazards in combinational logic.

Key relations. Minterm expansion of a $k$-literal product (covers $2^{n-k}$ minterms); the K-map adjacency rule (physically adjacent cells differ in one variable); the consensus theorem $AB+\overline{A}C+BC=AB+\overline{A}C$, whose discarded term $BC$ is precisely the hazard-cover term.

Why this works. Minimisation removes every product term that is logically redundant, but logic redundancy and timing redundancy are different things. Steady-state truth is preserved by dropping the consensus term, yet during the transition the two remaining terms exchange responsibility for holding the output high, and unequal path delays make that handover non-overlapping. Re-inserting the consensus term gives a third gate that is high both before and after the change and therefore bridges the handover. The same argument dualises exactly: a product-of-sums realisation suffers static-0 hazards, cured by a redundant sum term found the same way on the 0-cells.

Common pitfall. Two mistakes recur. The first is testing for hazards on the K-map picture rather than on the realisation: a pair of 1-cells that merely look adjacent is harmless if some single loop contains both. The second is assuming a hazard-free SoP is also free of dynamic and function hazards — the consensus fix only guarantees behaviour when exactly one input changes at a time.

Source. Mano & Ciletti, Digital Design 6th ed., §3.2–3.5 (K-maps, prime implicants) and Wakerly, Digital Design: Principles and Practices 5th ed., §3.4 (timing hazards and the consensus cure).

← Paper overview Next: Question 2 →

Minterm i	A	B	C	D	f
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

Part	Quantity	Result
(a)	Truth table	16 rows; \(f=1\) on nine of them (shaded above)
(b)	Canonical SoP	\(f=\Sigma m(1,2,3,5,7,10,11,13,15)\)
(c)	Minimum SoP	\(f=\overline{A}D+\overline{B}C+BD\) (3 terms, 6 literals)
(d)	Hazard present?	Yes — static-1 hazard between \(m_{11}\) and \(m_{15}\) (\(A=C=D=1\), \(B\) changing)
(d)	Smallest hazard-free SoP	\(f=\overline{A}D+\overline{B}C+BD+CD\)

Minterm i	A	B	C	D	f
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1

Minterm i	A	B	C	D	f
0	0	0	0	0	0
1	0	0	0	1	1
2	0	0	1	0	1
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	1
6	0	1	1	0	0
7	0	1	1	1	1
8	1	0	0	0	0
9	1	0	0	1	0
10	1	0	1	0	1
11	1	0	1	1	1
12	1	1	0	0	0
13	1	1	0	1	1
14	1	1	1	0	0
15	1	1	1	1	1