Spring, 1997

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.

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