How to downsample Fourier complex values?

Question

Disclaimer: I'm not a signal processing expert.

I'm writing a function that takes a 1D array and performs Fast Fourier Transform on it. Here's how it works:

1. If the array's size is not a power of two, pad it with 0s at the end so that its size becomes a power of two.
2. Perform FFT on the padded array and store the results in an array x.
3. Downsample the complex array x to match the length of the original non-padded array.
4. Return x.

I'm having trouble with step 3. If I omit step 3 and perform inverse FFT on the result of the function call, I get the initial padded array which means the function successfully performs steps 1 and 2.

I tried implementing step 3 by downsampling using linear interpolation, but when I perform inverse fourier transform on the final result using MatLab, the results I got were not equivalent to the original array. The programming language I need to use is not MatLab, I'm only using MatLab to verify correctness of the results.

What techniques can I use to perform step 3 while still being able to get back the original non-padded array after inverse FFT?

Answer 1

If you need accurate results, then you can use Bluestein's algorithm for the Chirp Z-transform to compute annoyingly-sized DFTs in O(N log N) time.

See: https://en.wikipedia.org/wiki/Chirp_Z-transform

It isn't as fast as a power-of-2 FFT, but it's much faster (for high accuracy) than interpolation on an FFT of the wrong length.

Answer 2

Use circular Sinc kernel interpolation to compute the down sampled points. The Sinc width will that of a low-pass filter with a cut-off appropriate to anti-alias for the new lower down-sampled sample rate.