EE 329: Laboratory 2
The DFT and FFT Algorithms

The Fast Fourier Transform (FFT) is one of the most important tools in digital signal processing. The FFT is a general name for a class of algorithms that efficiently compute the discrete Fourier transform (DFT). Today in lab you will write Matlab programs to compute the DFT based on the definition. Then you will compare the execution time of your program with that of the built-in FFT function in Matlab. We will also record some signals with the dSPACE box and analyze them with Matlab.

No written lab reports are required for Labs 1 and 2. Please work on the following during today's lab session.

1. Begin by demonstrating your work from Lab 1. Use your Simulink programs to demonstrate the sampling theorem and the effects of a digital filter. Also demonstrate the C programs that perform averaging and differencing. What does speech sound like through the differencing filter? If you would like more practice with Simulink, you might implement the averaging and differencing algorithms in Simulink.

2. Please write a Matlab function that will compute the DFT of a data set with arbitrary length N. You might begin by writing out the DFT computations on paper for N=4. You might name the file my_dft1.m. Approximately how many multiplication and addition operations are required to compute the DFT coefficients? Generate data vectors with N=128, 256, 512, and 1024. Compare the run time using your function and the Matlab fft function. You might use the etime function to measure run time. Is there a significant difference in run time between your DFT algorithm and the FFT algorithm? Is there any difference in the transform coefficients produced by each?

3. Explain how the DFT computation can be expressed as a matrix-vector multiplication. Then the dftmtx command in Matlab can be used to easily compute the DFT (with no for loops!). Check how the run time of the DFT computation based on dftmtx compares with those in the previous item.

4. Use the trace31 to record sampled data with the dSPACE box and store the data on the Sun computers. This can be done using either your Simulink diagram or your C program. To use a Simulink diagram, simply type trace31 at a UNIX prompt, and then load the proper .trc file. You may be able to sample faster with a C program, but you need to create your own .trc file. I will provide the proper format, if you need it.

5. Try recording a "chirp" signal and analyze it in Matlab with the fft command. Plot the amplitude spectrum versus frequency in hertz. Does the fft look as you would expect?

6. A better way to analyze the data is the spectrogram. If your data is stored in the variable y, then the spectrogram can be displayed with the Matlab command:

   specgram(y, 512, Fs, [], []);

   where Fs is the sampling rate. Interpret the spectrogram.