MATLAB: Difference between ‘conv’ & ifft(fft) when doing convolution

convolutionfft

Hi, I'm trying to obtain convolution of two vectors using 'conv' and 'fft' function in matlab. For example:
%%Example 1;
x = [1 2 3 4 0 0]; y = [-3 5 -4 0 0 0];
con_xy1 = conv(x,y);
con_xy2 = ifft(fft(x).*fft(y));
Results: >> con_xy1
con_xy1 =
    -3    -1    -3    -5     8   -16     0     0     0     0     0
>> con_xy2
con_xy2 =
   -3.0000   -1.0000   -3.0000   -5.0000    8.0000  -16.0000
Obviously, the first six values in con_xy1 is identical to con_xy2. However, when I use another two vectors, the results are totally different:
   %%Example 2
x = [5 6 8 2 5]; y = [6 -1 3 5 1];
con_xy1 = conv(x,y);
con_xy2 = ifft(fft(x).*fft(y));
Results: >> con_xy1
con_xy1 =
    30    31    57    47    87    47    33    27     5
>> con_xy2
con_xy2 =
    77    64    84    52    87
*My first question is: comparing example 1 and 2, why 'conv' and 'ifft(fft)' yields identical results in example 1 but not example 2？Is it because vectors in example 1 contain zeros at the end？Theoretically they should be identical, no matter what 'x' and 'y' are, am I right? *
Then, I try to apply 'fft(x,n)' instead of 'fft(x)' (I assigned 'n' in fft). It becomes:
%%Example 3:
x = [5 6 8 2 5]; y = [6 -1 3 5 1];
con_xy1 = conv(x,y);
con_xy2 = ifft(fft(x,16).*fft(y,16));
Results: >> con_xy1
con_xy1 =
    30    31    57    47    87    47    33    27     5
>> con_xy2
con_xy2 =
Columns 1 through 11
   30.0000   31.0000   57.0000   47.0000   87.0000   47.0000   33.0000   27.0000    5.0000    0.0000         0
Columns 12 through 16
         0         0         0   -0.0000         0
In this case, the non-zero values in con_xy2 are identical to con_xy1.
*My second question is: according to example 2 and 3, should we always assign a large enough number to 'n' to make 'fft' accurate? *
My last question: how do we understand convolution in matlab? For example: now we have two functions: x(t) and y(t), and t = 1:1:10, we want to get z(t) = x(t)*y(t).
Obviously, length of z(t) should be the same as t, x(t) and y(t), i.e. 10. But if we use 'conv' function, we will get a result of length 2*10-1 = 19; if we use 'ifft(fft)', we will get a result of length 10 – the same length as x and y; if we use 'ifft(fft(x,n))', the result will be length n – the number we assigned.
I'm totally confused: how can I obtain real 'z(t)'?? Should I just use the first half or the second half of con(x,y) to present z(t)?
Please help. Thanks in advance!!
Best Regards, Q.L

Best Answer

You have to keep in mind that the product of the DFTs of two vectors is Fourier transform of the circular convolution, not linear convolution. To establish equivalence between linear and circular convolution, you have to extend the vectors appropriately first before computing the circular convolution. The length of the linear convolution of two vectors of length, M and L is M+L-1, so we will extend our two vectors to that length before computing the circular convolution using the DFT.
 x = [5 6 8 2 5]; 
 y = [6 -1 3 5 1];
 x1 = [x zeros(1,4)];
 y1 = [y zeros(1,4)];
 c1 = ifft(fft(x1).*fft(y1));
 c2 = conv(x,y);
Now compare c1 and c2
Related Question