If we add enough trailing zeros to the signals being convolved, we can obtain acyclic convolution embedded within a cyclic convolution. How many zeros do we need to add? Suppose the signal consists of contiguous nonzero samples at times 0 to , preceded and followed by zeros, and suppose is nonzero only over a block of samples starting at time 0. Then the acyclic convolution of with reduces to
The number is easily checked for signals of length 1 since , where is 1 at time zero and 0 at all other times. Similarly,
When or is infinity, the convolution result can be as small as 1. For example, consider , with , and . Then . This is an example of what is called deconvolution. In the frequency domain, deconvolution always involves a pole-zero cancellation. Therefore, it is only possible when or is infinite. In practice, deconvolution can sometimes be accomplished approximately, particularly within narrow frequency bands .
We thus conclude that, to embed acyclic convolution within a cyclic convolution (as provided by an FFT), we need to zero-pad both operands out to length , where is at least the sum of the operand lengths (minus one).