Best approach for discarding the ends of convolution in FT

Question

In a recent discussion Linear vs. Circular Convolution on avoiding circular convolution by FFT, it was shown that the FFT length for convolution purposes set should be = (data set 1)+ (data set 2) -1.

For example, the length of data set A and B is 1000 each. The FFT of linear convolution of A and B in Fourier domain should be FFT(A, 1999) x FFT(B, 1999).

If it is desired that we keep the original number of points as in A, one can trim the first 500 points in the beginning and 499 points at the end or one can discard the first 499 points and then remove 500 points at the end.

A similar problem can arise if the length of A and B is odd, say 1001 point. The convolution length would be 2001.

What is the correct approach for discarding the ends of a convolution?

MATLAB has a "same" option in convolution, but they don't mention how the points are discarded.

Answer 1

In this particular example best practice would be zero pad both signals to 2048 samples, FFT, multiply, and inverse FFT. This will result in 2048 time samples. The first 1999 are your convolution result and the last 49 are zero. Whether you want to discard the last 49 samples or just leave them as zeros, depends on what you want to do with them.

If you are worried about efficiency you should choose an FFT length that has only very small prime factors and ideally a power of 2. Hence the choice of 2048. A 2048 sample FFT is much faster than one over 1999 samples.

Here is a Matlab example of this

%% convolution test
% create two random signals of 1000 samples each
n = 1000;
x0 = randn(n,1);
x1 = randn(n,1);
% time domain convolution
ytime = conv(x0,x1);  
% frequency domain multiplication with zero padding to 2048
yfft = real(ifft(fft(x0,2048).*fft(x1,2048)));
% discard the excess zeros
yfft = yfft(1:(n+n-1),:);
% calculate the difference and print the relative error
d = yfft-ytime;
err = 10*log10(sum(d.^2)./sum(ytime.^2));
fprintf('Difference = %6.2f dB\n',err);

Answer 2

For a convolution resulting in N+M-1 elements, with N>=M, best result might be to discard M-1 elements from both sides of the result. All the other convolutional result elements are "contaminated" by your assumptions about padding (zero, circular, random, etc.), and how closely that assumption corresponds to something useful or actual.