search

mborgerding / kissfft

a Fast Fourier Transform (FFT) library that tries to Keep it Simple, Stupid
Other
1.39k stars 278 forks source link

zero padding #17

Closed rs1909 closed 5 years ago

rs1909 commented 5 years ago

Hi there. I need an fft that produces many more frequencies than data points. This can be done with padding the data with zeros. It would be nice if I did not have to actually pad the data with zeros, the fft code would just sum up to ndata, but still calculate frequencies up to nfft, where nfft > ndata. This should be a rather simple change and would make the library vastly more useful. Thanks.

codecogseqn 2

mborgerding commented 5 years ago

This might avoid some of the early stages of the FFT, but to do this for arbitrary zero padding would require considerable changes down in the bowels of the code. I fear the resulting processor savings would be minimal. Not exactly upholding the KISS principle -- especially considering the limited applicability.

There is one special case though, that might warrant inclusion in tools. In the case where N_f / N_d is some integer K, you could build an oversample-by-K FFT on top of any existing FFT library with a decimation-in-frequency approach. Consider the fact that an N_d point FFT of the original signal gives you decimated bins of the large N_f point FFT [0,K,2K,...]. If you apply a 1/N_f frequency shift and do another FFT of the shifted signal, you get bins [1,K+1,2K+1,...]. Do this at K different shifts and you've calculated the whole large FFT.