GATE 2018 IN Q.35: solution and answer

GATE 2018 · INQ.35 · 2 marks · MCQ

For the sequence $x [n] = {1, - 1, 1, - 1}$ , with $n = 0, 1, 2, 3$ , the DFT is computed as $X (k) = \sum_{n = 0}^{3} x [n] e^{- j \frac{2 π}{4} nk}$ , for $k = 0, 1, 2, 3$ . The value of $k$ for which $X (k)$ is not zero is

(A)
0
(B)
1
(C)
2
(D)
3

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$X (k) = {0, 0, 4, 0}$ , so the only non-zero value is at $k = 2$ . Answer: (C).

Official answer: CSource: Official answer key, GATE 2018 IN (IIT Guwahati)

Recognise the sequence: $x [n] = {1, - 1, 1, - 1} = (- 1)^{n} = e^{j π n} = e^{j \frac{2 π}{4} \cdot 2 n}$ . It is a single complex exponential sitting exactly at DFT bin $k_{0} = 2$ .
Substitute into the 4-point DFT: $X (k) = n = 0 \sum 3 e^{j \frac{2 π}{4} 2 n} e^{- j \frac{2 π}{4} nk} = n = 0 \sum 3 e^{- j \frac{2 π}{4} n (k - 2)}$
Orthogonality of the DFT basis (sum of the $N$ -th roots of unity): $\sum_{n = 0}^{N - 1} e^{- j \frac{2 π}{N} nm} = N$ if $m \equiv 0 (mod N)$ , and $0$ otherwise. With $m = k - 2$ and $k \in {0, 1, 2, 3}$ , only $k = 2$ gives $m \equiv 0 (mod 4)$ . So $X (k) = 4 δ [k - 2]$ , i.e. $X (k) = {0, 0, 4, 0}$ .
Check directly: $X (0) = \sum x [n] = 1 - 1 + 1 - 1 = 0$ ; $X (2) = \sum x [n] (- 1)^{n} = 1 + 1 + 1 + 1 = 4$ .
Check $k = 1$ using $e^{- j \frac{π}{2} n} = 1, - j, - 1, j$ for $n = 0, 1, 2, 3$ : $X (1) = (1) (1) + (- 1) (- j) + (1) (- 1) + (- 1) (j) = 1 + j - 1 - j = 0$ . Since $x [n]$ is real, $X (N - k) = X^{*} (k)$ , so $X (3) = X^{*} (1) = 0$ .
Only $X (2)$ is non-zero, so $k = 2$ : option (C).

KEY IDEA

$x [n] = (- 1)^{n} = e^{j \frac{2 π}{N} \cdot \frac{N}{2} n}$ is one DFT basis vector, the one at the Nyquist bin $k = N /2$ . Because the DFT basis vectors are orthogonal, all its energy falls in that one bin: $X (k) = N δ [k - N /2]$ . Here that is $4 δ [k - 2]$ .

WATCH OUT FOR

Picking $k = 0$ because it is the DC term, when in fact $X (0) = \sum x [n] = 0$ for this zero-mean sequence. A second mistake is getting the sign of $e^{- j π n /2}$ wrong at $n = 1, 3$ , which makes $X (1)$ or $X (3)$ look non-zero. Remember $e^{- j π /2} = - j$ and $e^{- j 3 π /2} = + j$ .

From the GATE 2018 IN paper. Every question of this paper · Download the full paper · All 11 DTFT & DFT questions, with notes

GATE 2018 IN Q.35: solution and answer

Answer and solution

More DTFT & DFT questions