Chapter 22. Fourier Transforms

An endeavor common to a wide variety of scientific and engineering disciplines is the need to analyze or process a signal from a data source. A signal can be characterized either in the time domain (amplitude versus time) or in the frequency domain (frequency magnitude versus frequency). Sometimes it may be more convenient to work in the time domain, sometimes in the frequency domain, and there are times when you will want to switch back and forth between the two domains.

A Fourier transform is a way of switching between time and frequency domains. It is based on the theory that a signal can be decomposed into an infinite series of sinusoidal functions. The sinusoidal functions can identify the frequencies and amplitudes associated with the signal. The forward Fourier transform is usually defined to convert from the time to frequency domains. The inverse Fourier transform converts a signal from the frequency domain to the time domain and can be used to reconstitute a signal from a frequency spectrum. Fourier transforms are widely used in science and engineering in such differing fields as acoustics, image processing, seismology, astronomy, optics, and digital filtering.

The integral form of the Fourier transform is applicable only if the signal can be expressed as a mathematical equation. If no such expression exists, a discrete Fourier transform (DFT) can be used. The DFT samples values of the input signal at locations along a specified range and applies a Fourier transform to the sampled data. The transformed results are also at discrete points along either the time or frequency domains.

DFTs work well, but are computationally expensive if a large number of data samples is used. The standard form of the DFT has an operation count proportional to the square of the number of samples. If you are taking a million or so data samples, this can be a real problem. To overcome this limitation, variations on the standard DFT have been developed that require a substantially reduced operation count. These methods are referred to as fast Fourier transforms (FFTs).

In this chapter we will go over the general theory of the Fourier transform and show how the DFT and FFT algorithms are derived. We will write methods that implement a DFT and FFT and apply the methods to several sample problems. This chapter will pass rather quickly through Fourier transform theory and is not meant to be a comprehensive treatment on the subject. For example, we won't cover such topics as convolution theorem, Parseval's theorem, or windowing. The purpose of this chapter is to show how general workhorse DFT and FFT methods can be written in Java with the tools and concepts we have learned in this book. For a more complete treatment of Fourier transforms consult The Fast Fourier Transform and Its Applications by E. Oran Brigham.

The topics we will cover in this chapter are

• The Fourier transform

• Discrete Fourier transform

• Analyzing composite signals

• Sampling theory

• Spectral leakage

• Fast Fourier transform