Exercises — Multiplexers (2 - 1, 4 - 1, n - 1)

Selects for 32 inputs: we need the smallest $n$ with $2^n\ge 32$. Since $2^5=32$, $n=\lceil {\log }_{2}32\rceil =5$. Inputs for 3 selects: $n$ bits address $2^n$ rows, so $2^3=8$ data inputs. Answers: $5$ select lines; $8$ data inputs.

Read the bits as a binary number, high bit first: $110_2=1\cdot 4+1\cdot 2+0\cdot 1=6$. In spotlight terms: the only minterm that lights is $m_6=S_2{S}_1{\bar{S}}_0$, so its lamp forwards $I_6$. So the output is $I_6$.

$6$ is not a power of two. The address fact forces $n=\lceil {\log }_{2}6\rceil =3$ (since $2^2=4<6\le 8=2^3$). A 3-select MUX physically has $2^3=8$ input slots, so you buy an 8:1 MUX and use only $6$ of them. What happens to the extra minterms $m_6,m_7$? They still exist in $Y={\sum }_{k=0}^7{m}_k{I}_k$, but you either (a) tie the unused inputs $I_6,I_7$ to a safe constant ($0$) so those minterms contribute nothing, or (b) guarantee by design that the select combinations $110$ and $111$ never occur. Never leave them floating — a floating input can drift to an unknown level and, when its minterm lights, garbage reaches $Y$.

$Y={\bar{S}}_1{\bar{S}}_0{I}_0+{\bar{S}}_1{S}_0{I}_1+S_1{\bar{S}}_0{I}_2+S_1{S}_0{I}_3$ With $S_1=1,S_0=0$: only the minterm $S_1{\bar{S}}_0$ is $1$ (it needs $S_1=1$ and $S_0=0$ ✓). All other minterms contain a factor that is $0$ — exactly the "one lamp lit" picture from the spotlight figure, here the $I_2$ lamp. So $Y=I_2=1$.

Why the truth-table method is guaranteed correct (not a recipe — a proof). Put the variables on the selects, so the address $S_2{S}_1{S}_0$ is the assignment $ABC$. The anchor formula then reads $Y={\sum }_k{m}_k{I}_k$, and for any input $ABC=k$ only $m_k=1$, giving $Y=I_k$. So if we simply set each $I_k$ equal to the value $F$ should have at row $k$, then $Y=I_k=F(\text{row }k)$ for every row — the MUX reproduces $F$ line by line. That is why "read $I_k$ off the truth table" cannot fail: it is the spotlight collapsing $\sum m_k{I}_k$ to the one row you are testing.

Data inputs: $I_0{I}_1\dots I_7=0,0,0,1,1,0,1,1$. Every input is a constant $0$ or $1$ — the MUX is a straight lookup table.

The 2:1 equation is $Y=\bar{A}{I}_0+A{I}_1$. Substitute the wiring: $Y=\bar{A}\cdot B+A\cdot \bar{B}=A\oplus B.$ It is XOR. Check corners: $(A,B)=(0,0)\to 0$, $(0,1)\to B=1$, $(1,0)\to \bar{B}=1$, $(1,1)\to \bar{B}=0$. This is exactly the Shannon-expansion trick from the parent note read backwards.

Follow the trace figure below (each hop is a coloured arrow). Split the address: $S_2=1$ (pick the group), $S_1{S}_0=01$ (pick within a group, $01_2=1$).

• M0 (low group) lights its index-1 lamp and outputs $I_1=7$ — the red arrow in the figure.
• M1 (high group) lights its index-1 lamp and outputs $I_5=1$ — the green arrow.
• The 2:1 selector has $S_2=1$, so its yellow "S2=1 → pick M1" gate forwards M1's green wire to $Y$. Answer: $Y=I_5=1$. Sanity check the direct way: $101_2=5$, and indeed $I_5=1$. ✅

