Topic: Cross-correlation, correlation and how does it work? (Read 7410 times)
0 Members and 1 Guest are viewing this topic.

## Cross-correlation, correlation and how does it work?

##### 2010-11-11 17:26:51
Greetings.

I have a task to find the shift in two wave files which are almost similar (one is the decoded mp3 encode of another, which introduces delay).

From what i did read here http://www.bores.com/courses/intro/time/2_ave.htm i can use correlation of the two to get the shift value.
The point where correlation function will be maximised will mean the value i need to shift one waveform in time to match the other.

Now, the problem is, here http://www.bores.com/courses/intro/time/2_ave.htm it says i should multiply function 1 by function 2, but here http://en.wikipedia.org/wiki/Cross-correlation it says i should multiply function by its complex conjugate.

How do complex numbers relate here i just dont understand at all.
Does it mean i must take minus of one of the functions?
Also, why is this called cross-correlation in one place and just correlation in another?
Which one is correct?

Because so far i am getting strange results (totally different maximum points for different channels, although channels are synced in both waves), and i think this is because i am trying to calculate wrong thing...

## Cross-correlation, correlation and how does it work?

##### Reply #1 – 2010-11-11 17:47:17
There are two kinds of correlation. Cross correlation is the correlation between two separate functions, while auto correlation is the correlation of a function against itself.

Auto correlation is used to discover periodicity within a function, i.e. in addition to a peak at zero shift, there will be additional peaks at whatever period there is periodicity.

Cross correlation is usually applied to find the offset between two similar but time-shifted functions, as you are using it.

Simply referring to correlation is sloppy, but cross correlation is more commonly used than auto correlation so that it what it most likely refers to.

## Cross-correlation, correlation and how does it work?

##### Reply #2 – 2010-11-11 20:26:37
How do complex numbers relate here i just dont understand at all.

Your functions are real. The complex conjugate of a real number is the same number.

## Cross-correlation, correlation and how does it work?

##### Reply #3 – 2010-11-12 00:25:52
There's so many things in this I hardly know hwere to start.

1) normalize (make energy per some unit of time ==1)
2) take sum( x * y) where x and y are the two signals, and * means pointwise multiply.
3) shift y by 1, repeat.

Find out where the peak lies. that's your delay, give or take noise.

You can also do this in the Fourier domain.

you can also deconvolve in the Fourier domain, but of course signals with zeros create interesting problems

Hmm.

There's a whole semester class here...
-----
J. D. (jj) Johnston

## Cross-correlation, correlation and how does it work?

##### Reply #4 – 2010-11-12 09:08:58
Ah thanks, i see, complex conjugate is only needed when we have complex functions because otherwise i*i would provide -1...
And cross corellation is just to separate correlation from auto-corellation...

Thanks i understand now.

But now specific question: Should corellation of wave file with anothe wave file, which was coded in 320kbit/s mp3 and then decoded back, give me the peak that will indicate the shift introduced by mp3 encoding& (http://www.hydrogenaudio.org/forums/index.php?showtopic=84875)
Because right now the corellation of wave file with same wave file, shifted in time, indeed peaks at the shift (for both channels), but corellation of wave and encoded-decoded wave gives peaks at different shifts for different channels!

## Cross-correlation, correlation and how does it work?

##### Reply #5 – 2010-11-12 09:35:36
But now specific question: Should corellation of wave file with anothe wave file, which was coded in 320kbit/s mp3 and then decoded back, give me the peak that will indicate the shift introduced by mp3 encoding& (http://www.hydrogenaudio.org/forums/index.php?showtopic=84875)

Yes, it will. Just beware that this shift may be a few hundred or even thousand samples.

## Cross-correlation, correlation and how does it work?

##### Reply #6 – 2010-11-12 09:58:58
Often it's not necessary to process the whole file - the delay is fixed, so you can just process part of it, unless there are strictly periodic signals in the file which correlate with themselves and give false peaks. In that case you may need the whole file to be sure of getting the right result.

What you're trying to do usually works, but it's not the only way to account for these delays. The delays of most mp3 encoders and decoders are known and fixed. You don't need to re-calculate them every time.

http://mp3decoders.mp3-tech.org/decoders_lame.html#delays

lame and fb2k can now correct for the delays automatically, removing the problem entirely if they are used.

The fool-proof method I often use is to add an impulse (click) to the start and (near the) end of the file before encoding. You just look at the sample number the click appears at after decoding; that's the delay. Job done. The click at the end can be checked to ensure nothing funny happened due to a broken encoder or decoder, if you're paranoid.

Hope this helps.

Cheers,
David.