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

Question 1 of 6: Map simplification, prime implicants and hazards

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

Question 1: Map simplification, prime implicants and hazards (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 four-variable switching function specified canonically by its on-set, with A the most significant variable and D the least significant, so that the minterm index is $m = 8A + 4B + 2C + D$.

Find. The truth table, one non-prime implicant, one non-essential prime implicant, the complete set of essential prime implicants, the minimum two-level SoP expression, and whether that expression is free of static hazards — supplying a hazard-free form if it is not.

Approach. Plot the nine minterms on a four-variable map, enumerate every maximal group (the prime implicants), find which minterms are covered by only one group (those groups are essential), read the minimum cover, then test each adjacent pair of 1-cells to see whether any pair crosses a boundary between two different product terms — such a pair is where a static-1 hazard lives.

1. Build the truth table from the canonical form. A minterm list is a truth table in compressed form: $f = 1$ at exactly the nine listed indices and $0$ at the remaining seven. Writing the index in binary as ABCD gives the eight-row halves shown below.

   Truth table for f(A,B,C,D)

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

   A useful structural check before going further: the entire half A = 0 is a 1 except for m3, and the half A = 1 contributes only m8 and m10, so most of the covering work will be done by terms containing A′.
2. Enumerate the prime implicants. A prime implicant is a group of $2^k$ adjacent 1-cells that cannot be enlarged. Sweeping the map for maximal groups yields exactly four, all of them quads: $$A'C' = m(0,1,4,5) \qquad A'B = m(4,5,6,7)$$ $$A'D' = m(0,2,4,6) \qquad B'D' = m(0,2,8,10)$$ The last one is the wrap-around group formed by the four corner-adjacent cells in the D = 0, B = 0 region — on the map it appears as two separate rectangles, but the leftmost and rightmost columns are neighbours, so it is a single quad. No octet exists, because no eight 1-cells are mutually adjacent (m3 is missing from the A = 0 half, and the A = 1 half has only two 1-cells).
3. Part (b)(i): an implicant that is not prime. Any group contained inside a larger group qualifies. Take the pair $$\boxed{A'BC' = m(4,5)}$$ It is an implicant, because both m4 and m5 are 1-cells. It is not prime, because it sits strictly inside both A′B and A′C′ and can therefore be enlarged. The single cell A′B′C′D′ = m(0) would answer the part equally well.
4. Part (b)(ii): a prime implicant that is not essential. Test each quad by asking whether it owns any minterm exclusively. A′D′ covers m(0,2,4,6), and every one of those four cells is also covered by another prime implicant — m0 by A′C′ and by B′D′, m2 by B′D′, m4 by both A′C′ and A′B, m6 by A′B. It therefore owns nothing: $$\boxed{A'D' = m(0,2,4,6) \text{ is prime but not essential}}$$ It is the only non-essential prime implicant of this function.
5. Part (b)(iii): the essential prime implicants. A prime implicant is essential when at least one minterm is covered by it alone. Scanning the map for such distinguished cells:

   Essential prime implicants and the minterms that force them

   Prime implicant	Minterms covered	Covered by nothing else
   A′C′	m(0, 1, 4, 5)	m1
   A′B	m(4, 5, 6, 7)	m7
   B′D′	m(0, 2, 8, 10)	m8 and m10

   so the essential set is $$\boxed{\{\,A'C',\; A'B,\; B'D'\,\}}$$ Cell m1 is a 1 only in the column CD = 01 of the row AB = 00, and the only quad reaching it is A′C′; likewise m7 belongs to A′B alone, and the two cells in the A = 1 half belong to B′D′ alone.
6. Part (c): the minimum sum of products. Because the three essential prime implicants between them already cover the union $m(0,1,4,5) \cup m(4,5,6,7) \cup m(0,2,8,10)$, which is precisely the nine-cell on-set, nothing remains to be covered and the non-essential quad A′D′ is simply not needed: $$\boxed{f = A'C' + A'B + B'D'}$$ This cover is unique — when the essential prime implicants alone are sufficient, no cyclic-cover choice arises. It costs three AND gates and one OR gate, six literals in total, against the sixteen product terms and thirty-six literals of the canonical form.
7. Part (d): test the minimum expression for a static-1 hazard. A two-level SoP circuit glitches when a single input change moves the output between two 1-cells that lie in different product terms: for an instant the departing term has switched off while the arriving term has not yet switched on, and the OR gate momentarily sees all zeros. So the test is mechanical — list every adjacent pair of 1-cells and check whether one product term contains both. All pairs except one are safe, but $$m2 = 0\,0\,1\,0 \quad\text{and}\quad m6 = 0\,1\,1\,0 \quad\text{differ only in } B$$ and m2 lies in B′D′ while m6 lies in A′B, with no single term holding both. Hence the answer to the question as asked is no: with A = 0, C = 1, D = 0 held fixed and B changing from 0 to 1 (or back), the minimised circuit can produce a momentary 0 even though f is 1 both before and after the change.
8. Supply the hazard-free form. The cure is to add a redundant product term that covers both cells of the offending pair, so that this term holds the output high while the other two gates change over. The prime implicant A′D′ is exactly that consensus term — it contains m2 and m6 and, being independent of B, does not change at all during the transition: $$\boxed{f_{\text{hazard-free}} = A'C' + A'B + B'D' + A'D'}$$ Re-running the adjacency test on this four-term cover returns no hazardous pairs, and the added term is logically redundant, so the function realised is unchanged. The price is one extra AND gate and two extra literals; the reward is a glitch-free output, which matters whenever the signal drives an asynchronous input such as a latch enable, a clock, or a flip-flop preset.

It is worth noticing how neatly the two halves of the question fit together: the prime implicant that part (b)(ii) identifies as redundant for minimisation is precisely the term that part (d) needs for hazard elimination. Minimality and robustness pull in opposite directions here, and the examiner is testing whether the candidate understands that the “wasted” quad on the map has a real engineering use.