12
$\begingroup$

According to the cross-correlation theorem : the cross-correlation between two signals is equal to the product of fourier transform of one signal multiplied by complex conjugate of fourier transform of another signal. After doing this, when we take the ifft of the product signal, we get a peak which indicates the shift between two signals.

I am not able to understand how this works? Why would i get a peak which indicates the shift between two signals. I got the math from : http://mathworld.wolfram.com/Cross-CorrelationTheorem.html but i am not able to understand as to what this means intuitatively. Can somebody please provide some explanation or point me to the right documents?

Thanks!

$\endgroup$
  • $\begingroup$ Thanks Dilip. I understand i will be getting multiple peaks. What does each of this peak indicate? And why would you get multiple peaks when you take the ifft? I have read mathematical proof about cross-correlation theorem but i don't understand how to interpret it. More like what would multiplying FT of one signal with conjugate of another one indicate? what is the physical significance of it? $\endgroup$ – silver surfer Apr 20 '15 at 12:44
  • $\begingroup$ The code is not working .The code ends up with some error like index exceed the matrix dimension even though the x and y were given as 100 and l=50 $\endgroup$ – Athira Nov 20 '17 at 5:14
10
$\begingroup$

The concept is based on the convolution theorem, which states that for two signals $x(t)$ and $y(t)$, the product of their Fourier transforms $X(f)$ and $Y(f)$ is equal to the Fourier transform of the convolution of the two signals. That is:

$$ \mathcal{F}\{x(t) * y(t)\} = \mathcal{F}\{x(t)\}\mathcal{F}\{y(t)\} $$

You can read more on the derivation of this theorem at the above Wikipedia link. Now, convolution is a very important operation for linear systems in itself, so the theory on its properties is well-developed.

However, what you're looking for is the cross-correlation between $x(t)$ and $y(t)$. Here's the key: you the cross-correlation integral is equivalent to the convolution integral if one of the input signals is conjugated and time-reversed. This allows you to utilize theory developed for evaluating convolutions (like frequency-domain techniques for calculating them quickly) and apply them to correlations.

In your example, you're calculating the following:

$$ \mathcal{F}\{x(t)\}\left(\mathcal{F}\{y(t)\}\right)^* $$

Recall that in the Fourier domain, complex conjugation is equivalent to time reversal in the time domain (this follows directly from the definition of the Fourier transform). Therefore, using the first equation given above, we can state that:

$$ \mathcal{F}\{x(t) * y^*(-t)\} = \mathcal{F}\{x(t)\}\left(\mathcal{F}\{y(t)\}\right)^* $$

If you then take the inverse Fourier transform of this equation, the signal you're left with is the cross-correlation between $x(t)$ and $y(t)$.

$\endgroup$
-1
$\begingroup$
% Matlab function for frequency domain cross correlation
function [Lag,C]=xcorrf(X,Y,L)
% X, Y ---> Input vectors 
% L --->  maximum lag (must be less than minimum of (length of X, Y)
% C ---> correlation vector
% Lag ---> lag times  
X=X(:);
Y=Y(:);
s1=size(X);
s2=size(Y);
D=min(s1(1,1),s2(1,1));
for i=1:L
    X1=ifft(fft(X(1:D-i,:)).*conj(fft(Y(i+1:D,1))));
    C(i,1)=X1(1,1);
end

C=flipud(C);
X1=ifft(fft(X(1:D,:)).*conj(fft(Y(1:D,1))));
C(L+1,1)=X1(1,1);
for i=1:L
    X1=ifft(fft(Y(1:D-i,:)).*conj(fft(X(i+1:D,1))));
    C(i+L+1,1)=X1(1,1);
end
Lag=-L:1:L;
end
$\endgroup$
  • 1
    $\begingroup$ Can you please edit your response with a bit more information about how the code is supposed to be answering the original poster's question? $\endgroup$ – A_A Sep 21 '16 at 11:26
  • $\begingroup$ I think I see where he is going with this code but I have to say that if you ran this code with any vectors X and Y over 100 samples in length, you would have to make a cup of tea while you wait. $\endgroup$ – crowie May 21 '17 at 14:41
  • $\begingroup$ Code alone is not an answer $\endgroup$ – tobassist Mar 1 '18 at 14:03

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.