Cross correlation with FFT and fftshift

Question

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.

Answer 1

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.