GNU Info

(fftw.info)What FFTW Really Computes

---

Prev: fftw_destroy_plan Up: One-dimensional Transforms Reference

---

Enter node , (file) or (file)node

What FFTW Really Computes
-------------------------

   In this section, we define precisely what FFTW computes.  Please be
warned that different authors and software packages might employ
different conventions than FFTW does.

   The forward transform of a complex array X of size n computes an
array Y, where

 Y[i] = sum for j = 0 to (n - 1) of X[j] * exp(-2 pi i j sqrt(-1)/n) .

   The backward transform computes

 Y[i] = sum for j = 0 to (n - 1) of X[j] * exp(2 pi i j sqrt(-1)/n) .

   FFTW computes an unnormalized transform, that is, the equation
IFFT(FFT(X)) = n X holds.  In other words, applying the forward and
then the backward transform will multiply the input by n.

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