# fast Fourier Transform difference with discrete Fourier Transform

I'm a french student in engineering and I'm given a kind of mandatory technical project to work out on until February.

I must investigate the following article: Precise and fast spatial-frequency analysis using the iterative local Fourier transform and implement the same kind of iterative algorithm on MATLAB.

Actually I'm not good at signal processing either that much, only have the basics, however I don't understand why they say "the inherent frequency interval limit (of fFT) can be overcome using discrete Fourier transform". In my opinion that is non-sense because fFT is basically just the same as dFT, you just have to sum the sampled values an other way with their odd and even indexes. Therefore I don't really understand what do they apply dFT for...

If someone could help me please he would be more than welcome !

Thank you

• DFT is a transform. FFT is an algorithm to compute that transform. BTW, this article is not accessible (for me at least) so you should provide a more complete quotation. Nov 21, 2017 at 21:22
• Hello thanks for your answer. Here is the title of the article : "precise and fast spatial-frequency analysis" sukmock lee normally it's the 2nd link on Google Nov 21, 2017 at 22:08

That's a strange paper.

It seems like the authors didn't really understood that the FFT and the DFT are computing the exact same thing. The FFT is just a smart way to compute the DFT in an efficient manner. Lots of hand-waving in this paper with little mathematics.

In contrast to the fFT, which calculates the entire frequency spectral range at once, the discrete Fourier transform can only evaluate a set of arbitrarily or (if available) optimally selected frequency coordinates with a high resolution.

It is true, that using the discrete Fourier transform you can short-cut and only compute it for frequencies of interest while you are practically forced to compute the complete result using FFT. Also you can't pick an arbitrarily frequency with either the FFT or the DFT.

My guess what they're talking about:

If you take a step back and think about the DFT: It's just a correlation of an input signal with a bunch of sine-waves. The frequency of the sine-waves are chosen to integer multiples of whole sine-periods. The key idea behind this is, that the sine-waves at this frequencies are orthogonal to each other. This makes it possible to decompose and reconstruct all possible input signals without loss and ambiguity.

If you want to improve resolution for a single frequency you can evaluate the correlation with sine-waves of your choice. You'll loose the orthogonal property of the DFT but if you're only interested in the signals spectral magnitude at this specific frequency that's okay. Just don't try to decompose and reconstruct a signal with it because the orthogonality is gone.

If you do so, you're not doing an DFT anymore! You're somewhat in the middle of a discrete sine transform and a discrete cosine transform.

In the paper the authors are interested in peaks within the signal spectrum. What they do is to first do an FFT of the signal to find a first estimate of the peak location. Then they 'zoom' into the spectrum by doing correlation with frequencies that exactly fall between the spectral bins within their window of interest.

Afterwards, then they shrink the window of interest and and evaluate the new inbetween frequencies. Do this 10 times and you'll get the 2^10 frequency resolution improvement.

Btw, in my opinion it is debatable if their resulting peak frequency is an improvement over just doing FFT and find the peak there. Using their zoom technique they certainly generate a nice and smooth looking high resolution spectrum. Curve-fitted to find the peak will certainly yield a peak with very low error. They don't go into any detail to what extend the spectral leakage of their method skews their smooth looking spectrum at the first place.

• +1, the phrase that's used for this technique is 'empty resolution'. Interpolation on the normal DFT/FFT is far faster and loses no information, amplitude, position, even phase! Leakage related skew is identical too. Nov 22, 2017 at 5:17
• @Neil_UK I thought about it a bit longer and came to the conclusion that doing a correlation with non integer periods is identical to zero padding and doing an ordinary DFT on selected frequencies.. So no additional spectral leakage, but no higher resolution either. Nov 22, 2017 at 6:48
• another way of getting the same result is to note that the amplitude/frequency output of a DFT is Nyquist sampled in the frequency domain, so the original signal is entirely reconstructible from those elements alone. It doesn't matter if the input time samples are correctly Nyquist sampled or not, once the sampling has been done, any aliasing is 'baked into' the samples, and no amount of different linear analysis of those samples will undo it (extra info from a model could). Only resampling the original, not reanalysis of the samples, allows anything different than interpolation to be got. Nov 23, 2017 at 10:03
• Sorry for the late response, this week I've been very busy... I thank you for your help ! but why "In contrast to the fFT, which calculates the entire frequency spectral range at once, the discrete Fourier transform can only evaluate a set of arbitrarily or (if available) optimally selected frequency coordinates with a high resolution" ? And if I do a DFT again with for instance 25 selected frequencies around the peak I will only have 25 new frequencies is it a problem ? Nov 26, 2017 at 20:42