circular convolution - why the third argument - what is the use?
21 次查看(过去 30 天)
显示 更早的评论
"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?
0 个评论
采纳的回答
Chris Turnes
2014-8-4
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.
2 个评论
Chris Turnes
2014-8-5
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.
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Random Number Generation 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!