3.2 Fast fourier transform (fft)  (Page 2/2)

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·\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)$ .

Length-8 dft decomposition

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] ).

Butterfly

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·3^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.