Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

### Acyclic FFTConvolution

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 (9.15)

which is zero for and . Thus, The number is easily checked for signals of length 1 since , where is 1 at time zero and 0 at all other times. Similarly, (9.16)

and so on.

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).

Subsections
Next  |  Prev  |  Up  |  Top  |  Index  |  JOS Index  |  JOS Pubs  |  JOS Home  |  Search

[How to cite this work]  [Order a printed hardcopy]  [Comment on this page via email]