The discrete form of Parseval’s theorem is There are also discrete analogs to the convolution and correlation theorems (equations and ), but we shall defer them to § and §, respectively. | 504 Chapter 12. Fast Fourier Transform The discrete form of Parseval s theorem is N-1 N-1 h I2 H. k 0 n 0 There are also discrete analogs to the convolution and correlation theorems equations and but we shall defer them to and respectively. CITED REFERENCES AND FURTHER READING Brigham . 1974 The Fast Fourier Transform Englewood Cliffs NJ Prentice-Hall . Elliott . and Rao . 1982 Fast Transforms Algorithms Analyses Applications New York Academic Press . Fast Fourier Transform FFT How much computation is involved in computing the discrete Fourier transform of N points For many years until the mid-1960s the standard answer was this Define W as the complex number W e i N Then can be written as N-1 H X Wnkhk k 0 In other words the vector of hk s is multiplied by a matrix whose n k th element is the constant W to the power n x k. The matrix multiplication produces a vector result whose components are the Hn s. This matrix multiplication evidently requires N2 complex multiplications plus a smaller number of operations to generate the required powers of W. So the discrete Fourier transform appears to be an O N2 process. These appearances are deceiving The discrete Fourier transform can in fact be computed in O N log2 N operations with an algorithm called the fast Fourier transform or FFT. The difference between N log2 N and N2 is immense. With N 106 for example it is the difference between roughly 30 seconds of CPU time and 2 weeks of CPU time on a microsecond cycle time computer. The existence of an FFT algorithm became generally known only in the mid-1960s from the work of . Cooley and . Tukey. Retrospectively we now know see 1 that efficient methods for computing the DFT had been independently discovered and in some cases implemented by as many as a dozen individuals starting with Gauss in 1805 One rediscovery of the FFT that of Danielson and Lanczos in 1942 provides one of the clearest .
