void SPdCFFT (double x[], double y[], int N, int Ifn)


Fast Fourier transform (complex data)


This subroutine calculates the discrete Fourier transform or the inverse discrete Fourier transform of a set of complex numbers using the fast Fourier transform algorithm developed by G. Sande (mixed radix 4 and radix 2).
W. M. Gentleman and G. Sande, "Fast Fourier Transforms - For Fun and Profit", 1966 Fall Joint Computer Conference.
The calculation is done in place, that is the output data replaces the input data. The k-th complex output data point of the N point discrete Fourier transform is

         N-1           nk
  G(k) = SUM  g(n) * W     ,  where W = exp(-j*2*pi/N),

where j is the imaginary operator, and g(n) is the n-th complex input data point. The k-th complex output data point of the N point inverse discrete Fourier transform is

          1  N-1          -nk
  g(n) =  -  SUM  G(k) * W   .
          N  k=0


<-> double x[]
Array of length N containing the real part of the data
<-> double y[]
Array of length N containing the imaginary part of the data
-> int N
Number of elements in each of the arrays x and y. N must be a power of two.
-> int Ifn
Input parameter, positive for the forward transform and negative for the inverse transform.

Author / revision

P. Kabal / Revision 1.4 2003/05/09

See Also


Main Index libtsp