You may not choose the Fast Fourier Transform for Lab 7.
The Fast Fourier Transform is an important algorithm in digital signal processing. It provides a fast way to convert between the time domain and frequency domain representations of a sequence of sound samples (or other types of data). Time domain represents sound as a series of values changing over time (like the graph in the digital audio handout). Frequency domain represents sound as the sum of sine and cosine waves of different amplitudes, frequencies, and phases. For example, the graph in the digital audio handout could be represented by giving a single sine wave with amplitude 1000 and frequency 440 Hz. To learn more, see The Scientist and Engineer's Guide to Digital Signal Processing (or take EECS 216 and EECS 451).
For your educational toy, the FFT can help you find or modify the frequency components of sound segments.
It is possible to compute an FFT in software on the E100. However, the E100 can not run the FFT algorithm fast enough to keep up with the audio sampling rate, so we provide a co-processor that computes an FFT in hardware. This section describes how to use the FFT co-processor.
To use the FFT co-processor, an E100 program sends a sequence of up to 1024 data points to the FFT co-processor, which then computes the FFT of that sequence. Later, the E100 program reads the result of the FFT, which is a sequence of 1024 data points.
Each data point in a sequence consists of a real and imaginary component. Each component is limited to the range [-215, 215-1]. For time-domain data, the real component represents the magnitude of a sound sample, and the imaginary component is not used. For frequency-domain data, the real and imaginary components represent a frequency component in the complex plane. The magnitude of this frequency component is square_root(real*real + imaginary*imaginary). The phase of this frequency component is arctangent(imaginary/real).
When sending or receiving time-domain data, data points are given in order of increasing time.
When sending or receiving frequency-domain data, data points are given in increasing order of frequency. Point #0 is for frequency 0 Hz, and each succeeding point is for a frequency that is 7.8125 Hz more than the last point, up until point #512 (the 513th point), which is for frequency 4000 Hz (the Nyquist frequency for our audio rate). After point #512, the frequencies goes down by 7.8125 Hz between points; each of these points are the complex conjugates of the corresponding point in the first 512 samples. [This description assumes that sequences represent samples taken at the standard audio rate of 8 KHz. More generally, the frequency gap between points is the sampling frequency divided by the number of samples.]
fft_send_command and fft_send_response implement the standard I/O protocol. The command parameters are fft_send_real, fft_send_imaginary, fft_send_inverse, and fft_send_end. There are no response parameters.
fft_send_real, fft_send_imaginary specify the real and imaginary components of a data point. Remember that the range of these components is [-215, 215-1] (note that differs from the [-231, 231-1] range of the speaker and microphone).
fft_send_inverse specifies the direction of the transform and is used only on the first data point in a sequence (it is ignored on other points in the sequence). fft_send_inverse=0 specifies a forward transform (time domain -> frequency domain); fft_send_inverse=1 specifies an inverse transform (frequency domain -> time domain).
fft_send_end specifies whether this data point is the last point in the sequence. If the E100 program ends a sequence before sending 1024 points (by setting fft_send_end=1), the FFT co-processor will assume the remaining data points are (0, 0). The FFT co-processor will automatically end the sequence after the E100 sends 1024 points.
After sending a sequence of data points to be transformed, the E100 program can read the results (another sequence of data points) from the FFT controller. fft_receive_command and fft_receive_response implement the standard I/O protocol. There are no command parameters. The response parameters are fft_receive_real and fft_receive_imaginary, which specify the real and imaginary components of a data point.
If the E100 program starts sending a new sequence of points to the FFT controller, the controller will flush all remaining points in the result sequence.
ase100 simulates the FFT co-processor accurately enough for you to test your device driver and to run assembly-language programs. The exact results returned by ase100's simulated FFT co-processor may differ slightly from those returned by the DE2-115's FFT co-processor.
The FFT co-processor on the DE2-115 uses a time-limited module that is intended for lab use (not for final deployment). If the DE2-115 board is disconnected from USB-Blaster, the FFT co-processor will only work for 1 hour. If the DE2-115 board is connected to a computer via USB-Blaster, the FFT co-processor will work indefinitely.