An algorithm called the fast Fourier transform (FFT) has been developed for computing the DFT on digital computers. For a signal that has been sampled to give N evenly spaced samples, the Nyquist frequency c% is given by

coN = л/At = nN/T (4.6.1)

This corresponds to harmonic number к = N/2. Thus, if the signal energy at frequencies above the Nyquist frequency is negligible, then the Fourier transform at these N/2 frequencies gives a complete spectral representation of the signal. The complete Fourier analysis at N/2 frequencies to give all N Fourier coefficients (real and imaginary at each frequency) requires N2 multiplications when Eq. (4.3.5) is implemented directly.

The FFT algorithm is an efficient method that can greatly reduce the required number of arithmetic operations if the total number of data points can be restricted to some integer power of two (N = 2"). It has been found that the FFT algorithm requires 2N log2 N arithmetic operations to evaluate the N Fourier coefficients. The ratio of the number of arithmetic opera­tions for the FFT to the number for a conventional DFT is

(2 log2 N)/N (4.6.2)

This represents a substantial savings for larger values of N. For example, a data record containing 32,768 samples would take 1260 times as long to Fourier analyze using the conventional method as compared to the FFT. This makes it economically feasible to analyze signals containing many more data points than was possible prior to implementation of the FFT.

The principle underlying the FFT may be explained quite simply using a development of Cochran et al. (7). We begin by dividing the set of N samples Xp into two sets of N/2 samples each. The first set, Yp, is composed of all even-numbered samples and the second set, Zp, is composed of all odd — numbered samples. Thus

Yp = X2p, Zp = X2p+l, 0 < p < (N/2) — 1 (4.6.3)

The desired Fourier transform is

Ak = Y Xp exp( — 2njkp/N) (4.6.4)

p = о

It is possible to develop a formula for Ak in terms of the Fourier transform of Yp and Zp. This leads to the economy of the FFT algorithm. The Fourier

t See the literature (7-9).

transforms of Yp and Zp are

(N12)- 1

Bk = X Ypexp(-4njkp/N)

P = 0 (N12>- 1

Ck = X Zpexp(-4njkp/N)

P = o

The Fourier transform of the total signal may be written in terms of the odd — and even-numbered points as follows:

Inspection of Eqs. (4.6.5) and (4.6.6) reveals the following:

Bk = Bk+(N/2) (4.6.9)

Ck = Ck + iNi2) (4.6.10)

Thus we obtain

Equations (4.6.8) and (4.6.11) provide the formulas required to construct Ak from Bk and Ck.

Since the evaluations of Bk and Ck involved N/2 samples, conventional Fourier analysis to obtain these quantities requires 2 x (N/2)2 = N2 multiplications. Therefore, the analysis based on splitting the data record halves the computing time. Of course the halving can be repeated over and over as long as the remaining record is divisible by two. This is why the complete FFT algorithm is based on 2" data points for integer values of n.

Efficient computer programs have been developed for FFT calculations. One important feature of many of these programs is the capability of “in place” computation. This means that the computer is required to store only the N data points, because after they are used, the values at any stage in the calculation are no longer needed and their storage locations may be allotted to new intermediate values. Also, the details of the logic required to perform the FFT calculation are well documented in the literature (8).

It should be noted that other forms of the FFT are available and that FFT algorithms exist for N = 3", N = 4", and so on. However, the method out­lined here illustrates the principles involved, and the algorithm for N = 2" is by far the most common.