Code covered by the BSD License  

Highlights from
Quick Convolution

Be the first to rate this file! 13 Downloads (last 30 days) File Size: 3.91 KB File ID: #42561

Quick Convolution

by

 

10 Jul 2013 (Updated )

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

| Watch this File

File Information
Description

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.

Required Products MATLAB
MATLAB release MATLAB 7.4 (R2007a)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Updates
11 Jul 2013

Appended the description with an example and a brief note.

Contact us