As I explained earlier, the Fourier basis consists of sampled sine and cosine functions. Using complex numbers, these two can be combined into a single exponential, so the complex Fourier basis consists of sampled complex exponentials.

Let's start with a somewhat trivial example of a 4-point Fourier transform. We'll need 4 basis vectors,**e**_{k}, k = 0...3, which are sampled exponentials of increasing frequencies.

**e**_{k} =
(e^{-2πi(0*k)/4}, e^{-2πi(1*k)/4}, e^{-2πi(2*k)/4}, e^{-2πi(3*k)/4})

These are four samples of the exponential e^{-2πitk/4} taken at t = 0, 1, 2, 3.

Here are all four of them:

**e**_{0} = (1, 1, 1, 1)

**e**_{1} = (1, e^{-2πi/4}, e^{-2πi2/4}, e^{-2πi3/4})

**e**_{2} = (1, e^{-2πi2/4}, e^{-2πi4/4}, e^{-2πi6/4})

**e**_{3} = (1, e^{-2πi3/4}, e^{-2πi6/4}, e^{-2πi9/4})

As an example, the real part of **e**_{3} is

(1, cos(-2π3/4), cos(-2π6/4), cos(-2π9/4)

which is a sampled cosine function. In fact, using simple trigonometric identities, like cos(π/2) = 0, etc., one can simplify the real and imaginary parts to:

Re (e_{0}) = (1, 1, 1, 1) |
Im (e_{0}) = (0, 0, 0, 0) |

Re (e_{1}) = (1, 0, -1, 0) |
Im (e_{1}) = (0, -1, 0, 1) |

Re (e_{2}) = (1, -1, 1, -1) |
Im (e_{2}) = (0, 0, 0, 0) |

Re (e_{3}) = (1, 0, -1, 0) |
Im (e_{3}) = (0, 1, 0, -1) |

Notice that they are *not* all independent, in fact there can only be 4 independent basis vectors in 4-d. (The original complex exponentials, however, are independent in a 4-d *complex* space. They could be used to Fourier transform a complex sequence. It just so happens that all our samples have zero imaginary parts.)

Below is a picture of the real parts of the basis vectors, overlapped with the appropriate trigonometric functions whose samples they form.

The fact that these vectors are so regular is the basis of the FFT algorithm. But before we get to that, let's introduce some convenient notation. All our basis vectors in N-dimensions can be expressed in terms of various *powers* of one number, W_{N},

W_{N} = e^{-2πi/N}

For instance, for N=4 we have

**e**_{k} = (W_{4}^{k*0},
W_{4}^{k*1},
W_{4}^{k*2},
W_{4}^{k*3})

Check this out for yourself:

e^{-2πik*2/4}=(e^{-2πi/4})^{k*2} =W_{4}^{k*2}

So this is the final form of our N-point Fourier basis

e_{k}[n] = W_{N}^{kn}, n = 0, 1, ... N-1

and the kth component of the DFT of the buffer v[n] is the scalar product of the kth basis vector with our vector of samples:

V[k] = Σ_{n=0...N-1} W^{kn} v[n]

(the summation is from n=0 to N-1).

What can you do with the Fourier transform? You can display it graphically. Or you can modify it and then reverse-transform it. You may, for instance, cut off higher (or lower) frequencies. Or you can remove a particular frequency that is polluting your signal. This is called *filtering* the signal.

The reverse of the digital Fourier transform (DFT)is calculated simply by applying the Fourier transform again, and reversing the resulting buffer (to be precise, because of our normalization, you should also divide the resulting samples by N). By reversing I mean reading the buffer from back to front.

The components of the DFT are complex numbers. They have a modulus and a phase:

- The
*modulus*of V[k], sqrt (V[k]*V^{*}[k]), describes the intensity of the particular frequency corresponding to k (more precisely, because of our normalization, you should divide the modulus by sqrt(N)) - The
*phase*of a given component describes the phase shift of this component--at what angle it starts its oscillations

In most cases, the phase is of no relevance--our ears cannot detect it. However, if you have a stereo pair of sources, your ears can detect the phase difference between them. So if you do some signal processing involving multiple channels, you have to take the phases into account.

What is the relation between k--the index of the Fourier component--and its frequency? Here is the function describing the k-th basis vector, e^{-2πikt/N}. We sample it at t = 0, 1, 2,...,N-1. Let's just look at its real part, cos(2πkt/N) (cosine is symmetric, so the sign of its argument doesn't matter). Cosine starts repeating itself after 2π, which corresponds to kt/N = 1 or t = N/k. So how many such repetitions fit in a segment of length N? Exactly k. In other words, our k-th basis vector has k periods per buffer. But what time interval corresponds to one buffer? That depends on the sampling speed. If *sps* is the number of samples per second, then sps/N is the number of buffers per second. Therefore k * sps / N is the number of periods per second, or the frequency.

Next: FFT