Difference between 'conv' & ifft(fft) when doing convolution?

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

[Eran]

fft is cyclic therefore padding is needed

Answer 1

[Wayne King]

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

[Q L]

Get it now. Thanks, Wayne.

However, I'm still not sure about the last question I've raised:

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. Should I just use the first half or the second half of con(x,y) to present z(t)?

Thanks again!

[Fu Bin]

But I think there is also a problem what I faced. For example,

x = [5,6777777777777,333,7,8];

 y = [5,67,3334444444444,7,8];

 x1 = [x zeros(1,4)];

 y1 = [y zeros(1,4)];

 c1 = ifft(fft(x1).*fft(y1));

 c2 = conv(x,y);
for these code, why c1 and c2 not equal?

[Csanad Levente Balogh]

Hi @Wayne King!

This solution works perfect if I know the time domain signals, but what if I only have the spectrum of the signals? I have a problem, where I only have the two spectrums and I should calculate the convolution. I tried it with two spectrums, where I know what the result should be.

x some spectrum
y some other spectrum
z result of x.*y

res1 = conv(ifft(x),ifft(y));
res2 = ifft(z);

Now the two results have a huge amplitude difference.

(Actually my goal would be to then convert the result of the convolution back to frquency domain like:

RES = fft(res1);

maybe it helps if this is the final goal)

How would you account for the difference between linear and circular convolution in this case? How can you acquire the resulting signal with the right amplitude?

Answer 2

[Wayne King]

Hi, No, the result should not obviously be the same length. The result should be the length of x plus the length of y -1: length(x)+length(y)-1. In your case you get 19 and that is absolutely correct for linear convolution.

[Q L]

Thanks for your quick response. Sorry but I'm still a little confused. If t is of length 10, the length of z(t) should also be 10, while the length of the convolution result is 19 --- then how can I map the result to z(t)??

[Wayne King]

This forum does not lend itself to presenting you the proof, but I promise you, it is easy to show. Just assume you have two sequences, one of length L and another of length M, if you work out the summation, you will see that the resulting linear convolution has length L+M-1.

[Q L]

Hi, Wayne, thanks for your answers. I was asking the question in signal processing domain. Please see my post below.

[Wayne King]

I gave you the answer. Go back up and look at my post just below your original question. It has now moved up because it got two votes. Please read it, it is THE answer.

Answer 3

[Wayne King]

Here is a demonstration, not a proof, which is not hard. But assume you have two length 3 vectors, if you reverse one with respect to the other and shift, you will see that you will get 5 (3+3-1) products in the convolution. That is where the 5 terms come from (leaving out the summation)

 x = [1 2 3];
 y = [4 5 6];

Illustration of the 5 element-by-element products (summing produces the convolution)

     1 2 3
 6 5 4         %first element is 4

     1 2 3  
   6 5 4       %2nd element is 5+8

     1 2 3
     6 5 4     %3rd element is 6+10+12

     1 2 3
       6 5 4   %4th element is 12+15

     1 2 3
         6 5 4 %5th element is 18

Answer 4

[Guo]

Hi,I feel your question is very special.And I think you may mistake the 't',which may be different in signal processing and math function.Here 't' is just a subscript or signal order which has no negative value and is not a independent variable,so it's different from one within a mathematical function.Even though for a math problem,the domain of definition can be different before and after the computation.

[Q L]

Sorry I didn't put my point very clearly. Absolutely I was asking the question in signal processing domain. 't' represents 'time', ranges from 0 to t0. x(t) and y(t) are both continuous functions. z(t) is the convolution of x(t) and y(t) in [0 t0].

Obviously I need to digitalize t, x(t) and y(t) before operating convolution in matlab. Then how can I get z(t) (t is from 0 to t0)?

Thanks a lot for your help.

[Wayne King]

Even for square-integrable functions of a continuous variable, the convolution of those functions does NOT usually have the same support as the two individual functions. If you convolve two rectangles with support [0,1], In other words, f(t) = 1 0<=t<=1, the resulting convolution does not have support on [0,1]

[Q L]

I know what you mean now. Problem solved. Thanks again!

[ww]

Hi QL,

I have the same problem with you.

In signal processing, the time range t is fixed, but after convolution, the length is bigger than time range.

how did you solve this problem?

Thanks

Answer 5

[MD RASEL MIAH]

[MD RASEL MIAH]

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)); we can use this 1 st queastion answer