GATE 2024 EC Q.59: solution and answer

GATE 2024 · ECQ.59 · 2 marks · NAT

The relationship between any N-length sequence $x [n]$ and its corresponding N-point discrete Fourier transform $X [k]$ is defined as

X [k] = F {x [n]} .

Another sequence $y [n]$ is formed as below

y [n] = F {F {F {F {x [n]}}}} .

For the sequence $x [n] = {1, 2, 1, 3}$ , the value of $Y [0]$ is ________.

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

$Y [0] = 112$

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

Here $N = 4$ . $Y [k]$ is the $N$ -point DFT of $y [n]$ , so $Y [k] = F {y [n]} = F^{5} {x [n]}$ .
Applying the DFT twice (duality): since $x [n] = \frac{1}{N} \sum_{k} X [k] e^{j 2 π k n / N}$ , we get $F {F {x [n]}} [m] = \sum_{k} X [k] e^{- j 2 π k m / N} = N x [(- m)_{N}]$ , a circularly time-reversed copy of $x$ scaled by $N$ .
Applying this pair of DFTs once more: $F^{4} {x [n]} = N \cdot N x [(- (- n))_{N}] = N^{2} x [n]$ . With $N = 4$ , $y [n] = 16 x [n]$ .
By linearity, $Y [k] = F {16 x [n]} = 16 X [k]$ .
The DC bin of the DFT is the sum of the samples: $X [0] = \sum_{n = 0}^{3} x [n] = 1 + 2 + 1 + 3 = 7$ .
$Y [0] = 16 \times 7 = 112$

KEY IDEA

Applying the N-point DFT twice gives $N$ times the circularly time-reversed sequence, $N x [(- n)_{N}]$ . Applying it four times gives back the original sequence scaled by $N^{2}$ . So $y [n] = N^{2} x [n]$ , and then $Y [0] = N^{2} \sum_{n} x [n]$ .

WATCH OUT FOR

Assuming $F^{4}$ is the identity (true only for the unitary DFT with a $1/ N$ factor), which gives $Y [0] = 7$ . Another slip is reading $y [n]$ itself as the answer and forgetting that $Y [0]$ needs one more DFT, or treating $Y [0]$ as $y [0] = 16$ .

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

GATE 2024 EC Q.59: solution and answer

Answer and solution

More DTFT & DFT questions