1
$\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
    OK, done, adding a short argument for the minimal length $2N-1$.2011-05-16

1 Answers 1

2

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.