next up previous
Next: FFTC1: One-Dimensional Complex Fourier Up: FFTEASY C Routines for Previous: Output of Fourier Transforms


How FFTEASY works

FFTEASY uses a Cooley-Tukey Fast Fourier Transform algorithm. For an excellent discussion of Fourier transforms (continuous and discrete) in general and the Cooley-Tukey algorithm in particular see Numerical Recipes. Here I only briefly describe the algorithm and how it is implemented in FFTEASY.

The heart of the method is the Danielson-Lanczos (DL) formula that allows one to compute a discrete Fourier transform (DFT) of size $N$ by separately computing two FTs of size $N/2$. Let $F_b$ be the DFT of a function $f_a = f(x_a), a=0,1,...,N-1$. Then let $F^e_b$ be the DFT of the even points $a=0,2,...,N-2$ and $F^o_b$ be the DFT of the odd points $a=1,3,...,N-1$. The DL formula then says

\begin{displaymath}
F_b = F^e_b + e^{2 \pi i b/N} F^o_b.
\end{displaymath} (9)

For simplicity define $W \equiv e^{2 \pi i/N}$ so
\begin{displaymath}
F_b = F^e_b + W^b F^o_b.
\end{displaymath} (10)

Note that $F^e$ and $F^o$ both have period $N/2$ while $F$ has period $N$. This formula can be applied recursively so that $F^e$ and $F^o$ are each in turn calculated from two DFTs of size $N/4$. Assuming the original $N$ was a power of two this process can be repeated all the way down to DFTs of single points, which are just identity operations (i.e. $F_b=f_a$ for a single point).

It turns out that rather than keeping track of successive divisions into even and odd points, the data in the original array can be rearranged in such a way that $F^e$ and $F^o$ are always sequential. In other words once the array has been rearranged in this way the DL formula can be used to combine the first two elements into an $N=2$ DFT, and then combine that DFT with the succeeding $N=2$ DFT into an $N=4$ DFT, and so on. The way to rearrange the array to accomplish this is to arrange it in bit-reverse order. In other words if $N=4$ then the four elements of your original array are $f_{00}$, $f_{01}$, $f_{10}$, and $f_{11}$. To bit-reverse this array you would swap the middle two elements, leaving the first and last where they are. With some work you should be able to convince yourself that bit-reversal is equivalent to pulling out successive arrays of even and odd points. Otherwise you can take my word for it because I'm not going to prove it to you here.

The following sections describe each of the four FFTEASY functions. Note that all of the functions take as input an array of floats but immediately typecast it as an array of complex numbers, each consisting of two floats representing real and complex parts. So any time I refer to the $i$th element of an array I mean the $i$th complex element, corresponding to the $2 i$ and $2 i+1$ elements of the actual array of floats. Formulas are given here in terms of complex numbers and then implemented in the functions explicitly in terms of real and imaginary parts.



Subsections
next up previous
Next: FFTC1: One-Dimensional Complex Fourier Up: FFTEASY C Routines for Previous: Output of Fourier Transforms

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