13.2 Correlation and Autocorrelation Using the FFT 545 Brigham,E.O.1974,The Fast Fourier Transform(Englewood Cliffs,NJ:Prentice-Hall).Chap- ter 13. 13.2 Correlation and Autocorrelation Using the FFT 三 Correlation is the close mathematical cousin of convolution.It is in some ways simpler,however,because the two functions that go into a correlation are not g as conceptually distinct as were the data and response functions that entered into 2 convolution.Rather,in correlation,the functions are represented by different,but generally similar,data sets.We investigate their "correlation,"by comparing them Cam both directly superposed,and with one of them shifted left or right. We have already defined in equation (12.0.10)the correlation between two continuous functions g(t)and h(t),which is denoted Corr(g,h),and is a function of lag t.We will occasionally show this time dependence explicitly,with the rather 9 awkward notation Corr(g,h)(t).The correlation will be large at some value oft if the first function(g)is a close copy ofthe second(h)but lags it in time by t,i.e.,if the first function is shifted to the right of the second.Likewise,the correlation will be large for some negative value oft if the first function leads the second,i.e.,is shifted to the 9 left of the second.The relation that holds when the two functions are interchanged is Corr(g,h)(t)=Corr(h,g)(-t) (13.2.1) The discrete correlation of two sampled functions g and hk,each periodic with period N.is defined by N-1 Corr(g,h)≡g+khk (13.2.2) =0 Numerica 10.621 The discrete correlation theorem says that this discrete correlation of two real functions g and h is one member of the discrete Fourier transform pair Corr(g,h)方→GkHk* (13.2.3) North where G and Hk are the discrete Fourier transforms of g;and hj,and the asterisk denotes complex conjugation.This theorem makes the same presumptions about the functions as those encountered for the discrete convolution theorem. We can compute correlations using the FFT as follows:FFT the two data sets, multiply one resulting transform by the complex conjugate of the other,and inverse transform the product.The result(call it r)will formally be a complex vector of length N.However,it will turn out to have all its imaginary parts zero since the original data sets were both real.The components ofrk are the values of the correlation at different lags,with positive and negative lags stored in the by now familiar wrap-around order:The correlation at zero lag is in ro,the first component;13.2 Correlation and Autocorrelation Using the FFT 545 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). Brigham, E.O. 1974, The Fast Fourier Transform (Englewood Cliffs, NJ: Prentice-Hall), Chap￾ter 13. 13.2 Correlation and Autocorrelation Using the FFT Correlation is the close mathematical cousin of convolution. It is in some ways simpler, however, because the two functions that go into a correlation are not as conceptually distinct as were the data and response functions that entered into convolution. Rather, in correlation, the functions are represented by different, but generally similar, data sets. We investigate their “correlation,” by comparing them both directly superposed, and with one of them shifted left or right. We have already defined in equation (12.0.10) the correlation between two continuous functions g(t) and h(t), which is denoted Corr(g, h), and is a function of lag t. We will occasionally show this time dependence explicitly, with the rather awkward notation Corr(g, h)(t). The correlation will be large at some value of t if the first function (g) is a close copy of the second (h) but lags it in time by t, i.e., if the first function is shifted to the right of the second. Likewise, the correlation will be large for some negative value of t if the first function leads the second, i.e., is shifted to the left of the second. The relation that holds when the two functions are interchanged is Corr(g, h)(t) = Corr(h, g)(−t) (13.2.1) The discrete correlation of two sampled functions g k and hk, each periodic with period N, is defined by Corr(g, h)j ≡ N
−1 k=0 gj+khk (13.2.2) The discrete correlation theorem says that this discrete correlation of two real functions g and h is one member of the discrete Fourier transform pair Corr(g, h)j ⇐⇒ GkHk* (13.2.3) where Gk and Hk are the discrete Fourier transforms of gj and hj, and the asterisk denotes complex conjugation. This theorem makes the same presumptions about the functions as those encountered for the discrete convolution theorem. We can compute correlations using the FFT as follows: FFT the two data sets, multiply one resulting transform by the complex conjugate of the other, and inverse transform the product. The result (call it rk) will formally be a complex vector of length N. However, it will turn out to have all its imaginary parts zero since the original data sets were both real. The components of r k are the values of the correlation at different lags, with positive and negative lags stored in the by now familiar wrap-around order: The correlation at zero lag is in r 0, the first component;