The Fourier Transform provides the means of transforming a signal defined in the time domain into one defined in the frequency domain (see Tutorial 2 on time and frequency representation). When a function is evaluated by numerical procedures, it is always necessary to sample it in some fashion (refer to Tutorial 3 on Sampling and Aliasing). This means that in order to fully evaluate a Fourier transform with digital operations, it is necessary that the time and frequency functions be sampled in some form or another. Thus the digital or Discrete Fourier Transform (DFT) is of primary interest.
The Fourier transform is used to transform a continuous time signal into the frequency domain. It describes the continuous spectrum of a nonperiodic time signal. The Fourier transform X(f) of a continuous time function x(t) can be expressed as
The inverse transform is
This is used in the case where both the time and the frequency variables are discrete (which they are if digital computers are being used to perform the analysis). Let x(nT) represent the discrete time signal, and let X(mF) represent the discrete frequency transform function. The Discrete Fourier Transform (DFT) is given by
where
The fast Fourier transform (FFT) is simply a class of special algorithms which implement the discrete Fourier transform with considerable savings in computational time. It must be pointed out that the FFT is not a different transform from the DFT, but rather just a means of computing the DFT with a considerable reduction in the number of calculations required.
Since this tutorial is intended as an introduction to the Fourier transform, a rigourous development of the underlying theory of the FFT will not be attempted here.
While it is possible to develop FFT algorithms that work with any number of points, maximum efficiency of computation is obtained by constraining the number of time points to be an integer power of two, e.g. 1024 or 2048.
The approximations involved when using the DFT in the analysis of continuous time systems must be carefully understood. There are problems that arise in the process that may lead to erroneous results unless proper precautions are taken.
While the mathematical properties of the DFT are exact, the DFT is seldom of interest as the end goal. It is usually employed to transform data which may arise from either an actual continuous time process or perhaps a discrete time process which is being analysed from a continuous time system approach. The DFT is usually used to approximate the Fourier transform of a continuous time process, and it is necessary to understand some of the limitations inherent in this approach.
There are three possible phenomena that result in errors between the computed and the desired transform. These three phenomena are (a) aliasing, (b) leakage, and (c) the picket-fence effect.
(a) Aliasing. The phenomenon of aliasing is discussed in Tutorial 3 . The only solution to the aliasing problem is to ensure that the sampling rate is high enough to avoid any spectral overlap, or to use an anti-aliasing filter as discussed in Tutorial 5 .
(b) Leakage. This problem arises because of the practical requirement that we must limit observation of the signal to a finite interval. The process of terminating the signal after a finite number of terms is equivalent to multiplying the signal by a window function. The net effect is a distortion of the spectrum. There is a spreading or leakage of the spectral components away from the correct frequency, resulting in an undesirable modification of the total spectrum.
The leakage effect cannot always be isolated from the aliasing effect because leakage may also lead to aliasing. Since leakage results in a spreading of the spectrum, the upper frequency may move beyond the Nyquist frequency (refer to Tutorial 3 ), and aliasing may then result. The best approach for alleviating the leakage effect is to choose a suitable window function that minimises the spreading.
(c) Picket-Fence Effect. This effect is produced by the inability of the DFT to observe the spectrum as a continuous function, since computation of the spectrum is limited to integer multiples of the fundamental frequency F (reciprocal of the sample length). Observation of the spectrum with the DFT is analogous to looking at it through a sort of "picket-fence," since we can observe the exact behavior only at discete points. The major peak of a particular component could lie between two of the discrete transform lines, and the peak of this component might not be detected without some addition processing.
One procedure for reducing the picket-fence effect is to vary the number of points in a time period by adding zeros at the end of the original record, while maintaining the original record intact. This process artificially changes the period, which in turn changes the locations of the spectral lines without altering the continuous form of the original spectrum. In this manner, spectral components originally hidden from view can be shifted to points where they can be observed.
To summarise this section, the DFT algorithm can be used to approximate the transform of a continuous time function, subject to the following limitations and difficulties.
