12.4 FFT in Two or More Dimensions 523 -data[1] row of 2N,float numbers row I 万=0 row 2 fi2N△1 y2N1-1 row N/2 f1=N△1 8 row N /2+1 1=±2△ 虽 三g 2N1-1 row N /2+2 =- N△1 row N =-N 令 data [2N N]--- America Press. ART Figure 12.4.1.Storage arrangement of frequencies in the output H(,f2)of a two-dimensional FFT. 9 The input data is a two-dimensional M x N2 array h(t1,t2)(stored by rows of complex numbers). 9 The output is also stored by complex rows.Each row corresponds to a particular value of fi,as shown Progra in the figure.Within each row,the arrangement of frequencies is exactly as shown in Figure 12.2.2. A and A2 are the sampling intervals in the I and 2 directions,respectively.The total number of(real) CIENTIFIC array elements is 2NI N2.The program fourn can also do more than two dimensions,and the storage arrangement generalizes in the obvious way. product of the lengths of the L dimensions.It assumes that the array represents an L-dimensional complex array,with individual components ordered as follows: (i)each complex value occupies two sequential locations,real part followed by imaginary;(ii)the first subscript changes least rapidly as one goes through the array; 10-621 the last subscript changes most rapidly (that is,"store by rows,"the C norm):(iii) subscripts range from I to their maximum values (N1,N2,...,NL,respectively), 43106 rather than from 0 to N-1,N2-1,...,NL-1.Almost all failures to get fourn uction to work result from improper understanding of the above ordering of the data array, so take care!(Figure 12.4.I illustrates the format of the output array.) (outside North Software. #include <math.h> #define SWAP(a,b)tempr=(a);(a)=(b);(b)-tempr B void fourn(float data[],unsigned long nn[],int ndim,int isign) Replaces data by its ndim-dimensional discrete Fourier transform,if isign is input as 1. nn [1..ndim]is an integer array containing the lengths of each dimension (number of complex values),which MUST all be powers of 2.data is a real array of length twice the product of these lengths,in which the data are stored as in a multidimensional complex array:real and imaginary parts of each element are in consecutive locations,and the rightmost index of the array increases most rapidly as one proceeds along data.For a two-dimensional array,this is equivalent to storing the array by rows.If isign is input as-1,data is replaced by its inverse transform times the product of the lengths of all dimensions.12.4 FFT in Two or More Dimensions 523 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). row of 2N2 float numbers row 1 row 2 row N1/ 2 row N1/ 2 + 1 row N1/ 2 + 2 row N1 1 N1∆1 f1 = 0 f1 = f1 = f1 = − 1⁄ 2N1 − 1 N1∆1 1 N1∆1 f1 = ± 1 2∆1 f1 = − 1⁄ 2N1 − 1 N1∆1 data [1] Re Im data [2N1N2 ] Figure 12.4.1. Storage arrangement of frequencies in the output H(f1, f2) of a two-dimensional FFT. The input data is a two-dimensional N1 × N2 array h(t1, t2) (stored by rows of complex numbers). The output is also stored by complex rows. Each row corresponds to a particular value of f1, as shown in the figure. Within each row, the arrangement of frequencies f2 is exactly as shown in Figure 12.2.2. ∆1 and ∆2 are the sampling intervals in the 1 and 2 directions, respectively. The total number of (real) array elements is 2N1N2. The program fourn can also do more than two dimensions, and the storage arrangement generalizes in the obvious way. product of the lengths of the L dimensions. It assumes that the array represents an L-dimensional complex array, with individual components ordered as follows: (i) each complex value occupies two sequential locations, real part followed by imaginary; (ii) the first subscript changes least rapidly as one goes through the array; the last subscript changes most rapidly (that is, “store by rows,” the C norm); (iii) subscripts range from 1 to their maximum values (N1, N2,...,NL, respectively), rather than from 0 to N1 − 1, N2 − 1,..., NL − 1. Almost all failures to get fourn to work result from improper understanding of the above ordering of the data array, so take care! (Figure 12.4.1 illustrates the format of the output array.) #include <math.h> #define SWAP(a,b) tempr=(a);(a)=(b);(b)=tempr void fourn(float data[], unsigned long nn[], int ndim, int isign) Replaces data by its ndim-dimensional discrete Fourier transform, if isign is input as 1. nn[1..ndim] is an integer array containing the lengths of each dimension (number of complex values), which MUST all be powers of 2. data is a real array of length twice the product of these lengths, in which the data are stored as in a multidimensional complex array: real and imaginary parts of each element are in consecutive locations, and the rightmost index of the array increases most rapidly as one proceeds along data. For a two-dimensional array, this is equivalent to storing the array by rows. If isign is input as −1, data is replaced by its inverse transform times the product of the lengths of all dimensions