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

We start with: