MATH 465, FAST FOURIER TRANSFORM

JIM MORROW

Fast Fourier Transform

There are several ways to write an FFT. Here is an alternate to the ones in the book and in Henrici’s paper. Let m be an integer and let N = 2^{m}. Suppose that x = [x_{0}, …, x_{N−1}] is an N dimensional complex vector. Let ω = exp(\frac{−2πi}{N}). Then the DFT, c = F_{N}(x) is given by

c_{k} = \frac{1}{N} ∑_{j=0}^{j=N−1} x_{j}ω^{jk}. (1)

Let n = N/2 and let u and v be n dimensional vectors defined by

(2)  u_{j} = x_{j} + x_{j+n}, j = 0, …, n − 1
(3)  v_{j} = (x_{j} − x_{j+n})ω^{j}, j = 0, …, n − 1.

Then

c_{2j} = \frac{1}{2}(F_{n}(u))_{j}, j = 0, …, n − 1 (4)

c_{2j+1} = \frac{1}{2}(F_{n}(v))_{j}, j = 0, …, n − 1. (5)

There are various ways to exploit this version of the algorithm. A program can be written to use this version directly. Alternatively, a recursive program can be written. The recursive program is the easiest to read. In case you didn’t know it, Matlab supports recursion. It is hard to tell this from the manual as it is not mentioned. So it is an undocumented feature of Matlab. I will give you programs based on this way of writing the FFT when you hand in your program. (I will update this file in my homepage.)