mikeash.com pyblog/friday-qa-2012-11-02-building-the-fft.html comments

aReader - 2016-05-17 22:57:00

Tue, 17 May 2016 22:57:00 GMT

There are some missing parts, I assume due to non-escaped characters.

jamie - 2012-11-16 23:46:26

Fri, 16 Nov 2012 23:46:26 GMT

"If your 5-sample signal is meant to be periodic (with a period of 5), then the "right" way is to pad with the same sequence - but adjusting the size to 8 or 16 should give you different frequency responses"

You're presuming:
- a steady-state signal,
- with a known period,
- and all higher components (harmonic or otherwise) are even multiples of the fundamental period.

If any of those aren't true, your padding scheme wouldn't work.

An 8-sample window of a 5-sample signal might give a wrong zero-padded result, but you are remembering to window your samples with an apodization function, right? You can't just stick zeroes at the end of {0,1,2,0,1} and expect it to work, the samples have to be tapered. This causes spectral leakage, but that's a consequence of sampling a non-contrived signal, and it unavoidable.

You can only avoid having to use a windowing function by having prior knowledge of the signal, and if you require that level of precision, for an input of arbitrary length, I don't think the FFT is the droid you're looking for.

Arseny Kapoulkine - 2012-11-09 21:05:27

Fri, 09 Nov 2012 21:05:27 GMT

Thanks for the KissFFT link - this does give me the info I wanted. What their implementation does is get the prime factors of the dataset size and then use the divide&conquer approach for each prime factor. As far as I can tell, each butterfly step is quadratic in the prime factor size, something like O((N/p) * p^2) = O(N*p), so for powers of two you get O(N) for each stage, but for i.e. a prime N you get O(N^2).

On to padding; I guess it depends on what you're using FFT for. I'm remarking that AFAICS there is no way to compute DFT for a NPOT dataset using the outlined algorithm with any padding - for example, the sine wave frequencies of the distribution are different?

For some applications it might not matter, I guess - i.e. using FFT as a means of fast convolution should work with zero-padding.

If you *are* interested in frequency response by itself, however, why should you pad with zeroes? The padding values change the result of the FFT, which means that you can't choose the padding values arbitrarily. If your 5-sample signal is meant to be periodic (with a period of 5), then the "right" way is to pad with the same sequence - but adjusting the size to 8 or 16 should give you different frequency responses, i.e.:

http://www.wolframalpha.com/input/?i=DFT%5B1%2C+2%2C+3%5D%2C+DFT%5B1%2C+2%2C+3%2C+0%5D%2C+DFT%5B1%2C+2%2C+3%2C+1%5D%2C+DFT%5B1%2C+2%2C+3%2C+1%2C+2%2C+3%2C+1%2C+2%5D

Chris Liscio - 2012-11-07 21:40:31

Wed, 07 Nov 2012 21:40:31 GMT

Zero-padding the FFT does not produce incorrect results. In fact, it's the recommended approach when you're dealing with NPOT (non-power-of-two) data sets.

If you're getting bad results, it's because you're either doing something wrong, or perhaps your expectations are incorrect. Care to elaborate more on this?

As for answering your question, I believe there are algorithms that 'degrade gracefully' such that they're not as slow as the straightforward implementation, but they're definitely nowhere near the performance of a power-of-two data set. I'm not sure on their O notation runtimes though.

Check out the KissFFT implementation if you're interested in their approach. It's a fairly readable implementation of the FFT that also handles NPOT data sets.

Arseny Kapoulkine - 2012-11-07 20:44:22

Wed, 07 Nov 2012 20:44:22 GMT

Something that's been bugging me for a while but that I haven't looked into yet - maybe you know the answer! - is the problem of non-power-of-two sized data sets.

Is it possible to compute the FT in O(NlogN) in case the size is not the power of two? (padding the data with zeroes and applying FFT obviously generates wrong results; I think the same goes for padding with the repeated version of the data)