Table of Contents

..Introduction
..The Fourier Transform
..The Two Domains
..Fourier Transform Properties

..Scaling Property
..Shifting Property
..Convolution Theorem
..Correlation Theorem

..Parseval's Theorem
..Sampling Theorem
..Aliasing
..Discrete Fourier Transform (DFT)
..Fast Fourier Transform (FFT)
..Summary
..References

Introduction

The Fourier Transform

F(s) = f(x) exp(-i 2xs) dx.

Applying the same transform to F(s) gives

f(w) = F(s) exp(-i 2ws) ds.

If f(x) is an even function of x, that is f(x) = f(-x), then f(w) = f(x). If f(x) is an odd function of x, that is f(x) = -f(-x), then f(w) = f(-x). When f(x) is neither even nor odd, it can often be split into even or odd parts.

To avoid confusion, it is customary to write the Fourier transform and its inverse so that they exhibit reversibility:

F(s) = f(x) exp(-i 2xs) dx

f(x) = F(s) exp(i 2xs) ds

so that

f(x) = f(x) exp(-i 2xs) dx exp(i 2xs) ds

as long as the integral exists and any discontinuities, usually represented by multiple integrals of the form ½[f(x+) + f(x-)], are finite. The transform quantity F(s) is often represented as and the Fourier transform is often represented by the operator (Bracewell, 6-8).

There are functions for which the Fourier transform does not exist; however, most physical functions have a Fourier transform, especially if the transform represents a physical quantity. Other functions can be treated with Fourier theory as limiting cases. Many of the common theoretical functions are actually limiting cases in Fourier theory.

Usually functions or waveforms can be split into even and odd parts as follows

f(x) = E(x) + O(x)

where

E(x) = ½ [f(x) + f(-x)]

O(x) = ½ [f(x) - f(-x)]

and E(x), O(x) are, in general, complex. In this representation, the Fourier transform of f(x) reduces to

2E(x) cos(2xs) dx - 2iO(x) sin(2xs) dx

It follows then that an even function has an even transform and that an odd function has an odd transform. Additional symmetry properties are shown in Table 1 (Bracewell, 14).

Table 1: Symmetry Properties of the Fourier Transform

    function                        transform
-----------------------------------------------------------
real and even                   real and even
real and odd                    imaginary and odd
imaginary and even              imaginary and even
complex and even                complex and even
complex and odd                 complex and odd
real and asymmetrical           complex and asymmetrical
imaginary and asymmetrical      complex and asymmetrical
real even plus imaginary odd    real
real odd plus imaginary even    imaginary
even                            even
odd                             odd

The cosine transform of a function f(x) is defined as

F_c(s) = 2f(x) cos 2sx dx.

This is equivalent to the Fourier transform if f(x) is an even function. In general, the even part of the Fourier transform of f(x) is the cosine transform of the even part of f(x). The cosine transform has a reverse transform given by

f(x) = 2F_c(s) cos 2sx ds.

Likewise, the sine transform of f(x) is defined by

F_S(s) = 2f(x) sin 2sx dx.

As a result, i times the odd part of the Fourier transform of f(x) is the sine transform of the odd part of f(x).

Combining the sine and cosine transforms of the even and odd parts of f(x) leads to the Fourier transform of the whole of f(x):

f(x) = _CE(x) - i _SO(x)

where , _C, and _S stand for -i times the Fourier transform, the cosine transform, and the sine transform respectively, or

F(s) = ½F_C(s) - ½iF_S(s)

(Bracewell, 17-18).

Since the Fourier transform F(s) is a frequency domain representation of a function f(x), the s characterizes the frequency of the decomposed cosinusoids and sinusoids and is equal to the number of cycles per unit of x (Bracewell, 18-21). If a function or waveform is not periodic, then the Fourier transform of the function will be a continuous function of frequency (Brigham, 4).

The Two Domains

