cfftkissfft

Why is the kiss_fft's forward and inverse radix-4 calculation different?


I've been spending time understanding and implementing my own mixed radix decimation-in-time fast fourier transform. I've mostly been using kiss_fft and http://www.briangough.com/fftalgorithms.pdf to understand what's happening.

From what I've read, I can reverse an fft by using conjugate twiddle factors.

Yet when I read the kiss_fft source code, the radix-4 implementation actually tests if we are doing a forward or inverse transform, and uses slightly different maths.

https://github.com/itdaniher/kissfft/blob/master/kiss_fft.c#L77

    if(st->inverse) {
        Fout[m].r = scratch[5].r - scratch[4].i;
        Fout[m].i = scratch[5].i + scratch[4].r;
        Fout[m3].r = scratch[5].r + scratch[4].i;
        Fout[m3].i = scratch[5].i - scratch[4].r;
    }else{
        Fout[m].r = scratch[5].r + scratch[4].i;
        Fout[m].i = scratch[5].i - scratch[4].r;
        Fout[m3].r = scratch[5].r - scratch[4].i;
        Fout[m3].i = scratch[5].i + scratch[4].r;
    }

I thought that the fft calculations used are the same for forwards and reverse ffts (like it is for kiss_fft's radix-2, 3 and 5 implementations).

Why does kiss_fft radix-4 calculation need to do this?


Solution

  • You can use the same radix-4 computation kernel for an IFFT if you precede that computation by a vector complex conjugation. Or you can skip doing a separate preceding vector complex conjugation operation, and use a different radix-4 compute kernel which has the conjugation built-in.

    Doing the Radix-4 with the conjugation built-in might provide for better register re-use on some processor architectures.

    Note that 2 complex conjugations are included within the equation relating an IFFT to an FFT. Reverse rotating the twiddle factors only takes care on one of those.