I've got an algorithm that zero pads a sequence to 4N, does an FFT, and only uses the lowest frequency N points out of the generated 4N.
This seems like a lot of wasted work, any ideas how this can be done faster?
Signal Processing Stack Exchange is a question and answer site for practitioners of the art and science of signal, image and video processing. It only takes a minute to sign up.Sign up to join this community
If you only a few bins then the following may be very efficient for you:
1. Simply do the DFT of at each frequency you need.
2. Use the Goertzel algorithm for each frequency in question.
Zero padding to 4X length, computing the longer FFT, and then using only the bottom 1/4th bins produces almost identical results to windowed Sinc interpolation of the original length FFT.
So just use the original FFT length and interpolate using a 3 phase Sinc interpolation kernel with a suitable window width.
Zero padding in the time domain gives you higher frequency solution but no new information, so it provides essentially interpolating in the frequency domain. Depending on the nature of your signals and the precision required you may be able to get the additional frequency points with a regular FFT of N points and doing a suitable interpolation (linear, spline, pchip, sinc etc).