N point convolution with complex FFT

[matt42]

Hi,

I'm working on a convolution algorithm and am using the complex FFT as I'm keen to take advantage of "two for one" processing. I've got it working nicely for stereo signals, but I realise now I'll need to process a lot of mono signals (with different impulse responses).

So I can, if I have this right, format my time domain data so that the even samples are the real and the odd samples the imaginary part of my time domain data. Then apply the forward complex FFT. At this point I should have two N/2 spectra which I would then need to process an addition butterfly stage to synthesis the final N point spectra. After the convolution I would need to decompose the signal back into two N/2 length spectra before the inverse FFT.

In the context of convolution could I rather, ahead of time, decompose the frequency data of the impulse response into two N/2 spectra and then do the convolution directly?

My knowledge of FFT is rather superficial, so any help or advice on this would be much appreciated.

Thanks,

Matt

EDIT: Should add that due to efficiency, ease of use and licensing issues I'm using mystran's Dust FFT which is complex FFT only.

[Miles1981]

You can always preprocess your impulse as you wish. It is a fix constant in the processing.

[mystran]

I do realize this is somewhat old question (haven't been reading KVR very actively lately), but I think it's worth answer anyway (for two reasons):

First, you can indeed do such a "half-length" transform and yes it required an additional butterfly. As a result you get "half-complex" spectra that only contains the positive frequencies (since the negative ones are symmetric for real data). Then you can process as usual. For IFFT you do an inverse butterfly to turn it back into two half-length spectra and then apply regular IFFT.

Second, if you haven't figured out the above already I have some good news for you. The current development version of DustFFT already implements the above and seeing this post reminds me that I should update the public version. Stay tuned.

[matt42]

Thanks for the reply, mystran. I look forward to checking out an updated version.

For the current project I'm working on the primary issues are execution time, and licencing. Float vs double isn't an issue and since I posted the original question I've found the pffft library to be the fastest FFT that fits my criteria, probably due to it taking advantage of SSE instructions on floating point data. Plus the way the it packs frequency domain data makes vectorizing the convolution easy to implement.

I'm now using real FFT for mono signals, but I guess I could still squeeze out extra gains if I could use the complex FFT for two mono signals convolved with two different impulse responses, but then I'd either need to mess around with the guts of the library to get the final butterfly, which I probably don't have the stomach for, or roll my own, which I doubt would be as efficient. I dunno....

Dust is the fastest I've found for the complex transform on doubles and is a damn fine library. The updates you mention would definitely increase it's flexibility.

[mystran]

Oh, if you want a real FFT with half-length complex FFT, then this can be done with an extra butter-fly pass (doing a real-FFT algorithm from the ground up might be slightly faster though; in any case it's still much faster than full-length complex transform). If you instead want two real FFTs together in one complex FFT (which is slightly faster than doing 2 real FFTs), then packing them as real and imaginary gives you the transforms "directly" in the sense that you only need to separate the symmetric and anti-symmetric components from positive vs. negative frequencies (which requires no fancy butterfly's, just simple summation).