Discrete Fourier Transform and Hand-waving

mathman44

Hi all,

I'm reading the following PDF about the DFT:

http://www.analog.com/static/importe...p_book_Ch8.pdf

Please see pages 152-153.

So the inverse DFT (frequency to space, x[i] = ...) is given on page 152. Then it is claimed that the amplitudes for the space-domain synthesis (inverse DFT) are different than the frequency domain of a signal (page 153).

In short, the amplitude for the space-domain synthesis is the corresponding frequency domain multiplied by 2/N, except for the zero frequency term and the last frequency term, which are multiplied by 1/N.

A short digression on 'spectral densities' are made, and I really don't see the connection. Why are the different frequency components weighted differently in the space-domain synthesis?

Any help would be great.
Thanks.

jbunniii

If we define
$$X(k) = \sum_{n=0}^{N-1} x(n) e^{-i2\pi k n/N}$$
for ##k=0, 1, \ldots, N-1##, and we want to recover ##x(n)## from ##X(k)##, then
$$x(n) = \frac{1}{N} \sum_{k=0}^{N-1} X(k) e^{i2\pi k n/N}$$
Here the ##X(k)## are complex-valued. We can obtain an equivalent expression in terms of the real and imaginary parts of ##X(k)## by writing ##X(k) = R(k) + iI(k)## and simplifying:
$$x(n) = \frac{1}{N} \sum_{k=0}^{N-1} R(k) e^{i2\pi k n/N} + i \frac{1}{N} \sum_{k=0}^{N-1} I(k) e^{i2\pi k n/N}$$
where ##R(k)## and ##I(k)## are real-valued.

Now suppose the original data ##x(n)## is real-valued. Then notice that if we take the complex conjugate of the first equation above, we get
$$X^*(k) = \sum_{n=0}^{N-1} x(n) e^{i2\pi k n/N}$$
Now replace ##k## by ##N-k##:
$$X^*(N-k) = \sum_{n=0}^{N-1} x(n) e^{i2\pi (N-k) n/N} = \sum_{n=0}^{N-1} x(n) e^{-i2\pi k n/N} = X(k)$$
So we have established that ##X^*(N-k) = X(k)##. Now take the real and imaginary parts of this equation. We see that ##R(N-k) = R(k)## and ##-I(N-k) = I(k)##. This allows us to rewrite the two sums involving ##R(k)## and ##I(k)##. I will show how this works for ##R(k)##. You can do something similar for ##I(k)##.
$$\begin{align}
\sum_{k=0}^{N-1} R(k) e^{i2\pi k n/N} &= R(0) + \sum_{k=1}^{N/2 - 1} R(k) e^{i2\pi k n/N} + R(N/2) e^{i\pi n} + \sum_{k=N/2+1}^{N-1} R(k) e^{i2\pi k n/N}\\
&= R(0) + \sum_{k=1}^{N/2 - 1} R(k) e^{i2\pi k n/N} + R(N/2) \cos(\pi n) + \sum_{k=N/2+1}^{N-1}R(N-k)e^{i2\pi kn/N} \\
&= R(0) + \sum_{k=1}^{N/2 - 1} R(k) e^{i2\pi k n/N} + R(N/2) \cos(\pi n) + \sum_{m=1}^{N/2-1} R(m) e^{-i 2\pi mn/N} \\
&= R(0) + \sum_{k=1}^{N/2 - 1} R(k) (e^{i2\pi k n/N} + e^{-i2\pi k n/N}) + R(N/2)\cos(\pi n) \\
&= R(0) + 2 \sum_{k=1}^{N/2 - 1} R(k)\cos(2\pi k n/N) + R(N/2) \cos(\pi n)
\end{align}$$
This shows why there is a factor of 2 on all of the terms from ##k=1, 2, \ldots N/2-1## but not on the ##k=0## and ##k=N/2## terms.

I have used the following facts above: for the ##k=0## term,
$$e^{i2\pi k n/N} = e^{i2\pi 0 n/N} = e^{0} = 1$$
For the ##k=N/2## term:
$$e^{i2\pi k n/N} = e^{i2\pi (N/2) n/N} = e^{i \pi n} = \cos(\pi n) + i\sin(\pi n) = \cos(\pi n) + 0 = \cos(\pi n)$$
The RHS of this last equation also equals ##(-1)^n## but there was no need to use that fact here.

mathman44

Whoa... thanks, that's absolutely perfect.