TSP (libtsp) - SPfCFFT

SPfCFFT

Routine

void SPfCFFT (float x[], float y[], int N, int Ifn)

Purpose

Fast Fourier transform (complex data)

Description

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).

Reference:: 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),
         n=0

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

Parameters

<-> float x[]: Array of length N containing the real part of the data
<-> float 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