-1
$\begingroup$

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.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Dilip Sarwate Mar 12 '20 at 16:46
  • $\begingroup$ I meant FFT of the convolution. $\endgroup$ – M. Farooq Mar 12 '20 at 20:28
  • $\begingroup$ I would ask, why do you insist on applying the convolution in Fourier Domain? $\endgroup$ – Royi Mar 12 '20 at 20:42
  • $\begingroup$ 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. $\endgroup$ – M. Farooq Mar 12 '20 at 20:45
  • $\begingroup$ So why do you need to work on lengths which are results of Spatial / Time Domain convolution? $\endgroup$ – Royi Mar 12 '20 at 21:02
1
$\begingroup$

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);
Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\endgroup$
  • $\begingroup$ If we discard M-1 points from both ends, we would be left with only 1 point, assuming N=M in length. Probably you meant (M-1)/2. $\endgroup$ – M. Farooq Mar 26 '20 at 13:58
  • $\begingroup$ If N=M, you only get 1 correct-in-all-cases result point. All other points have edge assumption dependancies. Bad assumptions = bad results. $\endgroup$ – hotpaw2 Mar 26 '20 at 14:01
  • $\begingroup$ Okay, in order to get the same results via FFT as the conv (a,b, 'same'), we will have to trim b/2 points from both ends, assuming the length of a=b. The reason for using conv (a,b, 'same') is that it keeps the peak position the same as the original signal. For example, running a centered moving average via hamming window, H, of 51 points, I can use conv (a, H, 'same'). It smooths the signal and also keeps the peak position the same. $\endgroup$ – M. Farooq Mar 26 '20 at 14:13
  • $\begingroup$ Just for sake of doing it, doing the same via fft with zero padding H so that the fft length is a+H-1, I had to trim both ends symmetrically to keep the same peak position. Thanks. Do you agree with that? $\endgroup$ – M. Farooq Mar 26 '20 at 14:13

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.