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

Question 1 of 6: Combinational Design from a Word Statement

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

Question 1: Combinational Design from a Word Statement (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 three-bit unsigned input word $ABC$ with $A$ the most significant bit and $C$ the least significant bit, and two output specifications:

Find. The complete truth table, the canonical SoP expression for $E$, the canonical PoS expression for $O$, and the minimum-literal forms of both obtained by algebraic manipulation using only the supplied identities.

Approach. Translate each English clause into a Boolean primitive — "even" is a statement about the least significant bit alone, "equal" is an exclusive-NOR, "sum is odd" is an exclusive-OR — then tabulate all eight input combinations, read the canonical forms directly off the table, and reduce each with the identity list.

1. Translate the specification into primitives. A binary number is even exactly when its least significant bit is zero, so the "even" clause is $\overline{C}$ and does not involve $A$ or $B$ at all. Two bits are equal exactly when their exclusive-OR is zero, so "$A$ and $B$ are equal" is the exclusive-NOR $\overline{A \oplus B} = \overline{A}\,\overline{B} + AB$. The two clauses are joined by OR: $$E = \overline{C} + \overline{A \oplus B}$$ The second output asks whether $B + C$ is odd; a sum of two bits is odd exactly when the bits differ, which is the exclusive-OR $$O = B \oplus C$$
2. (a) Build the truth table. Evaluating both expressions over the eight input patterns, and recording the decimal value $N$ so the "even" clause can be checked by eye:

   $A$	$B$	$C$	$N$	$N$ even?	$A = B$?	$E$	$B+C$	$O$	minterm
   0	0	0	0	yes	yes	1	0	0	$m_0$
   0	0	1	1	no	yes	1	1	1	$m_1$
   0	1	0	2	yes	no	1	1	1	$m_2$
   0	1	1	3	no	no	0	2	0	$m_3$
   1	0	0	4	yes	no	1	0	0	$m_4$
   1	0	1	5	no	no	0	1	1	$m_5$
   1	1	0	6	yes	yes	1	1	1	$m_6$
   1	1	1	7	no	yes	1	2	0	$m_7$

   Only two rows drive $E$ low, namely $m_3$ and $m_5$: these are the odd numbers whose two leading bits differ, so both clauses fail simultaneously.
3. (b) Canonical sum-of-products for $E$. The canonical SoP is the OR of one minterm per row where the function is 1. Reading the $E$ column, $$E = \Sigma m(0,1,2,4,6,7)$$ which written out in literals is $$E = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + AB\overline{C} + ABC$$ Six product terms of three literals each — the canonical form is deliberately redundant, which is why part (d) asks for the reduction.
4. (c) Canonical product-of-sums for $O$. The canonical PoS is the AND of one maxterm per row where the function is 0. From the $O$ column those rows are $m_0, m_3, m_4, m_7$, and each maxterm is formed by complementing the literals of its row: $$O = \Pi M(0,3,4,7)$$ $$O = (A + B + C)(A + \overline{B} + \overline{C})(\overline{A} + B + C)(\overline{A} + \overline{B} + \overline{C})$$ Note that the pattern of zeros is independent of $A$ — rows 0 and 4 agree, as do rows 3 and 7 — which foreshadows the two-variable answer of part (e).
5. (d) Minimise $E$ using the identities. Start from the expression obtained in Step 1 and expand the exclusive-NOR: $$E = \overline{C} + \overline{A}\,\overline{B} + AB$$ To show this is genuinely the reduction of the canonical form, group the canonical minterms and apply the identities in order. Terms $m_0, m_2, m_4, m_6$ all carry $\overline{C}$; by the distributive identity (14) and complementarity (4), $$\overline{A}\,\overline{B}\,\overline{C} + \overline{A}B\overline{C} + A\overline{B}\,\overline{C} + AB\overline{C} = \overline{C}\,(\overline{A}\,\overline{B} + \overline{A}B + A\overline{B} + AB) = \overline{C}\cdot 1 = \overline{C}$$ The two remaining minterms are $m_1 = \overline{A}\,\overline{B}C$ and $m_7 = ABC$. Absorption in the form of identity (22), $\overline{X}Y + X = X + Y$, lets each be merged with the $\overline{C}$ term: $$\overline{C} + \overline{A}\,\overline{B}C = \overline{C} + \overline{A}\,\overline{B}, \qquad \overline{C} + \overline{A}\,\overline{B} + ABC = \overline{C} + \overline{A}\,\overline{B} + AB$$ so that $$\boxed{\,E = \overline{C} + \overline{A}\,\overline{B} + AB\,}$$ Three product terms and five literals, down from six terms and eighteen literals. A quick check against the table confirms it: the expression is 0 only when $C = 1$ and $A \neq B$, which is exactly rows 3 and 5.
6. (e) Minimise $O$ using the identities. Pair the maxterms that differ in one literal. Maxterms $M_0 = (A+B+C)$ and $M_4 = (\overline{A}+B+C)$ differ only in $A$, so by distribution (15) and complementarity, $$(A + B + C)(\overline{A} + B + C) = (B + C) + A\overline{A} = B + C$$ The same step applied to $M_3$ and $M_7$ gives $$(A + \overline{B} + \overline{C})(\overline{A} + \overline{B} + \overline{C}) = \overline{B} + \overline{C}$$ Multiplying the two survivors, $$\boxed{\,O = (B + C)(\overline{B} + \overline{C})\,}$$ which is the standard PoS form of the exclusive-OR $B \oplus C$: at least one of $B, C$ must be 1, and they must not both be 1. Two sum terms and four literals, down from four terms and twelve literals.
7. Realise the circuit. The minimised expressions map directly onto gates: $E$ needs one inverter, two two-input AND gates and one three-input OR gate; $O$ needs a single exclusive-OR gate.
   Minimised realisation of Question 1: E = C' + A'B' + AB and O = B XOR C.