0
$\begingroup$

When performing discrete [spatial] convolutions in the frequency domain, how much zero-padding is necessary to avoid the effects of circular convolution?

I have a book that almost certainly answers the question, but I've loaned it out and don't have easy access to it for now. So far, my google searches have turned up published papers with an abstract that vaguely mentions the topic, but I'd need access to that journal to see if the paper has the info I need -- info I figured would be easy to find.

  • 0
    Scratch that. The answer is $2N - 1$ along each dimension. See the following: http://cnx.org/content/m10963/latest/2011-05-16
  • 0
    Note that padding to $2N-1$ destroys any useful factorization that $N$ might have had. If $N$ was chosen to factor into small prime factors (e.g. to be a power of $2$), it will be far more efficient to pad to $2N$ instead.2011-05-16
  • 0
    @joriki - Very good point, thank you. If you want to provide the correct answer and that note as part of your answer, I'll accept it.2011-05-16
  • 0
    OK, done, adding a short argument for the minimal length $2N-1$.2011-05-16

1 Answers 1

1

The convolution of two functions with non-zero values at indices from $0$ to $N-1$, i.e. $N$ values, will have non-zero values at indices $0$ to $2(N-1)$, i.e. $2N-1$ values. Thus, it suffices to use a DFT of length $2N-1$ to avoid cyclical overlap. However, if $N$ is chosen so as to factor into small primes, this property is lost if a transform with length $2N-1$ is performed; in this case, it is far more efficient to pad to $2N$ instead.