Re: [music-dsp] Autocorrelation - probably a daft question

```
On Jan 25, 2011, at 7:34 PM, Jan Baumgart wrote:```
```
```
When the two signal portions are alike, they are strongly correlated - so you get a maximum value for the correlation. If they have "nothing in common" you get a correlation value near zero.\
```
he said he was using periodic function generation.

```
```For pitch detection you look for maxima in the auto-correlation.
```
```
```
yup, if P is the period (or *a* period - there is the "octave problem"), then
```
x[n+P] = x[n]  +  something very small

or

something very small =  x[n+P] - x[n]

or, making this error always positive....

|something very small| =  |x[n+P] - x[n]|          (AMDF)
or
(something very small)^2 =  (x[n+P] - x[n])^2      (ASDF)

```
Sum that up over n should result in something else quite small, if the offset i is equal to (or very close to) P. that's where the AMDF or ASDF get their answer.
```
```
for a very wide window (the "size" parameter), the ASDF can be shown to be related to the autocorrelation. in fact, it's the autocorrelation upside-down, so that when the ASDF is at a minimum, the autocorrelation is maximum.
```
```
SUM{ (x[n+i] - x[n])^2 } = SUM{ (x[n+i])^2 + (x[n])^2 - 2*x[n +i]*x[n] }
```
```
= SUM{ (x[n+i])^2 } + SUM{ (x[n])^2 } - 2*SUM{ x[n +i]*x[n] }
```
```
the first two summations sum to roughly the same thing (so the first summation isn't radically different for different i) which is a measure of the power or signal energy. the last summation is your autocorrelation which does depend on i a lot. so this is approximately true:
```
```
(1/2)*SUM{ (x[n+i] - x[n])^2 } = SUM{ (x[n])^2 } - SUM{ x[n +i]*x[n] }
```
Q[i]                =    R          -    R[i]

or

```
SUM{ x[n+i]*x[n] } = SUM{ (x[n])^2 } - (1/2)*SUM{ (x[n+i] - x[n])^2 }
```
R[i]     =       R        -            Q[i]

```
this would be exactly true if the summations where infinite, but the summations are finite, so this is only approximately true. one thing that can be said, even for the approximation, is that Q = 0 which is when i=0, R[i] = R.
```
```
but, given the definition with a finite sum (and the approximation for R[i]), you actually don't know that that R is at a maximum. but it should be close to a maximum. so find the maximum of R[i] around i=0 and when you find your other maximum (perhaps around i=P), then the difference in location of those two peaks should be your period, P.
```
think of this autocorrelation

R[i] = SUM{ x[n+i]*x[n] }  = SUM{ h[i-n]*x[n] }

```
as an FIR with this hypothetical "impulse response" h[n] = x[-n] (it's a time-reversed copy of the fixed leg of x[n] in your summation). the output of your autocorrelator is like that of an FIR filter. if a periodic x[n] (with period P) goes in, then a periodic R[n] comes out, with the same period, P. but that R[n] should have a peak around n=0, because it's sorta-kinda like a true autocorrelation. so the next peak should be P samples away from the peak around n=0 (but not necessarily exact on 0).
```
```
There's also the other way you mention, taking the difference. This is used in AMDF for example. In that case you look for minima.
```
yup, what he said.

--

r b-j                  r...@audioimagination.com

"Imagination is more important than knowledge."

```
```On 1/25/11 11:46 PM, Veronica Merryfield wrote:
```
I'm trying to understand autocorrelation as related to some pitch detection algorithms I've been looking at.
```
```
In example code for the autocorrelation, it is the summation of a sample at indexes multiplied by a sample at indexes plus an offset.
```
eg

for (i=0;i<size;i++)
{
sum=0;
for (j=0;j<size;j++)
{
sum+=x[j]*x[j+i];
}
R[i]=sum;
}

```
When I graph this (R[i]) in a spreadsheet for various offsets, I do not get a minima as expected when the samples match (I have tried with a couple of generated periodic waves).
```
```
However, if I use the summation of the differences I do get the minima as expected.
```
What am I missing?

Veronica

```
```--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp