Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: FFTW 3.3.5: The 1d Discrete Fourier Transform (DFT) Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: Chris@42:
Chris@42:

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

Chris@42:
Chris@42:
Chris@42: Chris@42:

4.8.1 The 1d Discrete Fourier Transform (DFT)

Chris@42: Chris@42: Chris@42: Chris@42:

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

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

Chris@42: Chris@42:

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

Chris@42: Chris@42:

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

Chris@42: Chris@42: Chris@42: Chris@42: Chris@42: