GATE 2018 EC Q.47: solution and answer

GATE 2018 · ECQ.47 · 2 marks · NAT

The logic gates shown in the digital circuit below use strong pull-down nMOS transistors for LOW logic level at the outputs. When the pull-downs are off, high-value resistors set the output logic levels to HIGH (i.e. the pull-ups are weak). Note that some nodes are intentionally shorted to implement "wired logic". Such shorted nodes will be HIGH only if the outputs of all the gates whose outputs are shorted are HIGH.

[Figure]

The number of distinct values of $X_{3} X_{2} X_{1} X_{0}$ (out of the 16 possible values) that give $Y = 1$ is ________.

GATE 2018 EC question 47: Inputs X0, X1, X2, X3 on the left; — Figure from the GATE 2018 EC paper. It is part of the question.

Answer and solution

ANSWER

$Y = X_{3}$ , so 8 of the 16 values of $X_{3} X_{2} X_{1} X_{0}$ give $Y = 1$ .

Official answer: 8Source: Official answer key, GATE 2018 EC (IIT Guwahati)

Wired-AND rule. The pull-downs are strong and the pull-ups are weak. So when several gate outputs are shorted together, any one output that is LOW pulls the node LOW, and the node is HIGH only if every tied output is HIGH. Each shorted node therefore carries the AND of the outputs tied to it. (In what follows, $\overline{X}$ means the complement of $X$ .)
Node at the AND gate's lower input. The XOR output is shorted to the output of NOT( $X_{3}$ ), so this node carries $A = (X_{1} \oplus X_{2}) \cdot \overline{X_{3}}$
AND gate output. Its top input is $X_{0}$ itself, taken from the junction before the inverter. Its bottom input is $A$ . So it outputs $X_{0} \cdot A$ .
Node at the OR gate's upper input. The AND output is shorted to the output of NOT( $X_{0}$ ), so this node carries $B = (X_{0} \cdot A) \cdot \overline{X_{0}} = (X_{0} \overline{X_{0}}) \cdot A = 0$ because $X_{0} \overline{X_{0}} = 0$ . You can also see it directly: if $X_{0} = 1$ , NOT( $X_{0}$ ) outputs LOW; if $X_{0} = 0$ , the AND gate outputs LOW. Either way one of the two tied outputs is LOW, and it pulls the node down.
OR gate. Its lower input is $X_{3}$ , taken directly from the junction before the second inverter, so $Y = B + X_{3} = 0 + X_{3} = X_{3}$
Count the input words. $Y = 1$ exactly when $X_{3} = 1$ . $X_{2}$ , $X_{1}$ and $X_{0}$ can each be anything, so $2^{3} = 8$ of the 16 combinations give $Y = 1$ .

KEY IDEA

With strong pull-downs and weak pull-ups, a shorted node is the AND of every output tied to it (wired-AND). The node at the OR gate's upper input ties $X_{0} \cdot (\dots)$ to $\overline{X_{0}}$ , so it is always 0. That leaves $Y = X_{3}$ .

WATCH OUT FOR

Treating the shorted nodes as wired-OR, or ignoring the shorts and reading each wire as a single gate's output. A second slip is to feed $\overline{X_{0}}$ (instead of $X_{0}$ ) into the AND gate, or $\overline{X_{3}}$ (instead of $X_{3}$ ) into the OR gate. Both taps are taken before the inverters.

From the GATE 2018 EC paper. Every question of this paper · Download the full paper · All 22 Boolean logic questions, with notes

GATE 2018 EC Q.47: solution and answer

Answer and solution

More Boolean logic questions