## Friday, 31 January 2014

### Fast Calculation of Autocorrelation Coefficients in Julia

Autocorrelation is one of those things that gets used a lot in signal processing which has a very simple formula, but which is easy to speed up. In essence, autocorrelation is a measure of how similar a signal is to itself. Periodic signals are exactly those signals that are self-similar, so autocorrelation is good for locationg periodicities. The basic formula for autocorrelation of a signal $$x(i)$$ is:

$R_{xx}(j) = \sum_{i=0}^N x(i)x(i-j)$

In the above equation, $$R_{xx}(j)$$ is the notation for the $$j^{th}$$ autocorrelation coefficient of signal $$x$$, where $$x$$ is of length $$N$$ samples. Note that the above equation is $$O(N^2)$$ in complexity if we want all the autocorrelation coefficients (of which there are around $$2N - 1$$ ). To speed it up, we are going to use the Wiener–Khinchin theorem, which states that the power spectrum of a signal and the autocorrelation sequence of a signal are related to each other via the Fourier Transform (FFT). This means:

$S_{xx} = FFT(R_{xx})$

and

$R_{xx} = IFFT(S_{xx}) = IFFT( |FFT(x)|^2 )$

where $$S_{xx}$$ is the power spectrum of our signal $$x$$. Note that the complexity of the FFT is $$O(n\log n)$$, so this is a significant speedup over the original equation. This means our code for fast autocorrelation is simply:

Alternatively, Julia provides a xcorr function for computing cross correlation, to produce the same output as the function above, you would need: xcorr(x,x)[length(x):], this is the preferred way of achieving it.