If math functions were rated by popularity, the fast Fourier transform (FFT) probably would be in the top 10. With applications ranging from atmospheric research to quality control, the FFT is a versatile function for analyzing waveforms.
Fourier transforms represent time-domain waveforms as sums of sine and cosine functions in the frequency domain. The magnitude of a frequency component determines the contribution of that frequency (Figure 1).
Engine knock is a common example of diagnosing a problem in the frequency domain. The magnitude (how loud the engine is knocking) and pitch (specific frequency or frequencies) immediately characterize the severity of the problem.
The FFT algorithm was invented by James Cooley and John Tukey in 1965. Cooley, a new member of the IBM research staff at the time, was given the problem because, by his own admission, he “had nothing important to do.”
As popular as Fourier analysis is, it did not gain acceptance in Fourier’s time because of a distrust in the use of series. One influential mathematician in 1828 commented, “Divergent series are the invention of the devil.” As we will see, the devil still is in the details.
FFT and other digital signal processing techniques can save time and money, but they often are misused because of a disregard for their limitations. A mathematically correct FFT calculated from a sampled wave may not accurately represent the frequency components of the original wave.
The choices of input windowing, sample frequency, and the number of samples taken before calculating an FFT can lead to very different results. Even a small change in the sampling frequency can produce a 25% change in the calculated magnitude of a frequency component because the FFT cannot display the exact frequency of the sampled wave unless the wave is an exact multiple of the frequency resolution of the FFT.
For example, if a data acquisition card or sampling oscilloscope has taken 4,096 samples at a 50-kHz rate, the maximum frequency resolution obtained is 50,000÷4,096 or 12.207 Hz/S. The FFT result puts the spectrum into “bins” spaced at 12.207-Hz intervals. If the input frequency is 12,207 Hz, an exact multiple of the resolution, the resultant amplitude of the frequency component yielded by the FFT is 1.0.
If the input waveform is between two exact multiples—for example, 12,200 Hz, the peak amplitude is 0.729. The calculated frequency is 12,195, the closest multiple of the sampling interval to the true frequency. The spectrum also spreads out slightly since it no longer can be represented by a perfect peak with only one non-zero value.
The display resolution of most PCs often is a more severe problem. Divide the highest frequency plotted by the number of X-axis pixels in the graph. The result is the smallest displayable frequency increment. For example, if an FFT spans DC to 1 MHz and the displayed graph is 400 pixels wide, you can resolve only 2,500 Hz. Anything between that interval will cover or be hidden by adjacent points.
Two other concepts that must be understood are leakage and aliasing. Leakage occurs when the sampled waveform is not an integer multiple of cycles of the input waveform. Stated another way, leakage occurs when an integer multiple of the period is not included in the data set. In this case, even if the sampled waveform is an integer multiple of the frequency resolution, the result will include additional frequency components, called side lobes.
What the FFT “sees” is a sampled waveform, not the continuous waveform. If the waveform is not sampled at a high enough rate, the sampled wave will not be an accurate representation of the input wave. This is aliasing or the representation of high-frequency components by lower-frequency lobes.
The minimum sampling frequency is based on the Nyquist criterion which states that the function being measured must be sampled at a rate equal to twice the highest frequency of interest. The higher the sampling rate, the closer the sampled wave is to the original. Sampling at less than the Nyquist rate guarantees a wrong result (Figure 2).
These restrictions seem to lead to a simple solution: Just sample the input wave at the highest frequency rate possible and calculate as many points as possible. Unfortunately, the higher the sampling frequency, the higher the cost of the A/D and the memory required to hold the samples.
The larger the number of points calculated, the longer it takes to calculate them. An FFT must make Nlog2N calculations. This is a big improvement over the discreet Fourier transform which must make N2 calculations.
However, time and money always will limit the accuracy of the final result. As one UC Berkeley professor noted on his web page, “The FFT can also be used on a galaxy, but at the cost of increased storage and computation.” Nicely understated, professor.
Another essential ingredient in calculating an accurate FFT is windowing. There are several windowing functions such as Blackman, Poisson, and Square (Figure 3). Their purpose is to transform a selected portion of the waveform and assume a zero value for the waveform outside the area selected.
Different waveform types require different window functions, and the correct choice is a hot topic of current research. A recent Internet search yielded more than 90,000 references to FFTs and windowing, many with useful and practical suggestions. The number of references also indicates that an FFT rarely yields a single “right” answer.
About the Author
Kerry Newcom is the president of Capital Equipment Corporation. He received a B.S.E.E. degree from Purdue and worked as a design engineer and product manager at Hewlett-Packard before founding Capital Equipment Corporation in 1983. Mr. Newcom also is an accomplished contemporary and jazz percussionist. Capital Equipment Corporation, 900 Middlesex Turnpike, Building 2, Billerica, MA 01821-3929, (508) 663-2002, www.cec488.com.
Applying FFT Successfully
For practical application of the FFT, here are some simple rules to
Use a sampling frequency of at least twice the highest frequency of interest.
Select a windowing algorithm appropriate for the sampled waveform.
Sample an integer number of cycles.
Set the number of samples equal to a power of 2.
Calculate the maximum error magnitude based on the displayed frequency and the sampling frequency. If the error is not within your tolerance, change the windowing algorithm and sampling frequency to produce a better result.
Finally, when using a PC to display an FFT, remember that the smallest resolvable frequency is equal to the displayed frequency range divided by the graph width in pixels.
Copyright 1997 Nelson Publishing Inc.