Reliable Software Logo
Home >Science  >  FFT: Digital Fourier Transform

Digital Fourier Transform

Exponential Basis

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,ek, k = 0...3, which are sampled exponentials of increasing frequencies.

ek = (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:

e0 = (1, 1, 1, 1)
e1 = (1, e-2πi/4, e-2πi2/4, e-2πi3/4)
e2 = (1, e-2πi2/4, e-2πi4/4, e-2πi6/4)
e3 = (1, e-2πi3/4, e-2πi6/4, e-2πi9/4)

As an example, the real part of e3 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 (e0) = (1, 1, 1, 1) Im (e0) = (0, 0, 0, 0)
Re (e1) = (1, 0, -1, 0) Im (e1) = (0, -1, 0, 1)
Re (e2) = (1, -1, 1, -1) Im (e2) = (0, 0, 0, 0)
Re (e3) = (1, 0, -1, 0) Im (e3) = (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.

Real part of basis vectors

Fig. The real part of the four basis vectors


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, WN,

WN = e-2πi/N

For instance, for N=4 we have

ek = (W4k*0, W4k*1, W4k*2, W4k*3)

Check this out for yourself:

e-2πik*2/4=(e-2πi/4)k*2 =W4k*2

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

ek[n] = WNkn,   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 Wkn v[n]

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

Properties of the Digital Fourier Transform

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 ImageNext: FFT