Next: Radix-2 FFT routines for real data, Previous: Mixed-radix FFT routines for complex data, Up: Fast Fourier Transforms [Index]

The functions for real data are similar to those for complex data. However, there is an important difference between forward and inverse transforms. The Fourier transform of a real sequence is not real. It is a complex sequence with a special symmetry:

z_k = z_{n-k}^*

A sequence with this symmetry is called *conjugate-complex* or
*half-complex*. This different structure requires different
storage layouts for the forward transform (from real to half-complex)
and inverse transform (from half-complex back to real). As a
consequence the routines are divided into two sets: functions in
`gsl_fft_real`

which operate on real sequences and functions in
`gsl_fft_halfcomplex`

which operate on half-complex sequences.

Functions in `gsl_fft_real`

compute the frequency coefficients of a
real sequence. The half-complex coefficients *c* of a real sequence
*x* are given by Fourier analysis,

c_k = \sum_{j=0}^{n-1} x_j \exp(-2 \pi i j k /n)

Functions in `gsl_fft_halfcomplex`

compute inverse or backwards
transforms. They reconstruct real sequences by Fourier synthesis from
their half-complex frequency coefficients, *c*,

x_j = {1 \over n} \sum_{k=0}^{n-1} c_k \exp(2 \pi i j k /n)

The symmetry of the half-complex sequence implies that only half of the
complex numbers in the output need to be stored. The remaining half can
be reconstructed using the half-complex symmetry condition. This works
for all lengths, even and odd—when the length is even the middle value
where *k=n/2* is also real. Thus only `n` real numbers are
required to store the half-complex sequence, and the transform of a real
sequence can be stored in the same size array as the original data.

The precise storage arrangements depend on the algorithm, and are different for radix-2 and mixed-radix routines. The radix-2 function operates in-place, which constrains the locations where each element can be stored. The restriction forces real and imaginary parts to be stored far apart. The mixed-radix algorithm does not have this restriction, and it stores the real and imaginary parts of a given term in neighboring locations (which is desirable for better locality of memory accesses).