The Discrete Fourier Transform

In order to create an approximation of the Fourier transform for discrete, sampled data, we must make two major steps:

• Move from limits of +/- infinity to limits of the amount of sampled data;
• Move from a continuous integral to a discrete summation.

The first step we can overcome by assuming the function is periodic outside the range which we are considering. Therefore, ω₀ = 2π/T. Since a periodic function only has harmonics that are multiples of ω₀, we can also say that ω = mω₀ = 2πm/T, where m is integral.

The second is a fairly simple thing to achieve: we can make the approximation that the space between the time elements, T_s, is small, and so convert the integral into a summation. Now, t = nT_s , and the period T is NT, where N is the number of samples:

We can now simplify and say that X is a discrete function of m, and x a discrete function of n:

This equation gives the discrete Fourier transform of the group of samples x[0..N-1]. Nyquist's sampling theorem dictates that there are N values in the discrete transform: [0..N-1].

A similar derivation leads to the inverse DFT:

which is very similar.

In the next section, we are going to talk about a more efficient method of doing this - the fast Fourier transform (FFT).