506 Chapter 12. Fast Fourier Transform 000 000 000 001 001 001 010 010 010 011 011 011 100 100 100 Permission is read able files 101 101 101 110 110 110 .com or call granted fori 111 111 111 (including this one) (a) (b) 111800-672 19881992y0的e 19 Figure 12.2.1.Reordering an array (here of length 8)by bit reversal,(a)between two arrays,versus(b) from NUMERICAL RECIPES IN C: in place.Bit reversal reordering is a necessary part of the fast Fourier transform(FFT)algorithm. (North Lemma,makes FFTs practical:Suppose we take the original vector of data fi America 州bMe se tusers to make one paper UnN电.t THE and rearrange it into bit-reversed order(see Figure 12.2.1),so that the individual 是 ART numbers are in the order not ofj,but of the number obtained by bit-reversing j. Then the bookkeeping on the recursive application of the Danielson-Lanczos Lemma ictly proh Programs becomes extraordinarily simple.The points as given are the one-point transforms. We combine adjacent pairs to get two-point transforms,then combine adjacent pairs of pairs to get 4-point transforms,and so on,until the first and second halves of the whole data set are combined into the final transform.Each combination takes to dir of order N operations,and there are evidently log2 N combinations,so the whole algorithm is of order Nlog2 N(assuming,as is the case,that the process of sorting OF SCIENTIFIC COMPUTING (ISBN into bit-reversed order is no greater in order than Nlog2 N). 1988-19920 This,then,is the structure of an FFT algorithm:It has two sections.The first section sorts the data into bit-reversed order.Luckily this takes no additional storage, 10-521 since it involves only swapping pairs of elements.(If is the bit reverse of k2,then k2 is the bit reverse of k1.)The second section has an outer loop that is executed log2 N times and calculates,in turn,transforms of length 2,4,8,...,N.For each Numerical Recipes 431985 stage of this process,two nested inner loops range over the subtransforms already computed and the elements ofeach transform,implementing the Danielson-Lanczos (outside Lemma.The operation is made more efficient by restricting external calls for North Software. trigonometric sines and cosines to the outer loop,where they are made only log2 N times.Computation of the sines and cosines of multiple angles is through simple recurrence relations in the inner loops(cf.5.5.6). visit website The FFT routine given below is based on one originally written by N.M. machine Brenner.The input quantities are the number of complex data points(nn),the data array(data[1..2*nn]),and isign,which should be set to either +1 and is the sign of i in the exponential of equation(12.1.7).When isign is set to-1,the routine thus calculates the inverse transform (12.1.9)-except that it does not multiply by the normalizing factor 1/N that appears in that equation.You can do that yourself. Notice that the argument nn is the number of complex data points.The actual506 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). 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 000 001 010 011 100 101 110 111 (a) (b) Figure 12.2.1. Reordering an array (here of length 8) by bit reversal, (a) between two arrays, versus (b) in place. Bit reversal reordering is a necessary part of the fast Fourier transform (FFT) algorithm. Lemma, makes FFTs practical: Suppose we take the original vector of data f j and rearrange it into bit-reversed order (see Figure 12.2.1), so that the individual numbers are in the order not of j, but of the number obtained by bit-reversing j. Then the bookkeeping on the recursive application of the Danielson-Lanczos Lemma becomes extraordinarily simple. The points as given are the one-point transforms. We combine adjacent pairs to get two-point transforms, then combine adjacent pairs of pairs to get 4-point transforms, and so on, until the first and second halves of the whole data set are combined into the final transform. Each combination takes of order N operations, and there are evidently log 2 N combinations, so the whole algorithm is of order N log2 N (assuming, as is the case, that the process of sorting into bit-reversed order is no greater in order than N log 2 N). This, then, is the structure of an FFT algorithm: It has two sections. The first section sorts the data into bit-reversed order. Luckily this takes no additional storage, since it involves only swapping pairs of elements. (If k 1 is the bit reverse of k2, then k2 is the bit reverse of k1.) The second section has an outer loop that is executed log2 N times and calculates, in turn, transforms of length 2, 4, 8,...,N. For each stage of this process, two nested inner loops range over the subtransforms already computed and the elements of each transform, implementing the Danielson-Lanczos Lemma. The operation is made more efficient by restricting external calls for trigonometric sines and cosines to the outer loop, where they are made only log 2 N times. Computation of the sines and cosines of multiple angles is through simple recurrence relations in the inner loops (cf. 5.5.6). The FFT routine given below is based on one originally written by N. M. Brenner. The input quantities are the number of complex data points (nn), the data array (data[1..2*nn]), and isign, which should be set to either ±1 and is the sign of i in the exponential of equation (12.1.7). When isign is set to −1, the routine thus calculates the inverse transform (12.1.9) — except that it does not multiply by the normalizing factor 1/N that appears in that equation. You can do that yourself. Notice that the argument nn is the number of complex data points. The actual