Given a function h(t), its Fourier transform H(f) is:
where i is the imaginary square root of –1. The Fourier transform H is a function of some other variable f. The process can be reversed at any point t where h is continuous by taking the inverse Fourier transform:
This may seem abstract, but Fourier transforms are widely used in practical applications. The classic example is signal processing. A signal can be represented as a function of time t or as a function of frequency f. You switch between the two representations by applying the Fourier transform or inverse Fourier transform. Fourier transforms are also used to solve partial differential equations. Accordingly, they are used in applications where partial differential equations arise, such as physics and financial engineering. Many software packages numerically evaluate Fourier transforms and their inverses. Results will be poor (often downright wrong) if the software employs standard techniques of numerical integration to evaluate integrals [1] and [2]. Such techniques are ill suited to the oscillatory integrands encountered with Fourier transforms. Effective software employs a technique known as the fast Fourier transform (FFT). This algorithm was discovered by Cooley and Tukey (1965). It runs rapidly and provides excellent results. It was one of the most significant discoveries in applied mathematics in the latter part of the 20th century. It revolutionized telecommunications. See Brigham (1988) for a discussion of Fourier transforms and the fast Fourier transform. If you use off-the-shelf software to value Fourier transforms, be aware that the definitions of the Fourier transform and inverse Fourier transform are not standardized. Check your software literature for the precise definition it uses, and modify output if necessary. To illustrate the use of fast Fourier transform software, consider the function:
which is graphed in Exhibit 1:
Although the function is defined for all real numbers, it can only be input to fast Fourier transform software on a finite interval. For this example, the interval considered is [–3,3]. Whatever interval you choose, it should be large enough to capture what is “important” about the function. To avoid an effect called aliasing, choose an interval such that the function equals 0—or almost 0—at the end points. The fast Fourier transform software treats the function as periodic, as illustrated in Figure 3.
Because of this imputed periodicity, you can shift the interval over which you input the function to the fast Fourier transform software. For technical reasons, you want to shift it so the left end-point is 0. For this example, the interval [0,6] is used instead of [–3,3] to input function [3] to the fast Fourier transform software. Described in this manner, the function appears as in Exhibit 3. Note that the function in Exhibit 3 is different from function [3], but it communicates the same information.
Now sample (evaluate) the function at a set of n evenly spaced values for t on the interval [0,6]. The number n of sampled values must be a power of 2. Let’s sample 25 = 32 values. Let Δ = 6/32 = .1875 be the sample interval. Note that you sample at the left end-point but not the right end-point. In the example, the function is sampled at t = 0 but not at t = 6. Output from the fast Fourier transform software comprises n values that are proportional to values of the Fourier transform H(f). To make them equal to H(f), multiply by Δ. Example results are indicated in Exhibit 4:
Your fast Fourier transform software is likely to accept
as inputs only the values for h(t) and provide as outputs
only the values proportional to
H(f). This means you will need to infer the corresponding
values for f from the values for t. The first value for
f is 0. Subsequent values are spaced The fast Fourier transform is a numerical technique, so results are not exact. Exhibit 5 compares results of Exhibit 4 with the actual Fourier transform H(f) of h(t). In this example, results are excellent. You can improve results by sampling at a greater number n of values for t.
When sampling a function h(t), the number n of values you sample as well as their spacing Δ should be chosen based upon the complexity of the graph of h. In the example, h had a simple graph, so sampling n = 32 points was sufficient. In probabilistic applications, you may deal with functions that oscillate wildly. Such functions need to be sampled at sufficiently many values to capture that oscillation. Otherwise, the fast Fourier transform will produce erroneous results. It is not uncommon to sample at 512 or more values.
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
apart. At the half-way point, the f values cycle back to the
negative
f-axis. In the above example, the 17th value for f
equals –2.6667 instead of 2.6667. This cycling is related to
periodicity.
_125.gif)
_125.gif)
