Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: FFTW 3.3.8: The 1d Discrete Fourier Transform (DFT) Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: Chris@82:
Chris@82:

Chris@82: Next: , Previous: , Up: What FFTW Really Computes   [Contents][Index]

Chris@82:
Chris@82:
Chris@82: Chris@82:

4.8.1 The 1d Discrete Fourier Transform (DFT)

Chris@82: Chris@82: Chris@82: Chris@82:

The forward (FFTW_FORWARD) discrete Fourier transform (DFT) of a Chris@82: 1d complex array X of size n computes an array Y, Chris@82: where: Chris@82:

.
Chris@82: The backward (FFTW_BACKWARD) DFT computes: Chris@82:
.
Chris@82:

Chris@82: Chris@82:

FFTW computes an unnormalized transform, in that there is no coefficient Chris@82: in front of the summation in the DFT. In other words, applying the Chris@82: forward and then the backward transform will multiply the input by Chris@82: n. Chris@82:

Chris@82: Chris@82:

From above, an FFTW_FORWARD transform corresponds to a sign of Chris@82: -1 in the exponent of the DFT. Note also that we use the Chris@82: standard “in-order” output ordering—the k-th output Chris@82: corresponds to the frequency k/n (or k/T, where T Chris@82: is your total sampling period). For those who like to think in terms of Chris@82: positive and negative frequencies, this means that the positive Chris@82: frequencies are stored in the first half of the output and the negative Chris@82: frequencies are stored in backwards order in the second half of the Chris@82: output. (The frequency -k/n is the same as the frequency Chris@82: (n-k)/n.) Chris@82:

Chris@82: Chris@82: Chris@82: Chris@82: Chris@82: