1
$\begingroup$

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.

enter image description here

Improve this question
$\endgroup$
2
  • $\begingroup$ crappy use of letters. we almost always use "$N$" for the DFT size. $\endgroup$
    – robert bristow-johnson
    Jan 13, 2021 at 6:33
  • $\begingroup$ and if we apply the DFT property of converting convolution into multiplication, the output is equal Max (length (M) or length (N)). No? That's not true. You need to bring both vectors to the same length before DFT'ing them (before then multiplying them) and if you don't use M+N-1 as common length, you don't get a valid convolution. There's no magic here. $\endgroup$
    – Marcus Müller
    Jan 13, 2021 at 6:35

1 Answer 1

Reset to default
3
$\begingroup$

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
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, could you also add the case, where, M=N, and K=N=M? How points will be contaminated on both ends due to circular convolution? $\endgroup$
    – AChem
    Jan 13, 2021 at 14:20
  • $\begingroup$ Makes no difference. I've already covered all general cases. Just plug in the numbers $\endgroup$
    – Hilmar
    Jan 13, 2021 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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