12.2 Fast Fourier Transform(FFT) 505 even-numbered points of the original N,the other from the odd-numbered points. The proof is simply this: -1 Fk= 2rik/Nf方 j=0 N/2- N/2-1 ∑e2aie/f+ 2ik(2j+1)/N f2j+1 j= 1=0 (12.2.3) N/2-1 N/2-1 e2xikj/(N/2)f23 +Wk e2ikj/(N2)f2j+1 83 j=0 j=0 =F+WF阳 g In the last line,W is the same complex constant as in (12.2.1),Fe denotes the kth component of the Fourier transform of length N/2 formed from the even components of the original fi's,while Fe is the corresponding transform of length N/2 formed from the odd components.Notice also that k in the last line of(12.2.3)varies from 9 0 to N,not just to N/2.Nevertheless,the transforms Fe and F are periodic in k with length N/2.So each is repeated through two cycles to obtain F The wonderful thing about the Danielson-Lanczos Lemma is that it can be used recursively.Having reduced the problem of computing F&to that of computing Fe and Fe,we can do the same reduction of Fe to the problem of computing 孕芝%0 9 the transform of its N/4 even-numbered input data and N/4 odd-numbered data. In other words,we can define Fee and Feo to be the discrete Fourier transforms of the points which are respectively even-even and even-odd on the successive subdivisions of the data. Although there are ways of treating other cases,by far the easiest case is the one in which the original N is an integer power of 2.In fact,we categorically recommend that you only use FFTs with N a power of two.If the length of your data set is not a power of two,pad it with zeros up to the next power of two.(We will give more sophisticated suggestions in subsequent sections below.)With this restriction g今 6 10-521 on N,it is evident that we can continue applying the Danielson-Lanczos Lemma Numerica until we have subdivided the data all the way down to transforms of length 1.What 43106 is the Fourier transform of length one?It is just the identity operation that copies its one input number into its one output slot!In other words,for every pattern of log2 N e's and o's,there is a one-point transform that is just one of the input numbers fn Peoceoeo.…oee=fn for some n (12.2.4) (Of course this one-point transform actually does not depend on k,since it is periodic in k with period 1.) The next trick is to figure out which value of n corresponds to which pattern of e's and o's in equation(12.2.4).The answer is:Reverse the pattern of e's and o's, then let e =0 and o =1,and you will have,in binary the value of n.Do you see why it works?It is because the successive subdivisions of the data into even and odd are tests of successive low-order (least significant)bits of n.This idea of bit reversal can be exploited in a very clever way which,along with the Danielson-Lanczos12.2 Fast Fourier Transform (FFT) 505 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). even-numbered points of the original N, the other from the odd-numbered points. The proof is simply this: Fk = N
−1 j=0 e2πijk/N fj = N/
2−1 j=0 e2πik(2j)/N f2j + N/
2−1 j=0 e2πik(2j+1)/N f2j+1 = N/
2−1 j=0 e2πikj/(N/2)f2j + Wk N/
2−1 j=0 e2πikj/(N/2)f2j+1 = Fe k + Wk Fo k (12.2.3) In the last line, W is the same complex constant as in (12.2.1), F e k denotes the kth component of the Fourier transform of length N/2 formed from the even components of the original fj ’s, while Fo k is the corresponding transform of length N/2 formed from the odd components. Notice also that k in the last line of (12.2.3) varies from 0 to N, not just to N/2. Nevertheless, the transforms F e k and Fo k are periodic in k with length N/2. So each is repeated through two cycles to obtain Fk. The wonderful thing about the Danielson-Lanczos Lemma is that it can be used recursively. Having reduced the problem of computing Fk to that of computing Fe k and Fo k , we can do the same reduction of F e k to the problem of computing the transform of its N/4 even-numbered input data and N/4 odd-numbered data. In other words, we can define F ee k and Feo k to be the discrete Fourier transforms of the points which are respectively even-even and even-odd on the successive subdivisions of the data. Although there are ways of treating other cases, by far the easiest case is the one in which the original N is an integer power of 2. In fact, we categorically recommend that you only use FFTs with N a power of two. If the length of your data set is not a power of two, pad it with zeros up to the next power of two. (We will give more sophisticated suggestions in subsequent sections below.) With this restriction on N, it is evident that we can continue applying the Danielson-Lanczos Lemma until we have subdivided the data all the way down to transforms of length 1. What is the Fourier transform of length one? It is just the identity operation that copies its one input number into its one output slot! In other words, for every pattern of log 2 N e’s and o’s, there is a one-point transform that is just one of the input numbers f n Feoeeoeo···oee k = fn for some n (12.2.4) (Of course this one-point transform actually does not depend on k, since it is periodic in k with period 1.) The next trick is to figure out which value of n corresponds to which pattern of e’s and o’s in equation (12.2.4). The answer is: Reverse the pattern of e’s and o’s, then let e = 0 and o = 1, and you will have, in binary the value of n. Do you see why it works? It is because the successive subdivisions of the data into even and odd are tests of successive low-order (least significant) bits of n. This idea of bit reversal can be exploited in a very clever way which, along with the Danielson-Lanczos