12.1 Fourier Transform of Discretely Sampled Data 503 The remaining step is to approximate the integral in(12.0.1)by a discrete sum: N-1 N-1 H(fn)= h(t)e2≈hke2mifn△=△hx e2mikn/N k=0 k=0 (12.1.6) Here equations (12.1.4)and(12.1.5)have been used in the final equality.The final summation in equation (12.1.6)is called the discrete Fourier transform of the N points hk.Let us denote it by Hn, N-1 Hn≡ hk e2nikn/N (12.1.7) k=0 素 The discrete Fourier transform maps N complex numbers(the hk's)into N complex numbers(the Hn's).It does not depend on any dimensional parameter,such as the time scale A.The relation (12.1.6)between the discrete Fourier transform of a set of numbers and their continuous Fourier transform when they are viewed as samples of a continuous function sampled at an interval A can be rewritten as H(fn)≈△Hn (12.1.8) 鸟6 9 where fn is given by (12.1.5). Up to now we have taken the view that the index n in(12.1.7)varies from-N/2 to N/2 (cf.12.1.5).You can easily see,however,that(12.1.7)is periodic in n,with IENTIFIC period N.Therefore,Hn =HN-n n 1,2,....With this conversion in mind, one generally lets the n in Hn vary from 0 to N-1 (one complete period).Then n and k (in h)vary exactly over the same range,so the mapping of N numbers into N numbers is manifest.When this convention is followed,you must remember that zero frequency corresponds to n =0,positive frequencies 0<f<fe correspond to values 1 nN/2-1,while negative frequencies-fe<f<0 correspond to N/2+1<n N-1.The value nN/2 corresponds to both f fcand f=-fe. The discrete Fourier transform has symmetry properties almost exactly the same Recipes Numerica 10.621 as the continuous Fourier transform.For example,all the symmetries in the table 431 following equation (12.0.3)hold if we read hk for h(t),Hn for H(f),and HN-n (outside Recipes for H(-f).(Likewise,"even"and"odd"in time refer to whether the values h k at k and N-k are identical or the negative of each other.) The formula for the discrete imverse Fourier transform,which recovers the set North of hk's exactly from the Hn's is: N-1 hk一 e-2xikn/N (12.1.9) =0 Notice that the only differences between(12.1.9)and(12.1.7)are (i)changing the sign in the exponential,and (ii)dividing the answer by N.This means that a routine for calculating discrete Fourier transforms can also,with slight modification, calculate the inverse transforms.12.1 Fourier Transform of Discretely Sampled Data 503 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 remaining step is to approximate the integral in (12.0.1) by a discrete sum: H(fn) = ∞ −∞ h(t)e2πifnt dt ≈ N
−1 k=0 hk e2πifntk∆=∆ N
−1 k=0 hk e2πikn/N (12.1.6) Here equations (12.1.4) and (12.1.5) have been used in the final equality. The final summation in equation (12.1.6) is called the discrete Fourier transform of the N points hk. Let us denote it by Hn, Hn ≡ N
−1 k=0 hk e2πikn/N (12.1.7) The discrete Fourier transform maps N complex numbers (the h k’s) into N complex numbers (the Hn’s). It does not depend on any dimensional parameter, such as the time scale ∆. The relation (12.1.6) between the discrete Fourier transform of a set of numbers and their continuous Fourier transform when they are viewed as samples of a continuous function sampled at an interval ∆ can be rewritten as H(fn) ≈ ∆Hn (12.1.8) where fn is given by (12.1.5). Up to now we have taken the view that the index n in (12.1.7) varies from −N/2 to N/2 (cf. 12.1.5). You can easily see, however, that (12.1.7) is periodic in n, with period N. Therefore, H−n = HN−n n = 1, 2,... . With this conversion in mind, one generally lets the n in Hn vary from 0 to N − 1 (one complete period). Then n and k (in hk) vary exactly over the same range, so the mapping of N numbers into N numbers is manifest. When this convention is followed, you must remember that zero frequency corresponds to n = 0, positive frequencies 0 <f<f c correspond to values 1 ≤ n ≤ N/2 − 1, while negative frequencies −fc <f< 0 correspond to N/2+1 ≤ n ≤ N −1. The value n = N/2 corresponds to both f = f c and f = −fc. The discrete Fourier transform has symmetry properties almost exactly the same as the continuous Fourier transform. For example, all the symmetries in the table following equation (12.0.3) hold if we read h k for h(t), Hn for H(f), and HN−n for H(−f). (Likewise, “even” and “odd” in time refer to whether the values h k at k and N − k are identical or the negative of each other.) The formula for the discrete inverse Fourier transform, which recovers the set of hk’s exactly from the Hn’s is: hk = 1 N N
−1 n=0 Hn e−2πikn/N (12.1.9) Notice that the only differences between (12.1.9) and (12.1.7) are (i) changing the sign in the exponential, and (ii) dividing the answer by N. This means that a routine for calculating discrete Fourier transforms can also, with slight modification, calculate the inverse transforms.