Combinational circuit — even / equal-MSB detector and odd-sum detector: 22-Elec-A4 Digital Systems and Computers, May 2018, Q1

Question 1: Combinational circuit — even / equal-MSB detector and odd-sum detector (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 input $ABC$ with $A$ the most significant bit and $C$ the least significant. Two outputs are specified verbally: $E=1$ when the number is even (its LSB $C=0$) or when the two MSBs are equal ($A=B$); $O=1$ when the sum of the two least-significant digits $B$ and $C$ is odd (exactly one of $B,C$ is 1).

Find. (a) the complete truth table; (b) $E$ as a canonical SoP; (c) $O$ as a canonical PoS; (d) the minimal SoP for $E$; (e) the minimal PoS for $O$, using only the supplied Boolean identities.

Approach. Translate each verbal condition into an algebraic expression, tabulate all eight input combinations, read the canonical forms directly from the 1-rows (SoP) and 0-rows (PoS), then reduce with the complementary, distributive and De Morgan identities.

Encode the two conditions algebraically. "Even" means $C=0$, i.e. the literal $\overline{C}$. "$A$ and $B$ equal" is the equivalence (XNOR) $A\odot B=AB+\overline{A}\,\overline{B}$. Hence $$E=\overline{C}+AB+\overline{A}\,\overline{B}.$$ "Sum of $B$ and $C$ is odd" is true when exactly one of them is 1, i.e. the exclusive-OR $O=B\oplus C=\overline{B}C+B\overline{C}.$
Tabulate all eight rows (minterm index $m=4A+2B+C$), evaluating the two expressions above.

(a) Truth table — minterm index, inputs, and both outputs
$m$	$A$	$B$	$C$	$E$	$O$
0	0	0	0	1	0
1	0	0	1	1	1
2	0	1	0	1	1
3	0	1	1	0	0
4	1	0	0	1	0
5	1	0	1	0	1
6	1	1	0	1	1
7	1	1	1	1	0

(b) Canonical SoP of $E$. $E=1$ at minterms $m=0,1,2,4,6,7$, so the sum of those minterms is $$E=\textstyle\sum m(0,1,2,4,6,7)=\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.$$
(c) Canonical PoS of $O$. $O=0$ at $m=0,3,4,7$; each 0-row contributes one maxterm (complement every literal that is 1), giving $$O=\textstyle\prod M(0,3,4,7)=(A+B+C)\,(A+\overline{B}+\overline{C})\,(\overline{A}+B+C)\,(\overline{A}+\overline{B}+\overline{C}).$$
(d) Minimal SoP of $E$. It is cleaner to minimize the two 0-cells. $\overline{E}=m_3+m_5=\overline{A}BC+A\overline{B}C=C(\overline{A}B+A\overline{B})=C\,(A\oplus B)$. Complementing with De Morgan and involution, $$E=\overline{C(A\oplus B)}=\overline{C}+\overline{(A\oplus B)}=\overline{C}+AB+\overline{A}\,\overline{B}.$$ This matches the K-map: the two 1-columns $C=0$ form $\overline{C}$, and the equal-MSB cells pair into $AB$ and $\overline{A}\,\overline{B}$. $$\boxed{\,E=\overline{C}+AB+\overline{A}\,\overline{B}\,}$$
(e) Minimal PoS of $O$. Combine the four maxterms in pairs on the absent variable $A$: $(A+B+C)(\overline{A}+B+C)=(B+C)$ and $(A+\overline{B}+\overline{C})(\overline{A}+\overline{B}+\overline{C})=(\overline{B}+\overline{C})$ (identity: $(X+Y)(\overline{X}+Y)=Y$). Hence $$\boxed{\,O=(B+C)(\overline{B}+\overline{C})\,}$$ which multiplies out to $B\overline{C}+\overline{B}C=B\oplus C$, confirming the specification.

K-map of $E$: the two vertical $C=0$ columns give $\overline{C}$; the corner-and-centre equal-MSB cells give $AB$ and $\overline{A}\,\overline{B}$.

K-map of $O=B\oplus C$: the 1-cells form a checkerboard with no adjacent pair, so no product term can merge — the compact form is the two-factor PoS, not a smaller SoP.

Question 1 — results
Item	Result
(a) $E$ 1-minterms	$\sum m(0,1,2,4,6,7)$
(a) $O$ 1-minterms	$\sum m(1,2,5,6)$
(b) $E$ canonical SoP	6 minterms (above)
(c) $O$ canonical PoS	$\prod M(0,3,4,7)$
(d) $E$ minimal SoP	$\overline{C}+AB+\overline{A}\,\overline{B}$
(e) $O$ minimal PoS	$(B+C)(\overline{B}+\overline{C})$

Topic: Two-level Boolean minimization — canonical vs. reduced SoP/PoS.

Key relations: canonical SoP $=\sum$ of 1-minterms, canonical PoS $=\prod$ of 0-maxterms; adjacency-merging identity $XY+X\overline{Y}=X$ (SoP) and its dual $(X+Y)(X+\overline{Y})=X$ (PoS); De Morgan $\overline{X+Y}=\overline{X}\,\overline{Y}$.

Why this works: A minterm is 1 for exactly one input pattern, so OR-ing the minterms where the function is 1 reproduces the function exactly; dually a maxterm is 0 for exactly one pattern, so AND-ing the 0-maxterms does the same. Minimization then merges terms that differ in a single variable, eliminating that variable — algebraically the complementary law, geometrically an adjacency on the K-map. Choosing to minimize whichever polarity has fewer active cells (here the two 0-cells of $E$) is usually the shortest route.

Common pitfall: mixing the maxterm convention — a maxterm complements the literals of the 0-row, the opposite of a minterm. An XOR/XNOR output like $O$ is famously irreducible in one level: its checkerboard map has no mergeable adjacency, so students waste effort chasing a two-term SoP that does not exist.

Source: Mano & Ciletti, Digital Design 6th ed., §2.4–2.7 (Boolean functions, canonical forms) and §3.1–3.3 (map minimization).

Question 1 of 6: Combinational circuit — even / equal-MSB detector and odd-sum detector

Question 1: Combinational circuit — even / equal-MSB detector and odd-sum detector (12 marks)