Spring, 1997

Programming the FFT Algorithm with Matlab

We will continue our discussion from class today and begin working
on a Matlab implementation of the FFT algorithm.
We will return to more FFT applications and the spectrogram
next week.
Our goal is for each student to write a *decimation in time*
FFT algorithm in Matlab.
Your algorithm should work for a data sequence of any length N
that is a power of 2.
Useful references are the notes from class, and
section 2.5 and the appendix to chapter 2 in the textbook.
A good way to begin might be to write the butterfly diagrams for
N=8 and N=16. You may want to code these special cases in Matlab
before you generalize to larger N values.

Please submit the following by Friday, February 14. Please send your Matlab programs by email.

- A Matlab function
`my_dft1`that computes the DFT directly from the definition for any value of N. (Please ask me if you have questions about creating functions in Matlab.) - A Matlab function
`my_dft2`that computes the DFT using matrix-vector multiplication and the`dftmtx`command. - A Matlab function
`my_fft`that is your implementation of the decimation in time FFT algorithm for values of N that are a power of 2. Include an explanation of how your algorithm works. You will probably need to do the explanation*first*in order to properly code the FFT algorithm. - Compare the run time of your FFT algorithm with
the built-in
`fft`function in Matlab. How do they compare for various values of N that are powers of 2?

Thank you.