Realising a 3-variable function on a 4:1 multiplexer
BlinkNBuild practice problem · GATE standard, authored and verified in-house
The Boolean function $F(A,B,C) = \sum m(1,2,4,7)$ is to be implemented using a single 4:1 multiplexer with $A$ and $B$ applied to the select lines ($A$ = MSB of select). What must be applied to the data inputs $I_0, I_1, I_2, I_3$?
Show the step-by-step derivation
Answer
(A) I_0=C, ; I_1= C , ; I_2= C , ; I_3=C
Step-by-step derivation
- Write out the minterms. With $A$ as MSB and $C$ as LSB, the required minterms are $m_1 = \overline{A}\,\overline{B}\,C$, $m_2 = \overline{A}B\overline{C}$, $m_4 = A\overline{B}\,\overline{C}$ and $m_7 = ABC$.
- The select lines $AB$ choose which data input reaches the output, so group the eight possible input combinations into the four select cases and see what $F$ must be in each, as a function of $C$ alone.
- $AB = 00$ (drives $I_0$): the two rows are $m_0$ ($C = 0$, $F = 0$) and $m_1$ ($C = 1$, $F = 1$). $F$ follows $C$, so $I_0 = C$.
- $AB = 01$ (drives $I_1$): rows $m_2$ ($C = 0$, $F = 1$) and $m_3$ ($C = 1$, $F = 0$). $F$ is the complement of $C$, so $I_1 = \overline{C}$.
- $AB = 10$ (drives $I_2$): rows $m_4$ ($C = 0$, $F = 1$) and $m_5$ ($C = 1$, $F = 0$). Again $I_2 = \overline{C}$.
- $AB = 11$ (drives $I_3$): rows $m_6$ ($C = 0$, $F = 0$) and $m_7$ ($C = 1$, $F = 1$). $F$ follows $C$, so $I_3 = C$.
- Collecting: $I_0 = C,\; I_1 = \overline{C},\; I_2 = \overline{C},\; I_3 = C$, which is option (A).
- The insight worth keeping: $\sum m(1,2,4,7)$ is exactly the set of inputs with an odd number of 1s, so $F = A \oplus B \oplus C$. Recognising the parity function lets you write the four data inputs down immediately, because $A \oplus B \oplus C = (A \oplus B) \oplus C$ is $C$ when $A \oplus B = 0$ and $\overline{C}$ when $A \oplus B = 1$.
The trap this question is built around
Getting the select-line ordering backwards. If $B$ were the MSB instead of $A$, $I_1$ and $I_2$ would swap. Here they happen to be equal, so the error is invisible - which is exactly why it survives to a question where they are not.