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 by
separately computing two FTs of size . Let be the DFT of a
function
. Then let be the DFT of
the even points and be the DFT of the odd
points . The DL formula then says

(9) |

(10) |

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 and 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 DFT, and then combine that DFT with the succeeding DFT into an 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 then the four elements of your original array are , , , and . 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 th element of an array I mean the th
*complex* element, corresponding to the and 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.

- FFTC1: One-Dimensional Complex Fourier Transforms
- FFTCN: Multi-Dimensional Complex Fourier Transforms
- FFTR1: One-Dimensional Real Fourier Transforms
- FFTRN: Multi-Dimensional Real 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