MA332 lecture notes, Fall 1998
Week 12 Tuesday

Topics: interpretation of DFTs
        fast Fourier transform (fft)

Interpretation of DFTs

1) why isn't the DFT of the sinusoid a perfect spike?

2) when we take the DFT of two sinusoids, why aren't
   they the same height

3) what's the deal with the indices of the H_n and the
   frequencies

4) What happens when we exceed the critical frequency?

5) What happens when f1 = 0.1 and f2 = 0.9?

   What is noise?  What does randomness sound like?

6) What do we expect when f1 = 0.1 and f2 = 1.1?


Fast Fourier Transform
----------------------

Thinking recursively.

1) decompose big problem into smaller problem(s)

2) use some other method to solve the smaller problem

3) stitch the small solutions into a big one


In this case, to perform a semi-FFT, we can

1) divide the signal into even and odd samples

2) use the DFT procedure to find the DFT of each half

3) stitch the results together.


Then we take the semi-FFT and encapsulate it in a procedure
called FFT.

What happens in step 2 if instead of calling DFT, we
call FFT, the procedure we are in the process of writing?

     (Infinite recursion)

We need a base case to tell us when to stop...

   The DFT of a single value is just the value itself.

     1 N problem becomes
     2 N/2 problems becomes
     4 N/4 problems becomes
     8 N/8 problems, etc.

     until N/something = 1, at which point H=h.

Splitting things up takes O(n) work at each level.

Stitching things back up takes O(n) work at every level,
and there are logN levels, so the total work is O(NlogN),
which is way better than N^2!