The radix-2 algorithms described in this section are simple and compact, although not necessarily the most efficient. They use the Cooley-Tukey algorithm to compute in-place complex FFTs for lengths which are a power of 2 -- no additional storage is required. The corresponding self-sorting mixed-radix routines offer better performance at the expense of requiring additional working space.

All these functions are declared in the header file ``gsl_fft_complex.h'`.

__Function:__int**gsl_fft_complex_radix2_forward***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_transform***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_backward***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_inverse***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
These functions compute forward, backward and inverse FFTs of length

`n`with stride`stride`, on the packed complex array`data`using an in-place radix-2 decimation-in-time algorithm. The length of the transform`n`is restricted to powers of two.The functions return a value of

`GSL_SUCCESS`

if no errors were detected, or`GSL_EDOM`

if the length of the data`n`is not a power of two.

__Function:__int**gsl_fft_complex_radix2_dif_forward***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_dif_transform***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_dif_backward***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
__Function:__int**gsl_fft_complex_radix2_dif_inverse***(gsl_complex_packed_array*`data`[], size_t`stride`, size_t`n`)-
These are decimation-in-frequency versions of the radix-2 FFT functions.

Here is an example program which computes the FFT of a short pulse in a sample of length 128. To make the resulting fourier transform real the pulse is defined for equal positive and negative times (@math{-10} ... @math{10}), where the negative times wrap around the end of the array.

#include <stdio.h> #include <math.h> #include <gsl/gsl_errno.h> #include <gsl/gsl_fft_complex.h> #define REAL(z,i) ((z)[2*(i)]) #define IMAG(z,i) ((z)[2*(i)+1]) int main (void) { int i; double data[2*128]; for (i = 0; i < 128; i++) { REAL(data,i) = 0.0; IMAG(data,i) = 0.0; } REAL(data,0) = 1.0; for (i = 1; i <= 10; i++) { REAL(data,i) = REAL(data,128-i) = 1.0; } for (i = 0; i < 128; i++) { printf ("%d %e %e\n", i, REAL(data,i), IMAG(data,i)); } printf ("\n"); gsl_fft_complex_radix2_forward (data, 1, 128); for (i = 0; i < 128; i++) { printf ("%d %e %e\n", i, REAL(data,i)/sqrt(128), IMAG(data,i)/sqrt(128)); } return 0; }

Note that we have assumed that the program is using the default error
handler (which calls `abort`

for any errors). If you are not using
a safe error handler you would need to check the return status of
`gsl_fft_complex_radix2_forward`

.

The transformed data is rescaled by @math{1/\sqrt N} so that it fits on the same plot as the input. Only the real part is shown, by the choice of the input data the imaginary part is zero. Allowing for the wrap-around of negative times at @math{t=128}, and working in units of @math{k/N}, the DFT approximates the continuum fourier transform, giving a modulated @math{\sin} function.

@image{fft-complex-radix2-t,3.4in} @image{fft-complex-radix2-f,3.4in}

A pulse and its discrete fourier transform, output from the example program.

Go to the first, previous, next, last section, table of contents.