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) \isdef \sum_{m=-\infty}^\infty x(m)h(n-m) = \sum_{m=0}^n x(m)h(n-m)$$

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... ...\delta)] = \delta + 2\hbox{\sc Shift}_1(\delta) + \hbox{\sc Shift}_2(\delta)$$

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 [104].

We thus conclude that, to embed acyclic convolution within a cyclic convolution (as provided by the 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).