search

mborgerding / kissfft

a Fast Fourier Transform (FFT) library that tries to Keep it Simple, Stupid
Other
1.46k stars 283 forks source link

Could you tell me the theory of the detail implement about kissfft ? #63

Closed wenwu-glagle closed 3 years ago

wenwu-glagle commented 3 years ago

Could you tell me the theory of the detail implement about kissfft, maybe a book or web.

I am confused about the code like in kiss_fftr(): 

    for ( k=1;k <= ncfft/2 ; ++k ) {
        fpk    = st->tmpbuf[k]; 
        fpnk.r =   st->tmpbuf[ncfft-k].r;
        fpnk.i = - st->tmpbuf[ncfft-k].i;
        C_FIXDIV(fpk,2);
        C_FIXDIV(fpnk,2);

        C_ADD( f1k, fpk , fpnk );
        C_SUB( f2k, fpk , fpnk );
        C_MUL( tw , f2k , st->super_twiddles[k-1]);

        freqdata[k].r = HALF_OF(f1k.r + tw.r);
        freqdata[k].i = HALF_OF(f1k.i + tw.i);
        freqdata[ncfft-k].r = HALF_OF(f1k.r - tw.r);
        freqdata[ncfft-k].i = HALF_OF(tw.i - f1k.i);
    }

Thanks.

abfan1127 commented 3 years ago

Its probably best to start with the Wikipedia Entry for Fast Fourier Transform, then build up from there. Know that the FFTR assumes the input is a Real valued input (as opposed to complex value).

https://en.wikipedia.org/wiki/Fast_Fourier_transform

mborgerding commented 3 years ago

This might help explain the kiss_fftr code. Two FFTs are done in parallel of the even and odd sequences, then recombined.