Next: Mixed-radix FFT routines for real data, Previous: Overview of real data FFTs, Up: Fast Fourier Transforms [Index]

This section describes radix-2 FFT algorithms for real data. They use the Cooley-Tukey algorithm to compute in-place FFTs for lengths which are a power of 2.

The radix-2 FFT functions for real data are declared in the header files
`gsl_fft_real.h`

- Function:
*int***gsl_fft_real_radix2_transform***(double*`data`[], size_t`stride`, size_t`n`) -
This function computes an in-place radix-2 FFT of length

`n`and stride`stride`on the real array`data`. The output is a half-complex sequence, which is stored in-place. The arrangement of the half-complex terms uses the following scheme: for*k < n/2*the real part of the*k*-th term is stored in location*k*, and the corresponding imaginary part is stored in location*n-k*. Terms with*k > n/2*can be reconstructed using the symmetry*z_k = z^*_{n-k}*. The terms for*k=0*and*k=n/2*are both purely real, and count as a special case. Their real parts are stored in locations*0*and*n/2*respectively, while their imaginary parts which are zero are not stored.The following table shows the correspondence between the output

`data`and the equivalent results obtained by considering the input data as a complex sequence with zero imaginary part (assuming`stride=1`),complex[0].real = data[0] complex[0].imag = 0 complex[1].real = data[1] complex[1].imag = data[n-1] ............... ................ complex[k].real = data[k] complex[k].imag = data[n-k] ............... ................ complex[n/2].real = data[n/2] complex[n/2].imag = 0 ............... ................ complex[k'].real = data[k] k' = n - k complex[k'].imag = -data[n-k] ............... ................ complex[n-1].real = data[1] complex[n-1].imag = -data[n-1]

Note that the output data can be converted into the full complex sequence using the function

`gsl_fft_halfcomplex_radix2_unpack`

described below.

The radix-2 FFT functions for halfcomplex data are declared in the
header file `gsl_fft_halfcomplex.h`.

- Function:
*int***gsl_fft_halfcomplex_radix2_inverse***(double*`data`[], size_t`stride`, size_t`n`) - Function:
*int***gsl_fft_halfcomplex_radix2_backward***(double*`data`[], size_t`stride`, size_t`n`) -
These functions compute the inverse or backwards in-place radix-2 FFT of length

`n`and stride`stride`on the half-complex sequence`data`stored according the output scheme used by`gsl_fft_real_radix2`

. The result is a real array stored in natural order.

- Function:
*int***gsl_fft_halfcomplex_radix2_unpack***(const double*`halfcomplex_coefficient`[], gsl_complex_packed_array`complex_coefficient`, size_t`stride`, size_t`n`) This function converts

`halfcomplex_coefficient`, an array of half-complex coefficients as returned by`gsl_fft_real_radix2_transform`

, into an ordinary complex array,`complex_coefficient`. It fills in the complex array using the symmetry*z_k = z_{n-k}^**to reconstruct the redundant elements. The algorithm for the conversion is,complex_coefficient[0].real = halfcomplex_coefficient[0]; complex_coefficient[0].imag = 0.0; for (i = 1; i < n - i; i++) { double hc_real = halfcomplex_coefficient[i*stride]; double hc_imag = halfcomplex_coefficient[(n-i)*stride]; complex_coefficient[i*stride].real = hc_real; complex_coefficient[i*stride].imag = hc_imag; complex_coefficient[(n - i)*stride].real = hc_real; complex_coefficient[(n - i)*stride].imag = -hc_imag; } if (i == n - i) { complex_coefficient[i*stride].real = halfcomplex_coefficient[(n - 1)*stride]; complex_coefficient[i*stride].imag = 0.0; }