How to save half computation in real output IFFT

0
votes

The FFT of real signal has the conjugate symmetric property. This property can be used to save half of the memory and half of the computation. This implementation is quite simple and I've done it.

Now I want to implement IFFT. Which applies on a conjugate symmetric signal, and a real signal is expected. As the IFFT is just the same as FFT with reversed sign twiddle factors. Is there any similar way to save half the computation and memory?

1
signal-processingfftdft
There are plenty of existing implementations of this, like link. Why wouldn't you start with one of them? – pentadecagon
@pentadecagon I'm doing cuda, and cufft is optimized for a big fft, but is not optimized enough to do many small fft. – Min Lin

1 Answers

0
votes

Bruun's FFT algorithm keeps the computation real for real signals, up to the last stage where the complex components of the spectrum are generated.

This is a similar approach as found in the Goertzel algorithm or, in a different context, of Bairstow's method relative to Newton's method for complex polynomial roots (or the real and complex variants of the Jenkins-Traub algorithm).