$\Sigma m(1,2,4,7)$ means $F=1$ for rows $ABC=001,010,100,111$. Group rows by $AB$ (that's the address), then read off what $F$ does as $C$ varies:

Why the residue trick is correct. With only $AB$ on the selects, the anchor formula gives $Y={\sum }_{k=0}^3{m}_k{I}_k$ where $m_k$ is now a minterm of $A,B$. For a fixed $AB$, exactly one $m_k=1$, so $Y=I_k$ — but here $I_k$ is allowed to be a wire carrying $C$ rather than a constant. So $Y$ equals whatever function of $C$ we placed in that slot. We just need each slot's function of $C$ to match the two truth-table rows it covers: $0\to 1$ pattern is "$C$", $1\to 0$ is "$\bar{C}$", constant halves are $0$ or $1$. Answer: $I_0=C,I_1=\bar{C},I_2=\bar{C},I_3=C$. (This is $A\oplus B\oplus C$, as expected for 3-input odd parity.)

A 16:1 needs ${\log }_{2}16=4$ select lines $S_3{S}_2{S}_1{S}_0$. Split the address into two halves of two bits:

• Lower level: four 4:1 MUXes, each holding a group of four inputs ($I_0..I_3$, $I_4..I_7$, $I_8..I_{11}$, $I_{12}..I_{15}$), all driven by $S_1{S}_0$ (chooses within each group).
• Upper level: one 4:1 MUX taking the four lower outputs, driven by $S_3{S}_2$ (chooses which group).

Total: $4+1=5$ four-to-one MUXes. Why it works: $S_3{S}_2$ names the group of four, $S_1{S}_0$ names the member — together they name any of $16$ inputs, matching $S_3{S}_2{S}_1{S}_0$.

The four coefficients of the inputs are the four minterms of two variables: $m_0={\bar{S}}_1{\bar{S}}_0,m_1={\bar{S}}_1{S}_0,m_2=S_1{\bar{S}}_0,m_3=S_1{S}_0.$ Claim 1 (exhaustive): their sum is $1$ for every input. $m_0+m_1={\bar{S}}_1({\bar{S}}_0+S_0)={\bar{S}}_1$; $m_2+m_3=S_1({\bar{S}}_0+S_0)=S_1$; total ${\bar{S}}_1+S_1=1$. So some minterm is always on — some lamp always lights. Claim 2 (exclusive): any two differ in at least one literal (e.g. $m_1{m}_2={\bar{S}}_1{S}_0\cdot S_1{\bar{S}}_0$ contains $S_1{\bar{S}}_1=0$). So at most one minterm is on. Together: for each select value exactly one $m_k=1$, the rest are $0$. Hence $Y=1\cdot I_k+0\cdot (\text{others})=I_k$. No leakage. ∎

Let chip L hold $I_0..I_3$ (address $S_1{S}_0$) and chip H hold $I_4..I_7$ (address $S_1{S}_0$). Use $S_2$ as the group bit and drive enables: $E_L={\bar{S}}_2,E_H=S_2.$

How is "tying two outputs together" even allowed? Two ordinary (push-pull) logic outputs must never be wired together — if one drives $1$ and the other $0$ they short the supply to ground and fight (bus contention). Real MUX chips avoid this in one of two ways, and both work here:

• Tri-state outputs: when a chip is disabled its output goes to high-Z (a third state that is neither $0$ nor $1$ — electrically disconnected, like an open switch). A disabled chip therefore contributes nothing to the bus; only the enabled chip drives it.
• Wired-OR (open-drain): each chip can only pull the bus low (or release it, with a pull-up resistor holding it high). Releases never fight, so the shared node is the OR of the active drivers.

Either way, contention is impossible iff at most one chip is ever enabled at a time. Check: $E_L{E}_H={\bar{S}}_2{S}_2=0(\text{never both on}),E_L+E_H={\bar{S}}_2+S_2=1(\text{never both off, so }Y\text{ is never floating}).$ With the tri-state picture, the bus therefore equals whichever chip is enabled: $Y={\bar{S}}_2\left({\sum }_{k=0}^3{m}_k{I}_k\right)+S_2\left({\sum }_{k=0}^3{m}_k{I}_{k+4}\right).$ When $S_2=0$ you get $\sum m_k{I}_k$ (inputs $I_0..I_3$); when $S_2=1$ you get $\sum m_k{I}_{k+4}$ (inputs $I_4..I_7$). That is precisely an 8:1 MUX with address $S_2{S}_1{S}_0$, built with no extra gate — the enables did the final selection. ∎

Selects for 32:1? ::: $5$ Input chosen by $110$? ::: $I_6$ MUX for 6 sources — which chip and dead inputs? ::: 8:1 (3 selects); tie $I_6,I_7$ to $0$ $F=A\bar{C}+BC$ on 8:1 — value of $I_3$? ::: $1$ XOR wiring $I_0=B,I_1=\bar{B}$ on 2:1 gives which function? ::: $A\oplus B$ 4:1 MUXes needed for a 16:1? ::: $5$ Enable equations for the two-chip 8:1? ::: $E_L={\bar{S}}_2,E_H=S_2$ What state must a disabled tri-state output take to share a bus? ::: high-Z