GATE 2024 EC Q.40: solution and answer

GATE 2024 · ECQ.40 · 2 marks · MCQ

A 4-bit priority encoder has inputs $D_{3}, D_{2}, D_{1},$ and $D_{0}$ in descending order of priority. The two-bit output $A B$ is generated as 00, 01, 10, and 11 corresponding to inputs $D_{3}, D_{2}, D_{1},$ and $D_{0}$ , respectively. The Boolean expression of the output bit $B$ is ______.

(A)
$\overline{D_{3}} \overline{D_{2}}$
(B)
$\overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{1}}$
(C)
$D_{3} \overline{D_{2}} + \overline{D_{3}} D_{1}$
(D)
$\overline{D_{3}} \overline{D_{1}}$

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$B = \overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{1}}$ , which is option (B).

Official answer: BSource: Official answer key, GATE 2024 EC (IISc Bengaluru)

Notation: $\overline{X}$ means the complement of $X$ . In a priority encoder an input is encoded only when every higher-priority input is 0. So the output is $00$ when $D_{3} = 1$ , $01$ when $\overline{D_{3}} D_{2}$ , $10$ when $\overline{D_{3}} \overline{D_{2}} D_{1}$ , and $11$ when $\overline{D_{3}} \overline{D_{2}} \overline{D_{1}} D_{0}$ .
Read off $B$ , the LSB of the code. $B = 1$ for code $01$ (input $D_{2}$ ) and code $11$ (input $D_{0}$ ). $B = 0$ for codes $00$ and $10$ .
Add up the conditions that give $B = 1$ : $B = \overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{2}} \overline{D_{1}} D_{0}$
Don't-care: when all four inputs are 0 there is no valid input to encode, so the output for $\overline{D_{3}} \overline{D_{2}} \overline{D_{1}} \overline{D_{0}}$ is a don't-care. Take it as 1 so it combines with the $D_{0}$ term: $\overline{D_{3}} \overline{D_{2}} \overline{D_{1}} D_{0} + \overline{D_{3}} \overline{D_{2}} \overline{D_{1}} \overline{D_{0}} = \overline{D_{3}} \overline{D_{2}} \overline{D_{1}}$
Now $B = \overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{2}} \overline{D_{1}}$ . Factor out $\overline{D_{3}}$ and apply the absorption rule $X + \overline{X} Y = X + Y$ with $X = D_{2}$ and $Y = \overline{D_{1}}$ : $B = \overline{D_{3}} (D_{2} + \overline{D_{2}} \overline{D_{1}}) = \overline{D_{3}} (D_{2} + \overline{D_{1}})$
Expanding gives $B = \overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{1}}$ , which is option (B). Check: this expression gives the right $B$ for all 15 valid input combinations, and none of the other options does.
Cross-check with the other output bit. $A = \overline{D_{3}} \overline{D_{2}} D_{1} + \overline{D_{3}} \overline{D_{2}} \overline{D_{1}}$ (with the same don't-care) $= \overline{D_{3}} \overline{D_{2}}$ . That is option (A), so (A) is the expression for $A$ , not $B$ .

KEY IDEA

Each input of a priority encoder is gated by the complements of every higher-priority input. Write $B$ as the sum of the conditions whose code has LSB 1, then set the all-zero input (no valid input) to 1 as a don't-care and simplify with $X + \overline{X} Y = X + Y$ .

WATCH OUT FOR

Leaving out the don't-care gives $B = \overline{D_{3}} D_{2} + \overline{D_{3}} \overline{D_{1}} D_{0}$ , which is not among the options. Other common slips: dropping the priority gating (writing just $D_{2} + D_{0}$ ), or choosing (A), which is the expression for the other output bit $A$ .

From the GATE 2024 EC paper. Every question of this paper · Download the full paper · All 12 Combinational questions, with notes

GATE 2024 EC Q.40: solution and answer

Answer and solution

More Combinational questions