I've found on multiple sites that convolution and cross-correlation are similar (including the tag wiki for convolution), but I didn't find anywhere how they differ.
What is the difference between the two? Can you say that autocorrelation is also a kind of a convolution?
Answer
The only difference between cross-correlation and convolution is a time reversal on one of the inputs. Discrete convolution and cross-correlation are defined as follows (for real signals; I neglected the conjugates needed when the signals are complex):
$$ x[n] * h[n] = \sum_{k=0}^{\infty}h[k] x[n-k] $$
$$ corr(x[n],h[n]) = \sum_{k=0}^{\infty}h[k] x[n+k] $$
This implies that you can use fast convolution algorithms like overlap-save to implement cross-correlation efficiently; just time reverse one of the input signals first. Autocorrelation is identical to the above, except $h[n] = x[n]$, so you can view it as related to convolution in the same way.
Edit: Since someone else just asked a duplicate question, I've been inspired to add one more piece of information: if you implement correlation in the frequency domain using a fast convolution algorithm like overlap-save, you can avoid the hassle of time-reversing one of the signals first by instead conjugating one of the signals in the frequency domain. It can be shown that conjugation in the frequency domain is equivalent to reversal in the time domain.
No comments:
Post a Comment