c13-1 (Numerical Recipes in C), страница 3

Now you overlap and add these sections of output. Thus, an outputpoint near the end of one section will have the response due to the input points atthe beginning of the next section of data properly added in to it, and likewise for anoutput point near the beginning of a section, mutatis mutandis.Even when computer memory is available, there is some slight gain in computingspeed in segmenting a long data set, since the FFTs’ N log2 N is slightly slower thanlinear in N . However, the log term is so slowly varying that you will often be muchhappier to avoid the bookkeeping complexities of the overlap-add or overlap-savemethods: If it is practical to do so, just cram the whole data set into memory andFFT away. Then you will have more time for the finer things in life, some of whichare described in succeeding sections of this chapter.CITED REFERENCES AND FURTHER READING:Nussbaumer, H.J.

1982, Fast Fourier Transform and Convolution Algorithms (New York: SpringerVerlag).Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).B54513.2 Correlation and Autocorrelation Using the FFTElliott, D.F., and Rao, K.R. 1982, Fast Transforms: Algorithms, Analyses, Applications (NewYork: Academic Press).Brigham, E.O. 1974, The Fast Fourier Transform (Englewood Cliffs, NJ: Prentice-Hall), Chapter 13.Correlation is the close mathematical cousin of convolution.

It is in someways simpler, however, because the two functions that go into a correlation are notas conceptually distinct as were the data and response functions that entered intoconvolution. Rather, in correlation, the functions are represented by different, butgenerally similar, data sets. We investigate their “correlation,” by comparing themboth directly superposed, and with one of them shifted left or right.We have already defined in equation (12.0.10) the correlation between twocontinuous functions g(t) and h(t), which is denoted Corr(g, h), and is a functionof lag t. We will occasionally show this time dependence explicitly, with the ratherawkward notation Corr(g, h)(t). The correlation will be large at some value oft if the first function (g) is a close copy of the second (h) but lags it in time byt, i.e., if the first function is shifted to the right of the second. Likewise, thecorrelation will be large for some negative value of t if the first function leads thesecond, i.e., is shifted to the left of the second.

The relation that holds when thetwo functions are interchanged isCorr(g, h)(t) = Corr(h, g)(−t)(13.2.1)The discrete correlation of two sampled functions gk and hk , each periodicwith period N , is defined byCorr(g, h)j ≡N−1Xgj+k hk(13.2.2)k=0The discrete correlation theorem says that this discrete correlation of two realfunctions g and h is one member of the discrete Fourier transform pairCorr(g, h)j ⇐⇒ Gk Hk *(13.2.3)where Gk and Hk are the discrete Fourier transforms of gj and hj , and the asteriskdenotes complex conjugation.

This theorem makes the same presumptions about thefunctions 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 inversetransform the product. The result (call it rk ) will formally be a complex vectorof length N . However, it will turn out to have all its imaginary parts zero sincethe original data sets were both real. The components of rk are the values of theSample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).13.2 Correlation and Autocorrelation Usingthe FFT.