next up previous
Next: Output of Fourier Transforms Up: Storage: What Goes Where Previous: Storage: What Goes Where

Fourier Transform Definitions and Conventions

The Fourier transform $F(k)$ of a function $f(x)$ is defined as

\begin{displaymath}
F(k) = \int_{-\infty}^{\infty} f(x) e^{2 \pi i k x} dx
\end{displaymath} (1)


\begin{displaymath}
f(x) = \int_{-\infty}^{\infty} F(k) e^{-2 \pi i k x} dk.
\end{displaymath} (2)

A discrete Fourier transform takes a function $f(x)$ known only at $N$ discrete points $f_a \equiv f(x_a)$ and gives back a function $F_b$ known only at the discrete points $k_b$
\begin{displaymath}
F_b \equiv \sum_{a=0}^{N-1} f_a e^{2 \pi i a b/N}
\end{displaymath} (3)


\begin{displaymath}
f_a = {1 \over N} \sum_{b=0}^{N-1} F_a e^{-2 \pi a b/N}.
\end{displaymath} (4)

Note that the relationship between the discrete Fourier transform and the continuous one is
\begin{displaymath}
F_b \approx \Delta x F(k_b)
\end{displaymath} (5)

where $\Delta x$ is the spacing between points $x_a$ and the spacing between frequencies $k_b$ is given by
\begin{displaymath}
\Delta k = {1 \over N \Delta x}.
\end{displaymath} (6)

(Note that I am following the conventions of Numerical Recipes using $k$ to denote frequency rather than angular frequency. The conversion is simply $\omega = 2 \pi k$.) Formally the discrete Fourier transform $F_b$ is periodic with period $N$ so $b$ can take any set of $N$ consecutive values. Practically speaking, though, if the points $x_a$ represent a typical region of the function $f(x)$ then the results $F_b$ give the frequency components in the range $-N/2 \leq b \leq
N/2$ (where $F_{-N/2} = F_{N/2}$ by periodicity). The next section describes how these complex points are arranged in the output of the routines fftc1 and fftcn. The following section describes the additional information needed to interpret the results of the real Fourier transform routines fftr1 and fftrn.


next up previous
Next: Output of Fourier Transforms Up: Storage: What Goes Where Previous: Storage: What Goes Where

Go to The FFTEASY Home Page
Go to Gary Felder's Home Page
Send email to Gary at gfelder@email.smith.edu

This documentation was generated on 2003-09-30