EE 329: Laboratory 3
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.

1. 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.)

2. A Matlab function my_dft2 that computes the DFT using matrix-vector multiplication and the dftmtx command.

3. 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.

4. 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.