Lesson 21

Fast Fourier Transform

The work of Cooley and Tukey showed how to calculate the DFT with complexity (called the Fast Fourier Transform) instead of complexity using the direct algorithm. The fft command that you use in MATLAB implements a Fast Fourier Transform.

Examine: There are approximately complex multiplications and additions required to implement this ( for each value of ).

If , then , a very large number!

However, the FFT would only require about 5000, a substantial savings in complexity (the actual calculation is ).

There are a number of different FFT algorithms that exist including decimation-in-time and decimation-in-frequency.

The primary idea is to split up the size- DFT into DFTs of length 2 each.

You split the sum into 2 subsequences of length and continue all the way down until you have subsequences of length 2.

First break into even and odd subsequences: Now let for even numbers and for odd numbers:    and are both the DFT of a point sequence. is often referred to as the twiddle factor.''

Now break up the size subsequences in half by letting : The first subsequence here is the terms and the second is Also, we have that:   So we get, and:   This was a problem I had on a DSP final exam in 1984:

Express the DFT of the 9-point sequence in terms of the DFTs of 3-point sequences and  