3
$\begingroup$

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?

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.