Đang chuẩn bị liên kết để tải về tài liệu:
Fast Fourier Transform part 3

The discrete form of Parseval’s theorem is There are also discrete analogs to the convolution and correlation theorems (equations 12.0.9 and 12.0.11), but we shall defer them to §13.1 and §13.2, respectively. | 504 Chapter 12. Fast Fourier Transform The discrete form of Parseval s theorem is N-1 N-1 h I2 H. 12.1.10 k 0 n 0 There are also discrete analogs to the convolution and correlation theorems equations 12.0.9 and 12.0.11 but we shall defer them to 13.1 and 13.2 respectively. CITED REFERENCES AND FURTHER READING Brigham E.O. 1974 The Fast Fourier Transform Englewood Cliffs NJ Prentice-Hall . Elliott D.F. and Rao K.R. 1982 Fast Transforms Algorithms Analyses Applications New York Academic Press . 12.2 Fast Fourier Transform FFT How much computation is involved in computing the discrete Fourier transform 12.1.7 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 12.2.1 Then 12.1.7 can be written as N-1 H X Wnkhk 12.2.2 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 J.W. Cooley and J.W. 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 .