# Discrete Fourier Transform and Hand-waving

1. Feb 4, 2013

### mathman44

Hi all,

http://www.analog.com/static/imported-files/tech_docs/dsp_book_Ch8.pdf

So the inverse DFT (frequency to space, x = ...) 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.

2. Feb 4, 2013

### 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.

Last edited: Feb 4, 2013
3. Feb 4, 2013

### mathman44

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