<< Chapter < Page | Chapter >> Page > |
Now for the fun. Because $N=2^{L}$ , each of the half-length transforms can be reduced to two quarter-length transforms, each of these to twoeighth-length ones, etc. This decomposition continues until we are left with length-2 transforms. This transform is quitesimple, involving only additions. Thus, the first stage of the FFT has $\frac{N}{2}$ length-2 transforms (see the bottom part of [link] ). Pairs of these transforms are combined by adding one to the other multiplied by a complexexponential. Each pair requires 4 additions and 2 multiplications, giving a total number of computations equaling $6\xb7\frac{N}{4}=\frac{3N}{2}$ . This number of computations does not change from stage to stage.Because the number of stages, the number of times the length can be divided by two, equals $\log_{2}N$ , the number of arithmetic operations equals $\frac{3N}{2}\log_{2}N$ , which makes the complexity of the FFT $O(N\log_{2}N)$ .
Doing an example will make computational savings more obvious. Let's look at the detailsof a length-8 DFT. As shown on [link] , we first decompose the DFT into two length-4 DFTs, with the outputs added and subtracted together in pairs.Considering [link] as the frequency index goes from 0 through 7, we recycle values fromthe length-4 DFTs into the final calculation because of the periodicity of the DFT output. Examining how pairs of outputsare collected together, we create the basic computational element known as a butterfly ( [link] ).
By considering together the computations involving common output frequencies from the two half-length DFTs, we see that the twocomplex multiplies are related to each other, and we can reduce our computational work even further. By further decomposing thelength-4 DFTs into two length-2 DFTs and combining their outputs, we arrive at the diagram summarizing the length-8 fastFourier transform ( [link] ). Although most of the complex multiplies are quite simple(multiplying by $e^{-(i\frac{\pi}{2})}$ means swapping real and imaginary parts and changing their signs), let's count those forpurposes of evaluating the complexity as full complex multiplies. We have $\frac{N}{2}=4$ complex multiplies and $N=8$ complex additions for each stage and $\log_{2}N=3$ stages, making the number of basic computations $\frac{3N}{2}\log_{2}N$ as predicted.Note that the ordering of the input sequence in the two parts of [link] aren't quite the same. Why not? How is the ordering determined?
The upper panel has not used the FFT algorithm to compute the length-4 DFTs while the lower one has. The ordering isdetermined by the algorithm.
Other "fast" algorithms were discovered, all of which make use of how many common factors the transformlength $N$ has. In number theory, the number of prime factors a given integer has measures how composite it is. The numbers 16 and 81 are highly composite (equaling $2^{4}$ and $3^{4}$ respectively), the number 18 is less so ( $2^{1}\xb73^{2}$ ), and 17 not at all (it's prime). In over thirty years of Fourier transform algorithm development, the originalCooley-Tukey algorithm is far and away the most frequently used. It is so computationally efficient that power-of-twotransform lengths are frequently used regardless of what the actual length of the data.
Suppose the length of the signal were $500$ ? How would you compute the spectrum of this signal using the Cooley-Tukeyalgorithm? What would the length $N$ of the transform be?
The transform can have any greater than or equal to the actual duration of the signal. We simply“pad” the signal with zero-valued samples until a computationally advantageous signal length results. Recallthat the FFT is an algorithm to compute the DFT . Extending the length of the signal this way merely means weare sampling the frequency axis more finely than required. To use the Cooley-Tukey algorithm, the length of theresulting zero-padded signal can be 512, 1024, etc. samples long.
Notification Switch
Would you like to follow the 'Discrete-time fourier analysis' conversation and receive update notifications?