Question 2 of 5: Multi-Output Karnaugh-Map Minimization with Shared Logic

Question 2: Multi-Output Karnaugh-Map Minimization with Shared Logic (25 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. $Y(a,b,c,d)=\sum m(0,2,4,6,7,9)+D(10,11)$; $Z(a,b,c,d)=\sum m(2,4,9,10,15)+D(0,13,14)$; every literal ($a,a',b,b',c,c',d,d'$) is available directly; only 2-input AND/OR gates are permitted.

Find. (a) A minimum-cost realization of $Y$ and $Z$ that shares logic between the two outputs; (b) how many 2-input gates that sharing saves versus minimizing $Y$ and $Z$ as two independent circuits.

Approach. Minimize $Y$ and $Z$ independently to their minimal sum-of-products forms (Karnaugh map / Quine–McCluskey, don't-cares used freely), then scan the two term lists for 2-literal sub-products common to terms of both functions and factor each shared sub-product out once, counting 2-input AND/OR gates for both the shared and the fully-separate realizations.

1. Minimize $Y$. Grouping the K-map (minterms 0,2,4,6,7,9 required; 10,11 don't-care) gives the minimal SOP $$Y = a'd' + ab'd + a'bc$$.
2. Minimize $Z$. Grouping the K-map (minterms 2,4,9,10,15 required; 0,13,14 don't-care) gives the minimal SOP $$Z = abd + ac'd + b'cd' + a'c'd'$$ (also verified against its truth table).
3. Cost the two functions as fully SEPARATE circuits (2-input gates only). $Y$'s terms need $1+2+2=5$ AND gates (the 2-literal term $a'd'$ costs 1 gate; each 3-literal term costs 2 cascaded 2-input ANDs) plus $2$ OR gates to sum 3 terms, i.e. 7 gates. $Z$'s four 3-literal terms cost $4\times2=8$ AND gates plus $3$ OR gates to sum 4 terms, i.e. 11 gates. Separate total: $7+11=18$ two-input gates.
4. Look for shared 2-literal sub-products between the two term lists. $Y$'s term $a'd'$ is itself the 2-literal product $P_1=a'\cdot d'$, and $Z$'s term $a'c'd'$ is exactly $P_1\cdot c'$ — so $P_1$ can be built once and reused. Separately, the pair $P_2=a\cdot d$ appears inside three different terms: $Y$'s $ab'd=P_2\cdot b'$, and $Z$'s $abd=P_2\cdot b$ and $ac'd=P_2\cdot c'$. $Y$'s $a'bc$ and $Z$'s $b'cd'$ share no common sub-product with anything else and must still be built from their own 2 AND gates each.
5. Cost the SHARED (combined) circuit. Build $P_1=a'd'$ (1 gate, and this is $Y$'s first term) and $P_2=ad$ (1 gate); tap $P_1\cdot c'$ for $Z$ (1 gate) and $P_2\cdot b'$, $P_2\cdot b$, $P_2\cdot c'$ for $Y$, $Z$, $Z$ respectively (1 gate each, 3 gates); build the two unshared terms $a'bc$ and $b'cd'$ at 2 gates each (4 gates). AND-gate subtotal: $1+1+1+3+4=10$. OR gates: $Y$ still sums 3 terms (2 OR gates), $Z$ still sums 4 terms (3 OR gates), subtotal 5. Combined total: $10+5=15$ two-input gates.
6. Part (b) — compare. Separate design $=18$ gates; shared design $=15$ gates: sharing $P_1=a'd'$ and $P_2=ad$ across both outputs saves $18-15=\boxed{3}$ two-input gates, an $\approx16.7\%$ reduction, with $Y$ and $Z$ computing identically to their independently-minimized forms.