# Computing a convolution using FFT and more than minimum number of samples

Assume vector s is a set of time samples of length 1000. Assume vector h is a set of samples of length 50.

If I want to compute the convolution of those vectors, the result will be 1000+50-1 = 1049 points long, as expected.

If I want instead to calculate this using an FFT, I need to ensure that the circular convolution does not alias. Therefore, the FFT size of each vector must be >= 1049. However, I want an efficient FFT length, so I compute a 2048 size FFT of each vector, multiply them together, and take the ifft. This leaves me with a 2048 point answer.

In Matlab: H = fftshift(fft(h,2048)); S = fftshift(fft(s,2048)); result = fftshift(ifft(H.*S));

That result contains "extra" samples because of the fft zero padding. Theoretically it contains exactly 999 extra samples that I need to throw out. What's the systematic way to know exactly which samples of the resulting vector to throw away?

• All the extra samples are zeros at the end. Makes them easy to find :-) Nov 18 '21 at 13:36
• For this example, the direct linear convolution is significantly more efficient than doing 3 2048 point FFTs. Nov 18 '21 at 14:38

Simply keep the first 1049 samples of the IFFT result and throw the rest away.

You don't have to do a fftshift

y1 = conv(s,h);
y2 = ifft(fft(s, 2048) .* fft(h, 2048));
figure; plot(y1); hold on; plot(y2(1:length(y1)), '--');


BTW, compared to linear convolution, it is more efficient to use FFT when s and h have similar lengths. In your case uniformly breaking the long signal s into several small blocks and then applying overlap-add or overlap-save should be a better solution.

• Thanks. It appears that all of the 'fftshift's I was doing were causing me my problems. Nov 19 '21 at 14:49