<< Chapter < Page Chapter >> Page >
The DFT can be reduced from exponential time with the Fast Fourier Transform algorithm.

One wonders if the DFT can be computed faster: Does another computational procedure -- an algorithm -- exist that can compute the same quantity, but more efficiently. Wecould seek methods that reduce the constant of proportionality, but do not change the DFT's complexity O N 2 .Here, we have something more dramatic in mind: Can the computations be restructuredso that a smaller complexity results?

In 1965, IBM researcher Jim Cooley and Princeton faculty member John Tukey developed what is now known as the Fast FourierTransform (FFT). It is an algorithm for computing that DFT that has order O N N for certain length inputs . Now when the length of data doubles, the spectral computational time will not quadruple aswith the DFT algorithm; instead, it approximately doubles. Later research showed that no algorithm for computing the DFT could have asmaller complexity than the FFT. Surprisingly, historical work has shown that Gauss in the early nineteenth century developed the samealgorithm, but did not publish it! After the FFT's rediscovery, not only was the computation of a signal's spectrum greatlyspeeded, but also the added feature of algorithm meant that computations had flexibility not available to analog implementations.

Before developing the FFT, let's try to appreciate the algorithm's impact. Suppose a short-length transform takes1 ms. We want to calculate a transform of a signal that is 10 times longer. Compare how much longer a straightforwardimplementation of the DFT would take in comparison to an FFT, both of which compute exactly the same quantity.

If a DFT required 1ms to compute, and signal having ten times the duration would require 100ms to compute. Using theFFT, a 1ms computing time would increase by a factor of about 10 2 logbase --> 10 33 , a factor of 3 less than the DFT would have needed.

To derive the FFT, we assume that the signal's duration is a power of two: N 2 L . Consider what happens to the even-numbered and odd-numberedelements of the sequence in the DFT calculation.

S k s 0 s 2 2 2 k N s N 2 2 N 2 k N s 1 2 k N s 3 2 2 1 k N s N 1 2 N 2 1 k N [ s 0 s 2 2 k N 2 s N 2 2 N 2 1 k N 2 ] [ s 1 s 3 2 k N 2 s N 1 2 N 2 1 k N 2 ] 2 k N

Each term in square brackets has the form of a N 2 -length DFT. The first one is a DFT of the even-numbered elements, and the second of the odd-numberedelements. The first DFT is combined with the second multiplied by the complex exponential 2 k N . The half-length transforms are each evaluated at frequency indices k 0 , , N 1 . Normally, the number of frequency indices in a DFT calculationrange between zero and the transform length minus one. The computational advantage of the FFT comes from recognizing the periodic nature of the discrete Fouriertransform. The FFT simply reuses the computations made in the half-length transforms and combines them through additions andthe multiplication by 2 k N , which is not periodic over N 2 . [link] illustrates this decomposition. As it stands, we now compute two length- N 2 transforms (complexity 2 O N 2 4 ), multiply one of them by the complex exponential (complexity O N ), and add the results (complexity O N ). At this point, the total complexity is still dominated by the half-length DFT calculations, but theproportionality coefficient has been reduced.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete-time fourier analysis. OpenStax CNX. Sep 20, 2008 Download for free at http://cnx.org/content/col10579/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete-time fourier analysis' conversation and receive update notifications?

Ask