504 Chapter 12.Fast Fourier Transform The discrete form of Parseval's theorem is N-1 N-1 (12.1.10) k=0 刀=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) RECIPES I 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 平空> Press. was this:Define W as the complex number W三e2m/N (12.2.1) Then (12.1.7)can be written as IENTIFIC 61 N-1 Hn= 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 A,'s.This matrix multiplication evidently requires Numerica 10.621 N2 complex multiplications,plus a smaller number of operations to generate the 431 required powers of W.So,the discrete Fourier transform appears to be an O(N2) Recipes 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 (outside Fourier transform,or FFT.The difference between Nlog2 N and N2 is immense. North 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 [11)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 derivations of the algorithm.Danielson and Lanczos showed that a discrete Fourier transform of length N can be rewritten as the sum of two discrete Fourier transforms,each of length N/2.One of the two is formed from the504 Chapter 12. Fast Fourier Transform Permission is granted for internet users to make one paper copy for their own personal use. Further reproduction, or any copyin Copyright (C) 1988-1992 by Cambridge University Press. Programs Copyright (C) 1988-1992 by Numerical Recipes Software. Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5) g of machine￾readable files (including this one) to any server computer, is strictly prohibited. To order Numerical Recipes books or CDROMs, visit website http://www.nr.com or call 1-800-872-7423 (North America only), or send email to directcustserv@cambridge.org (outside North America). The discrete form of Parseval’s theorem is N
−1 k=0 |hk| 2 = 1 N N
−1 n=0 |Hn| 2 (12.1.10) 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 ≡ e2πi/N (12.2.1) Then (12.1.7) can be written as Hn = N
−1 k=0 Wnkhk (12.2.2) 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 × 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(N 2) 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 derivations of the algorithm. Danielson and Lanczos showed that a discrete Fourier transform of length N can be rewritten as the sum of two discrete Fourier transforms, each of length N/2. One of the two is formed from the