§ III. The Fourier Transform and
Discrete Fourier Transform

Fourier series work very well to analyze periodic phenomena. The series work quite well with control and timing signals. However, many signals and functions are not periodic. Typically, a signal changes over time and is nondeterministic. We take an approach that develops a period of length infinity in this section as follows. Choose T>0. Restrict our function f to the interval [-T, T]. Now look at what happens to f 's Fourier series as we let T go to infinity. The resulting expression will be the Fourier transform.

3.1 The Fourier Transform

Suppose f is not periodic and that f decays quickly enough as t goes to infinity so as to be absolutely integrable; i.e.,


Figure 3.1 An Absolutely Integrable Function

Restrict f to the interval [-T, T] and make f periodic by extension.


Figure 3.2 Periodic Restriction

Now we can find f 's Fourier series over the interval [-T, T]. Write the series in complex form

where cn is given by

Now for the magic. Since f decays quickly, extending the integral to -infinity to +infinity doesn't change the value by very much. Set

Then, the Fourier series becomes
The integral in the coefficient cn,T is a function of zn alone; call it F(zn). Then, we have
which looks very much like a Riemann sum. Treating it as such (which requires some delicate analysis) leads us to the Fourier transform pair:
We have F(z) is the transform of f(x) and f(x) is the inverse transform of F(z). Typically, the transform is complex. The function f is in the time domain, while F is said to be in the frequency (signal) domain or the spectrum (optics) domain.

3.2 Properties of the Fourier Transform

The table below shows elementary properties of the transform.


Table 3.1. Properties of the Fourier Transform
Property Original Transform
Linearity
Time Shift
Frequency Shift
Scaling
Modulation

Look up properties of the transform related to differentiation and integration.

3.3 The Discrete Transform

We rarely know a closed form formula for a signal, but we can easily measure a signal and collect values at discrete times to make a table of data. Again think of the transform as a Riemann sum with the tabulated values used for the signal function f. This analysis leads to the Discrete Fourier transform pair:

Discrete Fourier Transform Algorithm

Given a vector of N points, calculate the DFT.

 DFT(data)
  N := length(data)
  for j = 0..N-1
    begin
    W := exp(2*i*Pi*j/N)
    DFT[j] := 0
    for k = 0..N-1
      begin
      DFT[j] := DFT[j] + Wk*data[k]
      end
    DFT[j] := DFT[j]/N
    end
  return(DFT)

[Maple V R4 version.]

3.4 Main Results

The Sampling Theorem describes whether a function can be adequately sampled for data and, if so, the minimum number of samples required.
Definition Band Limited Signal
A time function f(t) is a Band Limited Signal if the Fourier transform F(z) is zero above the frequency z0; i.e., for all |z| > z0.
Definition Time Limited Signal
A time function f(t) is a Time Limited Signal if the function f(t) is zero past the time t0; i.e., for all |t | > t0.
Theorem Time Sampling Theorem
The Band Limited signal f(t) (limited by z0) can be uniquely determined by N sampled values f(k/z0).
Theorem Frequency Sampling Theorem
The discrete transform F(z) of the Frequency Limited signal f(t) (limited by t0) can be uniquely determined by N sampled values F(k/t0).

Look up the "Uncertainty Principle of Spectral Analysis." Why the term "Uncertainty" ?

3.5 An Example

Find the Fourier and Discrete Fourier Transforms of a decaying signal.

Our function is defined by


Figure 3.3 A Decaying Signal

First, we find the Fourier tranform of f(x).

Now plot the spectrum, |F(z)|, of the transform.


Figure 3.3 A Decaying Signal

What frequencies carry most of f's power ?

For the discrete transform we'll sample at [i/5] for i = -50..50 and then apply DFT to the vector [f(i/5)]. The discrete power spectrum plot follows.


Figure 3.3 A Decaying Signal

[Check these with Maple V R4.]

Exercises

  1. Find the Fourier transform of a pulse of height 1 and width 2 centered at the origin.
  2. Find the Fourier transform of f(x) = sin(x) /x2.
  3. Prove the relations in Table 3.1
  4. Find the Fourier transform of a pulse of height 1 and width 2 centered at the x=a.