8.6 THE FAST FOURIER [TRANSFORM](#page-13-0) (FFT)

← Back to LINEAR SYSTEMS AND SIGNALS Overview

8.6 THE FAST FOURIER TRANSFORM (FFT)

The number of computations required in performing the DFT was dramatically reduced by an algorithm developed by Cooley and Tukey in 1965 [5]. This algorithm, known as the fast Fourier transform (FFT), reduces the number of computations from something on the order of N^{2 0} to N⁰ logN0. To compute one sample Xr from Eq. (8.12), we require N⁰ complex multiplications and N⁰ −1 complex additions. To compute N⁰ such values (Xr for r = 0, 1,…,N⁰ −1), we require a total of N^{2 0} complex multiplications and N0(N⁰ − 1) complex additions. For a large N0, these computations can be prohibitively time-consuming, even for a high-speed computer. The FFT algorithm is what made the use of Fourier transform accessible for digital signal processing.

HOW DOES THE FFT REDUCE THE NUMBER OF COMPUTATIONS?

It is easy to understand the magic of the FFT. The secret is in the linearity of the Fourier transform and also of the DFT. Because of linearity, we can compute the Fourier transform of a signal x(t) as a sum of the Fourier transforms of segments of x(t) of shorter duration. The same principle applies to the computation of the DFT. Consider a signal of length N⁰ = 16 samples. As seen earlier, DFT computation of this sequence requires N^{2 0} = 256 multiplications and N0(N⁰ − 1) = 240 additions. We can split this sequence into two shorter sequences, each of length 8. To compute DFT of each of these segments, we need 64 multiplications and 56 additions. Thus, we need a total of 128 multiplications and 112 additions. Suppose, we split the original sequence in four segments of length 4 each. To compute the DFT of each segment, we require 16 multiplications and 12 additions. Hence, we need a total of 64 multiplications and 48 additions. If we split the sequence in eight segments of length 2 each, we need 4 multiplications and 2 additions for each segment, resulting in a total of 32 multiplications and 8 additions. Thus, we have been able to reduce the number of multiplications from 256 to 32 and the number of additions from 240 to 8. Moreover, some of these multiplications turn out to be multiplications by 1 or −1. All this fantastic economy in the number of computations is realized by the FFT without any approximation! The values obtained by the FFT are identical to those obtained by the DFT. In this example, we considered a relatively small value of N⁰ = 16. The reduction in the number of computations is much more dramatic for higher values of N0.

The FFT algorithm is simplified if we choose N⁰ to be a power of 2, although such a choice is not essential. For convenience, we define

$$W_{N_0} = e^{-(j2\pi/N_0)} = e^{-j\Omega_0}$$

so that

$$X_r = \sum_{n=0}^{N_0 - 1} x_n W_{N_0}^{nr} \qquad 0 \le r \le N_0 - 1 \tag{8.21}$$

and

$$x_n = \frac{1}{N_0} \sum_{r=0}^{N_0 - 1} X_r W_{N_0}^{-nr} \qquad 0 \le n \le N_0 - 1 \tag{8.22}$$

Although there are many variations of the Tukey–Cooley algorithm, these can be grouped into two basic types: decimation in time and decimation in frequency.

THE DECIMATION-IN-TIME ALGORITHM

Here we divide the N0-point data sequence xn into two (N0/2)-point sequences consisting of evenand odd-numbered samples, respectively, as follows:

$$\underbrace{x_0, x_2, x_4, \ldots, x_{N_0-2}}_{\text{sequence } g_n}, \underbrace{x_1, x_3, x_5, \ldots, x_{N_0-1}}_{\text{sequence } h_n}$$

Then, from Eq. (8.21),

$$X_r = \sum_{n=0}^{(N_0/2)-1} x_{2n} W_{N_0}^{2n} + \sum_{n=0}^{(N_0/2)-1} x_{2n+1} W_{N_0}^{(2n+1)r}$$

Also, since

$$W_{N_0/2} = W_{N_0}^2$$

we have

$$X_r = \sum_{n=0}^{(N_0/2)-1} x_{2n} W_{N_0/2}^{nr} + W_{N_0}^r \sum_{n=0}^{(N_0/2)-1} x_{2n+1} W_{N_0/2}^{nr}$$

= $G_r + W_{N_0}^r H_r$ 0 \le $r \le N_0 - 1$ (8.23)

where Gr and Hr are the (N0/2)-point DFTs of the even- and odd-numbered sequences, gn and hn, respectively. Also, Gr and Hr, being the (N0/2)-point DFTs, are (N0/2) periodic. Hence,

$$G_{r+(N_0/2)} = G_r \qquad \text{and} \qquad H_{r+(N_0/2)} = H_r \tag{8.24}$$

Moreover,

$$W_{N_0}^{r + (N_0/2)} = W_{N_0}^{N_0/2} W_{N_0}^r = e^{-j\pi} W_{N_0}^r = -W_{N_0}^r$$

\n(8.25)

From Eqs. (8.23), (8.24), and (8.25), we obtain

$$X_{r+(N_0/2)} = G_r - W_{N_0}^r H_r \tag{8.26}$$

This property can be used to reduce the number of computations. We can compute the first N0/2 points (0 ≤ n ≤ (N0/2) − 1) of Xr by using Eq. (8.23) and the last N0/2 points by using Eq. (8.26) as

$$X_r = G_r + W_{N_0}^r H_r \qquad 0 \le r \le \frac{N_0}{2} - 1$$ $$X_{r + (N_0/2)} = G_r - W_{N_0}^r H_r \qquad 0 \le r \le \frac{N_0}{2} - 1$$

(8.27)

Figure 8.24 Butterfly signal flow graph.

Figure 8.25 Successive steps in an 8-point FFT.

Thus, an N0-point DFT can be computed by combining the two (N0/2)-point DFTs, as in Eq. (8.27). These equations can be represented conveniently by the signal flow graph depicted in Fig. 8.24. This structure is known as a butterfly. Figure 8.25a shows the implementation of Eq. (8.24) for the case of N⁰ = 8.

The next step is to compute the (N0/2)-point DFTs Gr and Hr. We repeat the same procedure by dividing gn and hn into two (N0/4)-point sequences corresponding to the even- and odd-numbered samples. Then we continue this process until we reach the one-point DFT. These steps for the case of N⁰ = 8 are shown in Figs. 8.25a, 8.25b, and 8.25c. Figure 8.25c shows that the two-point DFTs require no multiplication.

To count the number of computations required in the first step, assume that Gr and Hr are known. Equation (8.27) clearly shows that to compute all the N⁰ points of the Xr, we require N⁰ complex additions and N0/2 complex multiplications† (corresponding to W^r N0 Hr).

In the second step, to compute the (N0/2)-point DFT Gr from the (N0/4)-point DFT, we require N0/2 complex additions and N0/4 complex multiplications. We require an equal number of computations for Hr. Hence, in the second step, there are N⁰ complex additions and N0/2 complex multiplications. The number of computations required remains the same in each step. Since a total of log2N⁰ steps is needed to arrive at a one-point DFT, we require, conservatively, a total of N⁰ log2N⁰ complex additions and (N0/2)log2N⁰ complex multiplications, to compute the N0-point DFT. Actually, as Fig. 8.25c shows, many multiplications are multiplications by 1 or −1, which further reduces the number of computations.

The procedure for obtaining IDFT is identical to that used to obtain the DFT except that WN⁰ = ej(2π/N0) instead of e−j(2π/N0) (in addition to the multiplier 1/N0). Another FFT algorithm, the decimation-in-frequency algorithm, is similar to the decimation-in-time algorithm. The only difference is that instead of dividing xn into two sequences of even- and odd-numbered samples, we divide xn into two sequences formed by the first N0/2 and the last N0/2 samples, proceeding in the same way until a single-point DFT is reached in log2N⁰ steps. The total number of computations in this algorithm is the same as that in the decimation-in-time algorithm.