What is the correct length for obtaining a true linear convolution from DFT?

Question

In the linear convolution of two equal length sequences M and N, the length of the output is length(A)+length(B)-1, and if we apply the DFT property of converting convolution into multiplication, the output is equal Max (length (M) or length (N)).

a) If there a simple way to predict how many edge points are contaminated by circular convolution if we were interested in extracting only the linear convolution section from DFT? Suppose, one does not want to do zero padding in DFT to obtain linear convolution.

b) Secondly, if we wish to do true linear convolution via DFT, should we use zero padding up to length(M)+length(N)-1. This is a figure from a PhD thesis obtainable from ResearchGate pg 18, why does it say if the length of DFT >length(M)+length(N)-1, then results are valid. Is the linear convolution not restricted to the length of length(M)+length(N)-1.

Answer 1

I think what you are asking is: what happens of I implement the convolution of two sequences of length M & N, using spectral multiplication with an FFT of length K? We defined "correct" here as "matching the result of a linear convolution". For simplicity we define the correct length $L = M + N -1$

Here is what you get

1. K > L: The first L samples will be "correct", followed by (K-L) zeros
2. K = L: Correct
3. max(M,N) < K < L: the first (L-K) samples of the result are wrong because of time domain aliasing. You are also missing (L-K) samples at the end or your result since your buffer is too short. Some samples towards the end of your result to match the correct answer somewhere the middle.
4. K < max(M,N): everything is wrong