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

Overview of complex data FFTs

The inputs and outputs for the complex FFT routines are packed arrays of floating point numbers. In a packed array the real and imaginary parts of each complex number are placed in alternate neighboring elements. For example, the following definition of a packed array of length 6,

gsl_complex_packed_array data[6];

can be used to hold an array of three complex numbers, z[3], in the following way,

data[0] = Re(z[0])
data[1] = Im(z[0])
data[2] = Re(z[1])
data[3] = Im(z[1])
data[4] = Re(z[2])
data[5] = Im(z[2])

A stride parameter allows the user to perform transforms on the elements z[stride*i] instead of z[i]. A stride greater than 1 can be used to take an in-place FFT of the column of a matrix. A stride of 1 accesses the array without any additional spacing between elements.

The array indices have the same ordering as those in the definition of the DFT -- i.e. there are no index transformations or permutations of the data.

For physical applications it is important to remember that the index appearing in the DFT does not correspond directly to a physical frequency. If the time-step of the DFT is @math{\Delta} then the frequency-domain includes both positive and negative frequencies, ranging from @math{-1/(2\Delta)} through 0 to @math{+1/(2\Delta)}. The positive frequencies are stored from the beginning of the array up to the middle, and the negative frequencies are stored backwards from the end of the array.

Here is a table which shows the layout of the array data, and the correspondence between the time-domain data @math{z}, and the frequency-domain data @math{x}.

index    z               x = FFT(z)

0        z(t = 0)        x(f = 0)
1        z(t = 1)        x(f = 1/(N Delta))
2        z(t = 2)        x(f = 2/(N Delta))
.        ........        ..................
N/2      z(t = N/2)      x(f = +1/(2 Delta),
                               -1/(2 Delta))
.        ........        ..................
N-3      z(t = N-3)      x(f = -3/(N Delta))
N-2      z(t = N-2)      x(f = -2/(N Delta))
N-1      z(t = N-1)      x(f = -1/(N Delta))

When @math{N} is even the location @math{N/2} contains the most positive and negative frequencies @math{+1/(2 \Delta)}, @math{-1/(2 \Delta)}) which are equivalent. If @math{N} is odd then general structure of the table above still applies, but @math{N/2} does not appear.

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