Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Discrete Fourier Transform and Hand-waving

  1. Feb 4, 2013 #1
    Hi all,

    I'm reading the following PDF about the DFT:

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

    Please see pages 152-153.

    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. jcsd
  3. Feb 4, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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
  4. Feb 4, 2013 #3
    Whoa... thanks, that's absolutely perfect.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Discrete Fourier Transform and Hand-waving
Loading...