Inverse discrete Fourier transform

1k Views Asked by At

I'm having a silly problem in seeing how the inverse DFT is actually the inverse of the DFT. Consider an array $\{x_0,\dots,x_{N-1}\}$, the DFT is given by

$$X_k=\sum_{n=0}^{N-1}x_ne^{-\frac{2\pi i}{N}nk} $$

And the IDFT

$$x_n=\frac{1}{N}\sum_{k=0}^{N-1}X_ke^{\frac{2\pi i}{N}nk} $$

Let's actually try to take the IDFT of $X_k$

$$\frac{1}{N}\sum_{k=0}^{N-1}X_ke^{\frac{2\pi i}{N}nk}=\frac{1}{N}\sum_{k=0}^{N-1}\sum_{l=0}^{N-1}x_le^{-\frac{2\pi i}{N}lk}e^{\frac{2\pi i}{N}nk}=\frac{1}{N} \sum_{k=0}^{N-1}\sum_{l=0}^{N-1}x_le^{-\frac{2\pi i}{N}k(l-n)}$$

we can sum the geometric sum in $k$ if $l\neq n$, if $l=n$ we just get $x_n$

$$ x_n+\frac{1}{N}\sum_{l\neq n}x_l\frac{1-e^{-2\pi i (l-n)}}{1-e^{-\frac{2\pi i}{N}(l-n)}}$$

I can't see why the second term should be $0$

1

There are 1 best solutions below

1
On BEST ANSWER

You simply have that in your last expression, since $l\ne n$ $$ 1-e^{-2\pi i (l-n)} = 0 $$ since the exponent is an integer multiple of $2 \pi$.

Contrary to that, the denominator $$ 1-e^{-\frac{2\pi}{N} i (l-n)} \ne 0 $$