# Best approach for discarding the ends of convolution in FT

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.

• FFT(A,1999)xFFT(B,1999) Is not the linear convolution of A and B; it is the Fourier transform of the linear convolution. Discarding any of the terms in FFT(A,1999) or in FFT(A,1999)xFFT(B,1999) is a sure method of heading towards a disaster. – Dilip Sarwate Mar 12 at 16:46
• I meant FFT of the convolution. – M. Farooq Mar 12 at 20:28
• I would ask, why do you insist on applying the convolution in Fourier Domain? – Royi Mar 12 at 20:42
• Actually, I am working on a technique called Fourier self-deconvolution. It is used in spectroscopy to reduce the width of the peaks and enhance the resolution. Sometimes we need to divide one spectrum from another one in the Fourier domain and then do an inverse. – M. Farooq Mar 12 at 20:45
• So why do you need to work on lengths which are results of Spatial / Time Domain convolution? – Royi Mar 12 at 21:02

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)));