4
$\begingroup$

When I calculate the cross correlation between two vectors with the following code

a = [1 2 3 4 5];
b = [6 9 8 9 10];

% correlation using convolution
conv(a,conj(flipdim(b,2)))
% correlation using FFT
ifft(fft(a,9).*conj(fft(b,9)))
fftshift(ans)

when I use the FFT i need to fftshift the output in order to get the correct cross correlation:

ans = 10    29    56    92   134   116    94    69    30

ans = 134.0000  116.0000   94.0000   69.0000   30.0000   10.0000   29.0000   56.0000   92.0000

ans = 10.0000   29.0000   56.0000   92.0000  134.0000  116.0000   94.0000   69.0000   30.0000

However, if i just calculate the convolution of the two vectors using the FFT I don't need to apply the ffshift

 conv(a,b)
 ifft(fft(a,9).*fft(b,9))

ans = 6    21    44    76   118   124   106    85    50

ans = 6.0000   21.0000   44.0000   76.0000  118.0000  124.0000  106.0000   85.0000   50.0000

Why do I need to do a fftshift when calculating the cross correlation? I guess it must be very obvious but I just don't see it right now and I've been googling for hours.

$\endgroup$
7
$\begingroup$

The (linear or aperiodic) convolution of two vectors $\mathbf x = (x[0], x[1], \ldots, x[N-1])$ and $\mathbf y = (y[0], y[1], \ldots, y[N-1])$ is a vector $$\mathbf z = {\mathbf x}\star {\mathbf y} = (z[0], z[1], \ldots, z[2N-1]).$$ On the other hand, their cross-correlation is a vector $$\mathbf w = {\mathbf x}\otimes {\mathbf y} = (w[-(N-1)], w[-(N-2)], \ldots, w[-1], w[0], w[1], \ldots, w[N-2], w[N-1]).$$ Now, the FFT method for computing convolutions computes the cyclic (a.k.a. periodic or circular) convolution of the two vectors. To compute the linear or aperiodic convolution via FFTs, you zero-pad the vectors to length $2N-1$ so that the cyclic convolution of the zero-padded vectors is exactly the linear convolution you are looking for. Thus, after FFTing, term-by-term multiplying, and inverse-FFTing, what you get is $\mathbf z$. This is exactly what you have done as per your question. However, when you use the FFT method to compute the cross-correlation, what you get is the cyclic cross-correlation of the two zero-padded vectors, and this cyclic cross-correlation is not $\mathbf w$ but instead $$\hat{\mathbf w} = (w[0], w[1], \ldots, w[N-1], w[-(N-1)], w[-(N-2)], \ldots, w[-2], w[-1])$$ so that to get the $\mathbf w$ that you want, you need to circularly rotate $\hat{\mathbf w}$ so that $w[0]$ appear in the middle of the vector.

$\endgroup$
  • $\begingroup$ Thanks, your answer helped a lot. I get now that, since with the FFT method you are calculating the circular convolution, the signals don't wrap around at the end thanks to the additional zeros. However, when calculating the cross-correlation with the FFT/convolution, one of the signals is reversed (and conjugated) and, consequently, it does wrap around when it reaches the end. $\endgroup$ – Pedro G. Nov 13 '13 at 14:35

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.