Discrete Fourier Transform with different period

[vibe3]

Hi all, I have a seemingly simple problem which is I'd like to efficiently evaluate the following sums:

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

for k=0...n-1. Now if \alpha = 2\pi, then this reduces to a standard DFT and I can use a standard FFT library to compute the sums. But if \alpha \ne 2\pi 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 2 \pi.

Any help is appreciated!

 

[AlephZero]

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