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
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 idea behind this question
A $4{:}1$ multiplexer with two variables on its select lines can realise any function of three variables. For each combination of the select variables, look at the two minterms that share it and ask what the function does as the third variable changes: it is $0$, $1$, the variable or its complement. That value goes on the matching data input.
Try a variation
Realise $F(A,B,C) = \sum m(0,3,5,6)$ on the same $4{:}1$ multiplexer, with $A$ as the select MSB.
Show the answer
Answer: $I_0 = \overline{C},\; I_1 = C,\; I_2 = C,\; I_3 = \overline{C}$
Pair the minterms by $AB$: $(0,1)$ gives $\overline{C}$, $(2,3)$ gives $C$, $(4,5)$ gives $C$, $(6,7)$ gives $\overline{C}$.
Other mistakes to avoid
- Listing the minterms in the wrong order when grouping them in pairs.
- Putting a constant on a data input when the function actually follows the third variable.