It is often useful to think of functions and their transforms as occupying two domains. These domains are referred to as the upper and the lower domains in older texts, ``as if functions circulated at ground level and their transforms in the underworld'' (Bracewell, 135). They are also referred to as the function and transform domains, but in most physics applications they are called the time and frequency domains respectively. Operations performed in one domain have corresponding operations in the other. For example, as will be shown below, the convolution operation in the time domain becomes a multiplication operation in the frequency domain, that is, f(x) g(x) F(s) G(s). The reverse is also true, F(s) G(s) f(x) g(x). Such theorems allow one to move between domains so that operations can be performed where they are easiest or most advantageous.

Fourier Transform Properties

Scaling Property

If {f(x)} = F(s) and a is a real, nonzero constant, then

{f(ax)} = f(ax) exp(i 2sx) dx

= |a|^-1 f() exp(i 2s/a) d

= |a|^-1 F(s/a).

From this, the time scaling property, it is evident that if the width of a function is decreased while its height is kept constant, then its Fourier transform becomes wider and shorter. If its width is increased, its transform becomes narrower and taller.

A similar frequency scaling property is given by

{|a|^-1 f(x/a)} = F(as).

Shifting Property

If {f(x)} = F(s) and x₀ is a real constant, then

{f(x - x₀)} = f(x - x₀) exp(i 2sx) dx

= f() exp(i 2s ( + x₀)) d

= exp(i 2x₀s) f() exp(i 2s) d

= F(s) exp(i 2x₀s).

This time shifting property states that the Fourier transform of a shifted function is just the transform of the unshifted function multiplied by an exponential factor having a linear phase.

Likewise, the frequency shifting property states that if F(s) is shifted by a constant s₀, its inverse transform is multiplied by exp(i 2xs₀)

{f(x) exp(i 2xs₀)} = F(s-s₀).

Convolution Theorem

We now derive the aforementioned time convolution theorem. Suppose that g(x) = f(x) h(x). Then, given that {g(x)} = G(s), {f(x)} = F(s), and {h(x)} = H(s),

G(s) = {f(x) h(x)}

= { f() h(x - ) d }

= [ f() h(x - ) d ] exp(-i 2sx) dx

= f() [ h(x - ) exp(-i 2sx) dx ] d

= H(s) f() exp(-i 2s) d

= F(s) H(s).

This extremely powerful result demonstrates that the Fourier transform of a convolution is simply given by the product of the individual transforms, that is

{f(x) h(x)} = F(s) H(s).

Using a similar derivation, it can be shown that the Fourier transform of a product is given by the convolution of the individual transforms, that is

{f(x) h(x)} = F(s) H(s)

This is the statement of the frequency convolution theorem (Gaskill, 194-197; Brigham, 60-65).

Correlation Theorem

h(x) = f(u) g(x+u) du

and like the convolution integral, it forms a Fourier transform pair given by

{h(x)} = F(s) G*(s).

This is the statement of the correlation theorem. If f(x) and g(x) are the same function, the integral above is normally called the autocorrelation function, and the crosscorrelation if they differ (Brigham, 65-69). The Fourier transform pair for the autocorrelation is simply

f(u) f(x+u) du = |F |².

Parseval's Theorem

h²(t) dt = |H(f) |² df

(Brigham, 23). The power spectrum, P(f), is given by

P(f) = |H(f) |², f .

Sampling Theorem

A bandlimited signal is a signal, f(t), which has no spectral components beyond a frequency B Hz; that is, F(s) = 0 for |s| > 2B. The sampling theorem states that a real signal, f(t), which is bandlimited to B Hz can be reconstructed without error from samples taken uniformly at a rate R > 2B samples per second. This minimum sampling frequency, _s = 2B Hz, is called the Nyquist rate or the Nyquist frequency. The corresponding sampling interval, T = 1/2B (where t = nT), is called the Nyquist interval. A signal bandlimited to B Hz which is sampled at less than the Nyquist frequency of 2B, i.e., which was sampled at an interval T > 1/2B, is said to be undersampled.

Aliasing

