A discrete-time sequence x(n) = {3, 5, 1, 4, −3, 5, −2, −2, 4} of length 9 has a 9-point DFT denoted by X(k), where k = 0, 1, 2, ..., 8. Another discrete-time sequence y(n) has a 9-point DFT given by
Y(k) = e^{j4πk/3} X(k), k = 0, 1, 2, ..., 8
Without explicitly computing DFT or inverse DFT, determine the sequence y(n).
5 marks · directive: Determine
Answer
The core of a good answer
e^{j4πk/3} = e^{−j2πk(3)/9} (since 4π/3 = 2π × 6/9 and 6 ≡ −3 mod 9), so y(n) = x((n − 3))₉, a circular right shift by 3: y(n) = {−2, −2, 4, 3, 5, 1, 4, −3, 5}.
An outline written by upsc.help, not an official UPSC answer; every fact checked by a separate review. How we work
What the question asks
A direct application of the circular time shift property of the N-point DFT. The candidate must convert the phase factor into the form e^{−j2πkm/N} and identify the shift m modulo 9.
Answer outline
Introduction
N = 9; x(0) to x(8) = 3, 5, 1, 4, −3, 5, −2, −2, 4.
Step 1: Rewrite the phase factor
- e^{j4πk/3} = e^{j2πk·6/9}
- Since e^{j2πk·9/9} = 1, e^{j2πk·6/9} = e^{−j2πk·3/9}
Step 2: Apply the circular shift property
- x((n − m))_N ↔ e^{−j2πkm/N} X(k)
- Here m = 3, so y(n) = x((n − 3))₉, equivalently x((n + 6))₉
Step 3: Write out y(n)
- y(0) = x(6) = −2, y(1) = x(7) = −2, y(2) = x(8) = 4
- y(3) = x(0) = 3, y(4) = x(1) = 5, y(5) = x(2) = 1
- y(6) = x(3) = 4, y(7) = x(4) = −3, y(8) = x(5) = 5
- y(n) = {−2, −2, 4, 3, 5, 1, 4, −3, 5}
Step 4: Check
- Sum of y = sum of x = 15, so Y(0) = X(0), consistent with e^{j0} = 1.
- A numerical FFT and inverse FFT with the given phase factor reproduces the same sequence.
Conclusion
y(n) = {−2, −2, 4, 3, 5, 1, 4, −3, 5}, the 9-point circular shift of x(n) to the right by 3 (or left by 6).
Examples and data to cite
- Multiplying X(k) by e^{−j2πkm/N} leaves every |X(k)| unchanged and only adds a linear phase, which is why y(n) contains exactly the same samples as x(n), only rearranged.
- Circular, not linear, shift: samples pushed off the end wrap around to the start.
Facts
Facts to remember
- N-point DFT: X(k) = Σ from n = 0 to N − 1 of x(n)e^{−j2πkn/N}.
- Circular time shift: x((n − m))_N ↔ e^{−j2πkm/N} X(k).
- e^{j2πk} = 1 for integer k, so shifts are taken modulo N.
- X(0) equals the sum of the samples.