ISRO EC 2023 Q.27: solution and answer

ISRO 2023 · ECQ.27 · 1 mark · MCQ

The inputs to a digital circuit are signals $A$ , $B$ and $C$ . $\overline{A}$ , $\overline{B}$ and $\overline{C}$ are not available. The +5V supply and the ground can be used as logic '1' and '0' inputs respectively. To implement a function $\overline{B} \overline{C} + A \overline{C}$ using only 2:1 multiplexer, minimum number of MUX required is

(A)
2
(B)
3
(C)
4
(D)
5

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Two 2:1 multiplexers are needed, so the answer is option (A), 2.

Official answer: ASource: ISRO's revised and final answer key of 16 February 2024

Factor the function: $F = \overline{B} \overline{C} + A \overline{C} = \overline{C} (A + \overline{B})$ .
A 2:1 MUX with select $S$ and data inputs $I_{0}, I_{1}$ gives $Y = \overline{S} I_{0} + S I_{1}$ . The complement of the select is produced inside the MUX, so no inverter is needed. The constants $1$ (supply) and $0$ (ground) may be used as data inputs.
First MUX: select $= B$ , $I_{0} = 1$ , $I_{1} = A$ . Then $G = \overline{B} \cdot 1 + B A = A + \overline{B}$ .
Second MUX: select $= C$ , $I_{0} = G$ , $I_{1} = 0$ . Then $F = \overline{C} G + C \cdot 0 = \overline{C} (A + \overline{B})$ , which is the required function.
One MUX is not enough. Its inputs can only be $A$ , $B$ , $C$ , $0$ or $1$ , with no complements. The output $S^{'} I_{0} + S I_{1}$ is the sum of two terms that cannot overlap, because one needs $S = 0$ and the other $S = 1$ . Each term is $0$ , a single literal-type function of one of the three variables (covering 2 of the 8 input combinations), or a constant-1 term covering 4. So each term covers an even number of the 8 combinations, and the output is $1$ on an even number of them.
$F = \overline{C} (A + \overline{B})$ is $1$ for $A B C = 000, 100, 110$ , which is 3 combinations, an odd number. So no single MUX can produce it, and the minimum is 2.

KEY IDEA

A 2:1 MUX gives both $S$ and $\overline{S}$ for free, and the constants 0 and 1 can feed its data inputs. So factor the function into nested forms $\overline{S} I_{0} + S I_{1}$ with $S$ a plain input, and use one MUX per nesting level.

WATCH OUT FOR

Assuming that because $\overline{A}, \overline{B}, \overline{C}$ are unavailable, inverters or extra MUXes are needed to make complements, and so choosing 3 or more. Using a MUX with $I_{0} = 1$ and select $B$ gives $\overline{B} + A$ with no inverter.

From the ISRO EC 2023 paper. Every question of this paper · The full paper (PDF, ISRO) · All 6 ISRO Combinational questions, with notes

ISRO EC 2023 Q.27: solution and answer

Answer and solution

More ISRO Combinational questions