IAE Academy

GATE 2023 CS Q.44: solution and answer

GATE 2023 · CSQ.44 · 2 marks · MCQ

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

Which one of the following set of values of (X0, X1, X2, X3, X4, X5, X6, X7) will realise the Boolean function ?

GATE 2023 CS question 44: M1 is a 4-input multiplexer with data inputs 0,1,2,3 connected to X0, X1, X2, X3;Tap to open full size
Figure from the GATE 2023 CS paper. It is part of the question.
Figure description

M1 is a 4-input multiplexer with data inputs 0,1,2,3 connected to X0, X1, X2, X3; its select lines S1 and S0 are connected to A and C respectively; its output Q goes to input 0 of the 2-input multiplexer M3. M2 is a 4-input multiplexer with data inputs 0,1,2,3 connected to X4, X5, X6, X7; its select lines S1 and S0 are connected to A and C respectively; its output Q goes to input 1 of M3. M3 has select line S connected to B; its output Q is the circuit output.

  1. (A)

    (1, 1, 0, 0, 1, 1, 1, 0)

  2. (B)

    (1, 1, 0, 0, 1, 1, 0, 1)

  3. (C)

    (1, 1, 0, 1, 1, 1, 0, 0)

  4. (D)

    (0, 0, 1, 1, 0, 1, 1, 1)

Answer and solution

ANSWER

The data inputs are , which is option (C).

Official answer: CSource: Official answer key, GATE 2023 CS (IIT Kanpur)

  1. A 4-to-1 multiplexer with selects outputs the data input numbered . With and , M1 outputs and M2 outputs .

  2. M3 has select : for the output is M1's, and for it is M2's.

  3. Simplify the target: (absorption), so . By the rule , this gives .

  4. Case (M1 selected): , so .

  5. So .

  6. Case (M2 selected): , so .

  7. So .

  8. Together , which is option (C).

KEY IDEA

Treat the 2-input multiplexer as a Shannon expansion on . Each 4-input multiplexer is a truth-table lookup on , so every data input is the value of for one combination.

WATCH OUT FOR

Swapping the select order (, ), which reorders and . Another slip is not simplifying , which hides that reduces to when .

From the GATE 2023 CS paper. Every question of this paper · Download the full paper · All 18 Combinational questions, with notes

More Combinational questions