18.8.2 Algorithms (Correlation)

Fast algorithm for Correlation

Correlation is computed using a fast algorithm based on the correlation theorem.

Let f(n) and g(n) be the input signals and y(m) denote the output, then we have:

$y(m)=\sum_{n=0}^{M-1}f(n)g(n-m)=ifft(FG^{*})\,\!$

where F is the Fourier transform of f(n), G is the Fourier transform of g(n) and * means complex conjugation. Therefore the computation of correlation is actually carried out as follows:

The discrete Fourier transforms of f(n) and g(n) are computed using FFT;
Multiply the Fourier coefficients of f(n) with the conjugated coefficients of g(n);
Perform inverse discrete Fourier transform on the product.

If the Normalize checkbox is selected, the two input signals are first normalized before the correlation is computed.

The normalization is as follows:

$f_{norm}(n)=\frac{f(n)}{\sqrt{\sum _{i=0}^{M-1}(f(n))^2}}\,\!$ and $g_{norm}(n)=\frac{g(n)}{\sqrt{\sum_{i=0}^{M-1}(g(n))^2}} \,\!$

The normalized correlation can be computed as:

$y(m)=\sum_{i=0}^{M-1}f_{norm}(n)g_{norm}(n)=ifft(F_{norm}G_{norm}^{*}) \,\!$

where $F_{norm}$ is the Fourier transform of fnorm(n), $G_{norm}$ is the Fourier transform of $gnorm(n)$ and * means complex conjugation.

Note that if linear correlation is computed, zero padding will be performed before the computation of FFT.

Automatic Computation of Sampling Interval

When <Auto> is selected for Sampling Interval, the sampling interval needed in the computation is computed automatically by Origin.

The automatically computed sampling interval is the average increment of the time sequence, which is usually from the X column associated with the input signal. If there is no associated X column, the row numbers will be used. Note that if Origin fails to get the average increment, the sampling interval will be set to 1.