Background

It is the digital age. Just about every video, audio and written data is stored, processed and replayed using digital technologies. No matter what the source, the information can be represented as a vector, typically finite dimensional. Once we have the data we often want to manipulate it, e.g. increase the bass in an audio file, sharpen an image, remove the fuzziness from some data. The main tool for such manipulations is the Fast Fourier Transform (FFT). This lab is about building some intuition about the Fourier Transform.

Math Stuff

Start with a vector v which we'll assume represents a sound wave from a vibrating string. From studying the wave equation which models sound transmission, we know that v is built from various tones, each of which corresponds to a function of the form sin(kx) for some k. Try this:

x = 2*pi*[0:100]/100;   % create equally spaced points from 0 to 2pi
v = sin(x) + 2*sin(2*x) - 0.2*sin(3*x) + 0.4*sin(4*x);
plot(x,v)

In general we have that v = a(1)*sin(x) + a(2)*sin(2*x) + ... + a(n)*sin(n*x) for some set of (Fourier) coefficients a(i).

To manipulate this signal, we manipulate the coefficients. For example, if you want to increase the bass, you increase a(i) for low values of i. To increase the treble, you increase for high values of i. To clean up high-frequency hiss, you might just set all value of a(i) for high i to 0.
To manipulate the coefficients you have to be able to determine them from a signal. This is where the Fourier Transform comes into play. Rather than tell you how it works, we'll work through it in the exercises.

Exercises

Let x be a vector of equally space points as in the example above and let s1 = sin(x), s2 = sin(2*x), s3 = sin(3*x), ..., s7 = sin(7*x).

1. Compute dot products of 5 different pairs of vectors, via dot(s1,s2) etc. (Consider any small value as 0). What can you say about the vectors (s1, s2, ..., s7)? Remember if dot(u,v)=0 then the vectors are orthogonal.

2. Compute the dot product of each vector with itself, i.e. dot(s1,s1) etc. What pattern do you see?

3. Suppose v = 4*s1 + 2*s2. Compute dot(v,s1)/dot(s1,s1) and dot(v,s2)/dot(s2,s2).

4. Combining what we saw in 1-3, we have the basics of the Fourier (Sine) Transform. If v = a(1)*s1 + a(2)*s2 + ... + a(k)*sk, write out an equation for the coefficient a(i).

5. Now to test it out. Construct and plot a random signal vector as follows:

v = randn(1)*s1 + randn(1)*s2 + randn(1)*s3 + 0.3*[0, randn(1,99), 0];
plot(x,v)

This should produce a noisy signal and we are going to smooth it out. Now, using s1, ..., s7 and the formula you derived in 4, construct the Fourier coefficients a(i), i = 1, ..., 7.

Now construct a new signal from the coefficients and plot it:

w = a(1)*s1 + a(2)*s2 + a(3)*s3 + a(4)*s4 + a(5)*s5 + a(6)*s6 + a(7)*s7;
plot(x,v,x,w,'g')

You should see a much smoother version of the signal.

Answer the questions from the exercises and list the coefficients you computed in #5.