Figure 1: Undersampled, oversampled, and critically-sampled unit area gaussian curves.

As an example, Figure 1 shows a unit gaussian curve sampled at three different rates. The FFT (or Fast Fourier Transform) of the undersampled gaussian appears flattened and its tails do not reach zero. This is a result of aliasing. Additional spectral components have been folded back onto the ends of the spectrum or added to the edges to produce this curve.

The FFT of the oversampled gaussian reaches zero very quickly. Much of its spectrum is zero and is not needed to reconstruct the original gaussian.

Finally, the FFT of the critically-sampled gaussian has tails which reach zero at their ends. The data in the spectrum of the critically-sampled gaussian is just sufficient to reconstruct the original. This gaussian was sampled at the Nyquist frequency.

Figure 1 was generated using IDL with the following code:

  !P.Multi=[0,3,2]
  a=gauss(256,2.0,2) ; undersampled
  fa=fft(a,-1)
  b=gauss(256,2.0,0.1) ; oversampled
  fb=fft(b,-1)
  c=gauss(256,2.0,0.8) ; critically sampled
  fc=fft(c,-1)
  plot,a,title='!6Undersampled Gaussian'
  plot,b,title='!6Oversampled Gaussian'
  plot,c,title='!6Critically-Sampled Gaussian'
  plot,shift(abs(fa),128),title='!6FFT of Undersampled Gaussian'
  plot,shift(abs(fb),128),title='!6FFT of Oversampled Gaussian'
  plot,shift(abs(fc),128),title='!6FFT of Critically-Sampled Gaussian'

  function gauss,dim,fwhm,interval
  ;
  ; gauss - produce a normalized gaussian curve centered in dim data
  ;         points with a full width at half maximum of fwhm sampled
  ;         with a periodicity of interval
  ;
  ; dim      = the number of points
  ; fwhm     = full width half max of gaussian
  ; interval = sampling interval
  ;
  center=dim/2.0 ; automatically center gaussian in dim points
  x=findgen(dim)-center
  sigma=fwhm/sqrt(8.0 * alog(2.0))  ; fwhm is in data points
  coeff=1.0 / ( sqrt(2.0*!Pi) * (sigma/interval) )
  data=coeff * exp( -(interval * x)^2.0 / (2.0*sigma^2.0) )
  return,data
  end

Discrete Fourier Transform (DFT)

f_k = T f(kT) = T₀N₀^-1 f(kT)

and

F_r = F(rs₀)

where

s₀ = 2 ₀ = 2 T₀^-1.

The discrete Fourier transform (DFT) is defined as

F_r = f_k exp(-i r₀k)

where ₀ = 2 N₀^-1. Its inverse is

f_k = N₀^-1 F_r exp(i r₀k).

These equations can be used to compute transforms and inverse transforms of appropriately-sampled data. Proofs of these relationships are in Lathi (546-548).

Fast Fourier Transform (FFT)

Summary

References

Bracewell, Ron N., 1965, The Fourier Transform and Its Applications, New York: McGraw-Hill Book Company, 381 pp.

Brault, J. W. and White, O. R., 1971, The analysis and restoration of astronomical data via the fast Fourier transform, Astron. & Astrophys., 13, pp. 169-189.

Brigham, E. Oren, 1988, The Fast Fourier Transform and Its Applications, Englewood Cliffs, NJ: Prentice-Hall, Inc., 448 pp.

Cooley, J. W. and Tukey, J. W., 1965, An algorithm for the machine calculation of complex Fourier series, Mathematics of Computation, 19, 90, pp. 297-301.

Gabel, Robert A. and Roberts, Richard A., 1973, Signals and Linear Systems, New York: John Wiley & Sons, 415 pp.

Gaskill, Jack D., 1978, Linear Systems, Fourier Transforms, and Optics, New York: John Wiley & Sons, 554 pp.

Lathi, B. P., 1992, Linear Systems and Signals, Carmichael, Calif: Berkeley-Cambridge Press, 656 pp.

Information supplied by http://www.math2.org