GNU Scientific Library Reference Manual - Third Edition (v1.12)by M. Galassi, J. Davies, J. Theiler, B. Gough, G. Jungman, P. Alken, M. Booth, F. Rossi Paperback (6"x9"), 592 pages, 60 figures ISBN 0954612078 RRP £24.95 ($39.95) |

## 15.5 Overview of real data FFTs

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

ISBN 0954612078 | GNU Scientific Library Reference Manual - Third Edition (v1.12) | See the print edition |