File Exchange

image thumbnail

Quick Convolution

version 1.1 (3.91 KB) by

Qconv is a faster alternative to the "conv" function of the SP Toolbox when the inputs are long



View License

While the "conv" function of the SP Toolbox is very efficient when one of the two signals being linearly convolved is small in length, the convolution can be computed much faster with the FFT when the signals are large. However, it is often even more efficient to choose a "smart" FFT size (namely, one that has only small primes as its prime factors) to reduce the overhead cost. While the simplest approach is often to take the next power of 2, there can still be considerable gains by allowing the FFT length to be a product of any primes up to "p." Qconv provides this functionality by calling the included cfft.m instead of fft.m.

As an additional note, it seems that p = 5 tends to be a good choice for efficiency.

Here is an example usage from my machine that shows the potential benefit:
>> N1 = 463902; N2 = 123456;
>> X = randn(N1, 1); Y = randn(N2, 1);
>> tic; Xc = qconv(X,Y); toc %-- FFT length is N1 + N2 - 1
Elapsed time is 1.074133 seconds.
>> tic; Xc2 = qconv(X,Y,5); toc %-- choose more optimal FFT size, max prime = 5
Elapsed time is 0.330343 seconds.

Comments and Ratings (0)



Appended the description with an example and a brief note.

MATLAB Release
MATLAB 7.4 (R2007a)

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Win prizes and improve your MATLAB skills

Play today