GATE CSE 2023 | Question: 34

Question

A Boolean digital circuit is composed using two $4$-input multiplexers $\text{(M1 and M2)}$ and one $2$-input multiplexer $\text{(M3)}$ as shown in the figure. $\text{X0-X7}$ are the inputs of the multiplexers $\text{M1 and M2}$ and could be connected to either $0$ or $1.$ The select lines of the multiplexers are connected to Boolean variables $\text{A, B and C}$ as shown.

Which one of the following set of values of $\text{(X0, X1, X2, X3, X4, X5, X6, X7)}$ will realise the Boolean function $\overline{\mathrm{A}}+\overline{\mathrm{A}} \cdot \overline{\mathrm{C}}+\mathrm{A} \cdot \overline{\mathrm{B}} \cdot \mathrm{C}?$ 

• A. $(1,1,0,0,1,1,1,0)$
• B. $(1,1,0,0,1,1,0,1)$
• C. $(1,1,0,1,1,1,0,0)$
• D. $(0,0,1,1,0,1,1,1)$

Answer 1

$f= \overline{A} + \overline{A} \ \overline{C} + A \overline{B} C$

Since, final output is given by a $2 \times 1$ MUX i.e. $M_3$, so we have to write $f$ as $f= \overline{B} (.) + B (.)$

$f=\overline{A} (1+\overline{C}) + A \overline{B}C$

$f= \overline{A} + A \overline{B}C$

$f= \overline{A}(B + \overline{B})(C + \overline{C}) + A \overline{B}C$

$f = \overline{A}BC + \overline{A}B\overline{C} + \overline{A} \ \overline{B}C + \overline{A} \ \overline{B} \ \overline{C} + \overline{B}AC$

$f= \overline{B}(\overline{A}C + \overline{A} \ \overline{C} + AC) + B (\overline{A}C + \overline{A} \ \overline{C})$

Now, our job is completed to write $f$ as $f= \overline{B} (.) + B (.)$

Now, for $(\overline{A}C + \overline{A} \ \overline{C} + AC)$ we have to go upper left side MUX i.e. $M_1$ and we get:

$1)$ $\overline{A}C$ i.e. $\overline{S_1}S_0$ i.e. $X_1=1$

$2)$ $\overline{A} \ \overline{C}$ i.e. $\overline{S_1} \ \overline{S_0}$ i.e. $X_0=1$

$3)$ $AC$ i.e. $S_1S_0$ i.e. $X_3=1$

Now, from left below MUX i.e. $M_2$, we get:

$4)$ $\overline{A} C$ i.e. $\overline{S_1} S_0$ i.e. $X_5=1$

$5)$ $\overline{A} \ \overline{C}$ i.e. $\overline{S_1} \ \overline{S_0}$ i.e. $X_4=1$

Hence, $X_0=X_1=X_3=X_4=X_5=1$ and $X_2=X_6=X_7=0$

So, order is: $\textbf{11011100}$

$\textbf{Therefore, (C)}$

Comments

thanks ankit sir

---

Wow this solution made problem look so easy.

Answer 2

As per arrangement of MUX , choose  BAC ,  B:MSB , C:LSB

	B	A	C
x0	0	0	0	1 → Due to A’ , 1 → Due to A’C’
x1	0	0	1	1 → Due to A’
x2	0	1	0	0
x3	0	1	1	1 → Due to AB’C
x4	1	0	0	1 → Due to A’ , 1 → Due to A’C’
x5	1	0	1	1 → Due to A’
x6	1	1	0	0
x7	1	1	1	0

 

 x0..x7  = 11011100

Comments

If you take B as LSB i.e. ACB then too ans is coming as “C” option. Then why to take B as MSB? Is there any reference on why to take Level 2 MUX Select lines as MSB.

---

Not every time we need reference. It can be proved easily.

Let Output of multiplexer M1 is $Q_1$ and Output of multiplexer M2 is $Q_2$. Then,

$Q_1=\overline{A} \ \overline{C}X_0+\overline{A} \ CX_1+A \ \overline{C} X_2 + A \ C \ X_3$

$Q_2=\overline{A} \ \overline{C}X_4+\overline{A} \ CX_5+A \ \overline{C} X_6 + A \ C \ X_7$

So, $Q=\overline{B}Q_1 +B \ Q_2$

$Q=\overline{B}(\overline{A} \ \overline{C}X_0+\overline{A} \ CX_1+A \ \overline{C} X_2 + A \ C \ X_3) +B \ (\overline{A} \ \overline{C}X_4+\overline{A} \ CX_5+A \ \overline{C} X_6 + A \ C \ X_7)$

$Q=\overline{B} \ \overline{A} \ \overline{C}X_0+\overline{B} \ \overline{A} \ CX_1+\overline{B} \ A \ \overline{C} X_2 + \overline{B} \  A \ C \ X_3 +B \ \overline{A} \ \overline{C}X_4+B \ \overline{A} \ CX_5+ B \ A \ \overline{C} X_6 + B \ A \ C \ X_7$

This function corresponds to a 8:1 multiplexer with select lines as B,A,C (B is MSB) and inputs as X0 to X7.

Answer 3

First of all we can see the resultant circuit is nothing but an 8x1 Mux(with inputs as: X0,X1,X2,X3,X4,X5,X6,X7 that is implemented here using two 4x1 Mux(Level-1) + one 2x1 Mux(Level-2).

Now as the select line of Level-2 Mux is B hence we consider B as MSB and select lines of Level-1 Mux are A(connected to S1) and C (connected to S0) so C is LSB.

so function that circuit realise is F(B,A,C) =$\bar{A}+\bar{A}\bar{C}+\bar{B}AC$ which can be further written as 

F(B,A,C) =$(\bar{A}+\bar{A}\bar{C})+\bar{B}AC$   =   $(\bar{A}+\bar{B}AC)$   (used distributive law here)

now find all minterm expression for it by expanding it, 

F(B,A,C) =$\bar{B}\bar{A}\bar{C}+\bar{B}\bar{A}C+B\bar{A}\bar{C}+B\bar{A}C+\bar{B}AC$

so its minterms are 

F(B,A,C)= $\sum$m(0,1,3,4,5) , now to get these minterms, the inputs X0,X1,X3,X4,X5 must be 1 and remaining inputs i.e X2,X6,X7 must be 0.

hence answer is option C.