Acyclic FFT Convolution

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 $x(n)$ consists of $N_x$ contiguous nonzero samples at times 0 to $N_x-1$ , preceded and followed by zeros, and suppose $h(n)$ is nonzero only over a block of $N_h$ samples starting at time 0. Then the acyclic convolution of $x$ with $h$ reduces to

$$(x\ast h)(n) \isdefs \sum_{m=-\infty}^\infty x(m)h(n-m) \eqsp \sum_{m=0}^n x(m)h(n-m)$$ (9.15)

which is zero for $n<0$ and $n>(N_x+N_h-1)-1$ . Thus,

$\parbox{0.8\textwidth}{\emph{the acyclic convolution of $N_x$\ samples with $N_h$\ samples produces at most $N_x+N_h-1$\ nonzero samples.}}$

The number $N_x+N_h-1$ is easily checked for signals of length 1 since $\delta\ast \delta = \delta$ , where $\delta$ is 1 at time zero and 0 at all other times. Similarly,

$$[\delta+\hbox{\sc Shift}_1(\delta)] \ast [\delta+\hbox{\sc Shift}_1(\delta)] \eqsp \delta + 2\hbox{\sc Shift}_1(\delta) + \hbox{\sc Shift}_2(\delta)$$ (9.16)

and so on.

When $N_x$ or $N_h$ is infinity, the convolution result can be as small as 1. For example, consider $x=[1,r,r^2,r^3,\ldots]$ , with $\left\vert r\right\vert<1$ , and $h=[1,-r,0,0,\ldots]$ . Then $x\ast h = [1, 0, 0, \ldots]$ . 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 $N_x$ or $N_h$ is infinite. In practice, deconvolution can sometimes be accomplished approximately, particularly within narrow frequency bands [119].

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 $N$ , where $N$ is at least the sum of the operand lengths (minus one).