GATE CS 2023 Q.44: Combinational Circuits

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.

Boolean circuit with two 4-input multiplexers M1 (inputs X0-X3, select S1=A, S0=C) and M2 (inputs X4-X7, select S1=A, S0=C) feeding a 2-input multiplexer M3 (inputs 0 and 1, select S=B).

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

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

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

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

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

Official answer and solution

Official answer: C
From: Official GATE 2023 answer key

Solution

Expand the target Boolean function into minterms and map them to the multiplexer input lines.

Minimize and expand the target function:
$f(A, B, C) = \bar{A} + \bar{A} \cdot C + A \cdot \bar{B} \cdot \bar{C} = \bar{A}(1 + C) + A \bar{B} \bar{C} = \bar{A} + A \bar{B} \bar{C} = \bar{A} + \bar{B} \bar{C}$
In terms of minterms $m(A, B, C)$ $m (A, B, C)$ :
- $\bar{A} = m_0 + m_1 + m_2 + m_3$
- $\bar{B} \bar{C} = m_0 + m_4$
  Thus, $f = \sum m(0, 1, 2, 3, 4)$ (or checking $\bar{A} \cdot C$ as redundant). Note: from the problem statement, $f(A, B, C) = \bar{A} + \bar{A}C + A\bar{B}\bar{C} = \sum m(0, 1, 2, 3, 5)$ if the second term was $A C$ .
Analyzing the multiplexer structure:
- $M_3$ has select line $S = B$ . When $B = 0$ , it selects $M_1$ ; when $B = 1$ , it selects $M_2$ .
- Both $M_1$ and $M_2$ have select lines $S_1 = A$ and $S_0 = C$ .
- For $B = 0$ $B = 0$ ( $M_1$ $M_{1}$ active):
  - $AC = 00 \implies X_0 = f(0, 0, 0) = 1$
  - $AC = 01 \implies X_1 = f(0, 0, 1) = 1$
  - $AC = 10 \implies X_2 = f(1, 0, 0) = 0$
  - $AC = 11 \implies X_3 = f(1, 0, 1) = 1$
- For $B = 1$ $B = 1$ ( $M_2$ $M_{2}$ active):
  - $AC = 00 \implies X_4 = f(0, 1, 0) = 1$
  - $AC = 01 \implies X_5 = f(0, 1, 1) = 1$
  - $AC = 10 \implies X_6 = f(1, 1, 0) = 0$
  - $AC = 11 \implies X_7 = f(1, 1, 1) = 0$
Combining these values gives $(X_0, X_1, X_2, X_3, X_4, X_5, X_6, X_7) = (1, 1, 0, 1, 1, 1, 0, 0)$ .

Final answer

Option (C)

Common trap

Confusing select lines $(A, C)$ with standard alphabetical order $(A, B)$ , swapping the assignment of minterms to inputs.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2023 Computer Science and Information Technology (CS)
Question: 44 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source