1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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 with different period

  1. Sep 13, 2012 #1
    Hi all, I have a seemingly simple problem which is I'd like to efficiently evaluate the following sums:

    Y_k = \sum_{j=0}^{n-1} c_j e^{\frac{i j k \alpha}{n}}

    for [itex]k=0...n-1[/itex]. Now if [itex]\alpha = 2\pi[/itex], then this reduces to a standard DFT and I can use a standard FFT library to compute the sums. But if [itex]\alpha \ne 2\pi[/itex] then I don't see how I can put this into standard DFT form to use a regular FFT library on this.

    I guess this problem amounts to computing a DFT with harmonics that do not necessarily have periods of [itex]2 \pi[/itex].

    Any help is appreciated!
  2. jcsd
  3. Sep 13, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    This situation happens all the time when you analyse measured data, because obviously you don't know exactly what frequencies are in the data till AFTER you have measured it and processsed it.

    If you do a DFT on the raw data, the result will be hard to understand, because the discontinuity between the two ends of the sample will produce a lot of high frequency Fourier components that don't mean anything physically.

    One standard technique is to multiply the data by a "windowing function" which is close to 0 at the ends of the range, and close to 1 in the middle. That gets rid of the meaningless high frequency fourier components by making the ends of the sample "match up" (both become close to 0), but at the cost of blurring the frequency components you are intrested in.

    There are several different windowing functions that have been invented, with different tradeoffs between the amount of filtering and the amount of blurring, but if you are new to this I would recommend the Hanning window
    http://en.wikipedia.org/wiki/Hann_function Note, there is also a Hamming window - be careful with the spelling!

    This might be useful: http://www.tmworld.com/electronics-news/4383713/Windowing-Functions-Improve-FFT-Results-Part-I (and also part 2)

    "Real world" signal processing programs like Matlab have these windowing options built in, so you don't have to work out the math yourself.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook