fft - Intuitive explanation of cross-correlation in frequency domain

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!

Answer

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)$.