**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
[-2 ^{15}, 2^{15}-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

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 [-2^{15}, 2^{15}-1] (note that differs from
the [-2^{31}, 2^{31}-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.