circular convolution - why the third argument - what is the use?

"Circular convolution is used to convolve two discrete Fourier transform (DFT) sequences." MATLAB documentation says this. To me, circular convolution is an operation on any sequences. whether time or DFT or some thing else. Also, circular convolution is defined for 2 sequences of equal length and the output also would be of the same length. But cconv(a,b,n) has three parameters. It could have been simply cconv(a,b). Take 2 sequences a and b find the circular convolution by padding zeros to the smaller sequence to make the lengths equal. Is there any thing that we are gaining from the third parameter flexibility? I have studied the effect. For example, with 2 sequences of length say 10 and giving cconv(a,b,4). Where is this kind of computation useful?

Answer 1

[Chris Turnes]

The third argument of cconv is used to control the length of the result of the convolution. To calculate what would typically be viewed as the circular convolution of two signals of length n, the third argument must be supplied:

c = cconv(a,b,n);

If the third argument is not supplied,

d = cconv(a,b);

will return the result of the linear convolution of a and b, which is equal to the circular convolution of a and b after they have been padded with n-1 zeroes each. For more on the differences between these operations, please refer to this article.

In fact, this is the reason why the third argument is useful. The circular convolution function cconv and the linear convolution function conv use different algorithms to perform their calculations. Since the third argument of cconv allows it to perform either circular or linear convolution, there are scenarios for which it will be more efficient to use cconv to compute a linear convolution than conv.

As an example, notice the difference in execution times for the two algorithms for two similar problems on my system. First, a problem where one signal is considerably smaller than the other:

>> a = randn(129996, 1);
>> b = randn(4, 1);
>> for i = 1:3, conv(a,b); end %--warmups
>> tic; conv(a,b); toc
Elapsed time is 0.000579 seconds.
>> for i = 1:3, cconv(a,b); end %--warmups
>> tic; cconv(a,b); toc
Elapsed time is 0.009817 seconds.

Then, a problem where both signals have the same length:

>> a = randn(65000,1);
>> b = randn(65000,1);
>> for i = 1:3, conv(a,b); end %--warmups
>> tic; conv(a,b); toc
Elapsed time is 0.502528 seconds.
>> for i = 1:3, cconv(a,b); end %--warmups
>> tic; cconv(a,b); toc
Elapsed time is 0.011336 seconds.

The convolution in each problem produces a signal of the same length, but the algorithm in cconv is far more efficient than conv for the latter problem.

[Seetha Rama Raju Sanapala]

But I have got contrary results. Please comment.

first_sequence_length=20; second_sequence_length=20; REPEAT_NUMBER=100; t1=zeros(1,REPEAT_NUMBER); t2=zeros(1,REPEAT_NUMBER); x=1:REPEAT_NUMBER; for i=1:REPEAT_NUMBER; a=randperm(first_sequence_length); b=randperm(second_sequence_length); tic;conv(a,b);t1(i)=toc; tic;cconv(a,b);t2(i)=toc; clear a b; end plot(x,t1,'r',x,t2,'b')

Even though both the sequences are of equal length, cconv seems to take almost double the time as conv.

[Chris Turnes]

This is a good point. I did not mean to suggest that cconv is always faster than conv when the signals have equal length. In the example I gave, both signals were considerably longer than 20 samples.

Since the two algorithms have different overhead costs, when both signals are relatively small conv may outperform cconv. However, as the signal lengths increase, there will be some point where cconv becomes preferable in terms of execution time.

For example, I can run the following experiment on my computer:

% exponential increase in signal size
N = 2*10.^(1:5);
tconv = zeros(length(N), 1);
tcconv = zeros(length(N), 1);
for i = 1:length(N);
   % construct random signals
   a = randn(N(i), 1);
   b = randn(N(i), 1);
   % warmups
   for j = 1:3; conv(a,b); end;
   % average "conv" execution time over 10 trials
   tic; for j = 1:10; conv(a,b); end;
   tconv(i) = toc / 10;
   % warmups
   for j = 1:3; cconv(a,b); end;
   % average "cconv" execution time over 10 trials
   tic; for j = 1:10; cconv(a,b); end;
   tcconv(i) = toc / 10;
end

and when I compare the average execution times, I see:

>> [tconv, tcconv]

ans =

     2.7592e-05   1.0256e-04
     1.1447e-04   1.0497e-04
     1.0001e-03   4.2639e-04
     4.3004e-02   7.4970e-03
     3.5894e+00   4.1021e-02

So, for my machine, the two algorithms run in roughly the same time for signals up to length 200, and for longer signals cconv is preferable.