The Fast Fourier Transform is an extremely important and widely-used method of extracting useful information from sampled signals. It is quite possible to use the FFT simply as a tool, without needing to understand its theoretical basis; nevertheless, in this section we will attempt to give a brief outline of how the FFT works, without getting too involved in the mathematical aspects.
The Fourier Transform (named after its discoverer, the French mathematician Jean-Baptiste Fourier) is a mathematical procedure which can be thought of as transforming a function from the time domain to the frequency domain. The application of the Fourier transform to a signal is analogous to the splitting up or "dispersion" of a light beam by a prism or diffraction grating to form the optical spectrum of the light source. An optical spectrum consists of lines or bands of colour corresponding to the various wavelengths (and hence different frequencies) of light waves emitted by the source. In Digital Signal Processing, the spectrum of a signal refers to the way energy in the signal is distributed over its various frequency components.
The Fourier transform operates on continuous functions: that is, functions which are defined at all values of the time t. Such a function might, for example, represent a continually-varying analog voltage signal produced by a microphone or other type of transducer.
Digital signal processing involves discrete signals (signals which are sampled at regular intervals of time) rather than continuous signals. A modified form of the Fourier Transform, known as the Discrete Fourier Transform or DFT, is used in the case of sampled (discrete) signals.
When the DFT is applied to a discrete signal, the result is a set of sine and cosine coefficients. When sine and cosine waves of appropriate frequencies are multiplied by these coefficients and then added together, the original signal waveform is exactly reconstructed. The sine and cosine waves are the frequency components of the original signal, in the sense that the signal can be built up from these components. The coefficients determined by the DFT represent the amplitudes of each of these components.
The procedure by which the sine and cosine coefficients are calculated is straightforward in principle, although in practice it requires a great deal of computation. To determine each individual coefficient, every one of the sampled values of the signal must be multiplied by the corresponding sampled value of a sine or cosine wave of the appropriate frequency. These products must then be added together, and the result then divided by the number of samples involved, to give the value of the coefficient.
If the signal consists of a number of samples N, the DFT requires the calculation of N sine and N cosine coefficients. For each coefficient to be determined, N products of samples of the signal and the appropriate sine or cosine wave must be evaluated and summed. The total number of steps in the computation of the DFT is thus N2, each step requiring the evaluation of a sine or cosine function together with a multiplication (and this does not include the calculation of the N products in order to find each coefficient). To compute the DFT of a signal comprising 1000 samples, say, would entail of the order of one million calculations. The DFT is therefore an extremely numerically intensive procedure.
Although the ability of the DFT to provide information about the frequency components of a signal is extremely valuable, the huge computational effort involved meant that until the 1960's it was very rarely used in practical applications. Two important advances have changed the situation completely. The first was the development of the digital computer, with its ability to perform numerical calculations rapidly and accurately; the second was the discovery by Cooley and Tukey of a numerical algorithm which allows the DFT to be evaluated with a significant reduction in the amount of calculation required. This algorithm, called the Fast Fourier Transform, or FFT, allows the Discrete Fourier Transform of a sampled signal to be obtained rapidly and efficiently. Many FFT algorithms have subsequently been devised, based on different approaches; some may offer slight advantages over others in specific applications.
Nowadays, the FFT is used in many areas, from the identification of characteristic mechanical vibration frequencies to image enhancement. Standard routines are available to perform the FFT by computer in programming languages such as Pascal, Fortran and C, and many spreadsheet and other software packages for the analysis of numerical data allow the FFT of a set of data values to be determined readily.
The process of determining the amplitudes of all the frequency components of a signal is referred to as "spectrum analysis". A spectrum analyser is an instrument which displays in graphical form the frequency spectrum of an input signal. Traditionally, such instruments were based on analog electronic circuits in which the input signal was effectively multiplied by a sine wave signal whose frequency was swept through the frequency range of interest. The output from the multiplier circuit, after suitable flltering and scaling, was used to control the vertical deflection of the trace on a CRO display, the horizontal deflection being keyed to the swept sine wave frequency. Modern digital spectrum analysers use the FFT or similar computational methods to determine the spectrum, which again is usually displayed in graphical form as a plot of magnitude against frequency, often on a logarithmic (decibel) scale.
The Goertzel filter is a digital filter derived from the FFT which can detect specific frequency components in a signal, for example to allow digital telephone switching circuits using DSP technology to identify the characteristic tones generated when a number is dialled on a DTMF (dual-tone multifrequency) phone. Such digital signal processing techniques are employed in modern digital exchanges.
FFT Spectrum Analyser applet: 1.02 version | 1.1 version