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 nearzero.\

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[0] - 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[0] - 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] = 0 which`

`is when i=0, R[i] = R[0].`

`but, given the definition with a finite sum (and the approximation for`

`R[i]), you actually don't know that that R[0] 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. Thisis 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 pitchdetection algorithms I've been looking at.In example code for the autocorrelation, it is the summation of asample 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 donot get a minima as expected when the samples match (I have triedwith a couple of generated periodic waves).However, if I use the summation of the differences I do get theminima 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 links http://music.columbia.edu/cmc/music-dsp http://music.columbia.edu/mailman/listinfo/music-dsp