Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Scratch that. The answer is $2N - 1$ along each dimension. See the following: cnx.org/content/m10963/latest –  Brian Vandenberg May 16 '11 at 21:10
    
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. –  joriki May 16 '11 at 21:12
    
@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. –  Brian Vandenberg May 16 '11 at 21:13
    
OK, done, adding a short argument for the minimal length $2N-1$. –  joriki May 16 '11 at 21:19
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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