Elliott, ., and Rao, . 1982, Fast Transforms: Algorithms, Analyses, Applications (New York: Academic Press). Brigham, . 1974, The Fast Fourier Transform (Englewood Cliffs, NJ: Prentice-Hall), Chapter 13. | 132 Correlation andAutocorrelation Using the FFT 545 Elliott . and Rao . 1982 Fast Transforms Algorithms Analyses Applications New York Academic Press . Brigham . 1974 The Fast Fourier Transform Englewood Cliffs NJ Prentice-Hall Chapter 13. Correlation andAutocorrelation 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 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 Corri 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 . 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 . 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 The discrete correlation of two sampled functions gk and hk each periodic with period N is defined by N-1 Corr g h j X gj khk k 0 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 C21G 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 .
