I'm doing autocorrelation (via fft) on pure, synthetic generated sinusoids and getting unexpected jitter in the results. The jitter depend on where in the sine the signal buffer is started. I get the correct results if I start the buffer at 0 and 180 degrees of a sine wave, and get the most error at 90 and 270 degrees. I am padding with zeros after the signal buffer up to the next power of 2 above 2x-1 the signal buffer size.

I've been using scipy fftconvolve, as well as doing the auto-correlation with fft, multiply the results by it's complex conjugate, then inverse fft. I get the same results both ways. This makes me think I am not preparing my signal buffer properly or analyzing the autocorrelation function results correctly.

Below are two examples of autocorrelation of a 440hz signal. The signal buffer the autocorrelator is analyzing is enclosed by the two vertical lines, approximately two and a half periods and 256 samples at 44.1khz sample rate.

In the first example, the buffer is filled with the sine starting at 0 degrees. The result is 440.7 hz. enter image description here

In the second example, below, the buffer is filled with the sine starting at 90 degrees. The result is 453hz, a considerable error. enter image description here

Any ideas on why the error is so large in the second example?

  • $\begingroup$ Here is a possible error on my part. I'm assuming the autocorrelation results max peak is in the middle. Should I be searching for the exact max peak, then finding the distance to the next peak? $\endgroup$ Mar 11 '13 at 4:33
  • $\begingroup$ Also, I notice other peoples autocorrelation functions with equal amplitude peaks while mine have descending amplitude peaks. How is equal amplitude peaks achieved? $\endgroup$ Mar 11 '13 at 4:49
  • $\begingroup$ The autocorrelation function of a sinus function is again periodic. That is why you see the autocorrelation of other peoples having equal amplitude peaks. Maybe you are only observing a window? $\endgroup$ Mar 11 '13 at 9:52
  • $\begingroup$ Yes, I'm only autocorrelating 2 or 3 periods. That explains why the peaks are descending rapidly. $\endgroup$ Mar 11 '13 at 11:32
  • $\begingroup$ Maybe the errors depending on phase of sine in the signal buffer can be reduced by applying a windowing function. $\endgroup$ Mar 11 '13 at 12:45

The (periodic) autocorrelation function of a sinusoid $A\cos(2\pi f_0 t + \theta)$ is

$$\begin{align} R(\tau) &= \int_0^{f_0^{-1}} A\cos(2\pi f_0 t + \theta) A\cos(2\pi f_0 (t +\tau)+ \theta)\,\mathrm dt\\ &= \frac{A^2}{2}\int_0^{f_0^{-1}} \cos(2\pi f_0\tau)+\cos(2\pi f_0 (2t +\tau)+ \theta)\,\mathrm dt\\ &= \frac{A^2}{2f_0}\cos(2\pi f_0\tau) \end{align}$$ which has a peak at $\tau = 0$. Notice in particular that there is no dependence on $\theta$. More generally, if the integration is carried out over an interval $[0,T]$ of arbitrary length, we get $$\begin{align} \hat{R}(\tau) &= \int_0^{T} A\cos(2\pi f_0 t + \theta) A\cos(2\pi f_0 (t +\tau)+ \theta)\,\mathrm dt\\ &= \frac{A^2}{2}\int_0^{T} \cos(2\pi f_0\tau)+\cos(2\pi f_0 (2t +\tau)+ \theta)\,\mathrm dt\\ &= \frac{A^2T}{2}\cos(2\pi f_0\tau) + \left.\frac{A^2}{2}\frac{\sin(2\pi f_0 (2t +\tau)+ \theta)}{4\pi f_0}\right|_0^T\\ &= \frac{A^2T}{2}\cos(2\pi f_0\tau) + \frac{A^2}{2}\frac{\sin(2\pi f_0 (2T +\tau)+ \theta)-\sin(2\pi f_0\tau + \theta)}{4\pi f_0}\\ &= \frac{A^2T}{2} \left[\cos(2\pi f_0\tau) + \frac{\sin(2\pi f_0 (2T +\tau)+ \theta)-\sin(2\pi f_0\tau + \theta)}{4\pi f_0T}\right] \end{align}$$ which does depend on $\theta$ as well as $T$. Notice that if $T$ is an integer multiple $kf_0^{-1}$ of the fundamental period $f_0^{-1}$, then the second term in brackets disappears entirely and we get $$\hat{R}(\tau) = kR(\tau).$$ On the other hand, since the numerator in that second term cannot have value more than $2$, we get that if $T \gg f_0^{-1}$ but is not an integer multiple of $f_0^{-1}$, the second term is quite small in magnitude and so the autocorrelation function that one deduces from $\hat{R}(\tau)$ depends only very slightly on $\theta$.

With that as prologue, I point out to you that the FFT method of computing the autocorrelation function of a signal gives the periodic autocorrelation function of a segment of the signal, that is, what one gets is effectively an approximation to $\hat{R}_x(\tau)$ for a periodic signal $x(t)$ that is approximately $2.5$ periods of a sinusoid repeated over and over again. In particular, this periodic repetition is not the same as the sinusoid continuing smoothly and without break as one would want it to be for the above results to apply. Thus, it is not at all surprising that the results from the FFT method of computing the autocorrelation function depend more heavily on the phase of the sinusoid. In approximately $2.5$ periods, the $sin(\cdot)$ goes from $0$ at $t=0$ to nearly $0$ again at the end of nearly $2.5$ periods. Thus, the periodic extension is nearly continuous (though there is an abrupt change of phase at the transition). On the other hand, with a $90$-degree phase shift, $\cos(\cdot)$ goes from $1$ at $t = 0$ to nearly $-1$ at the end of nearly $2.5$ periods, and so the periodic extension is very discontinuous. This shows up in the FFT results which don't get a good estimate of the frequency in the latter case.

If you take the frequency of the sinusoid to be be such that an integer number of cycles fit into the $N$ that you are using for your FFT, these artifacts will disappear.

  • $\begingroup$ Thanks for that detailed explanation. Unfortunately, I'm trying to estimate the fundamental of an unknown signal so I can only size the buffer to handle a range of frequencies, from 80hz, to 2Khz. If there is no way around this problem, I'll mark your answer as the accepted solution. $\endgroup$ Mar 11 '13 at 17:04
  • $\begingroup$ This result makes auto-correlation useless if one wants a good estimate over a range of frequencies. I wonder if a windowing function applied before the fft would soften the discontinuities? $\endgroup$ Mar 11 '13 at 17:22
  • $\begingroup$ This link says one should not use windowing functions in fft based autocorrelation: link $\endgroup$ Mar 11 '13 at 17:48

FFT-based autocorrelation gives you a circular autocorrelation, which will be phase dependent for any waveform not perfectly periodic in the FFT aperture width, due to the discontinuity at the wrap-around points.

What you could try instead is a (FFT fast) cross-correlation between a zero-padded copy of the data against a longer unpadded vector of the same data source. If the zero-padding is longer than the period, then the circular effects will be removed (similar to the effect of zero-padding for fast convolution) for some range of lags. If you expect noise, then you might also want to try windowing just the portion of the data to be zero-padded.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.