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

Mail: