Special convolutions

Screencast video [⯈]

In many practical situations a measured signal $x\left[n\right]$, which is assumed to be zero for $n<0$, must first be cleaned up before further processing. This is done by filtering the measured samples of $x\left[n\right]$ with a filter with impulse response $\hat{h}\left[n\right]$. In such situations the number of samples of the measured signal $x\left[n\right]$ can be extremely long, while the length $L$ of the impulse response $\hat{h}\left[n\right]$ is much smaller. Thus the problem at hand is to calculate the following extreme, or ‘$\infty$’, long convolution sum in an efficient way: $$\begin{array}{}y\left[n\right]=\hat{h}\left[n\right]\ast x\left[n\right]=\sum _{k=0}^{L-1}\hat{h}\left[k\right]x[n-k]\text{Length}x\left[n\right]\gg L.& \text{(1)}\end{array}$$ In a followup module we will show that the convolution sum of a signal $x\left[n\right]$ with a length $L$ impulse response $\hat{h}\left[n\right]$ can be computed very efficiently with the use of Fast Fourier Transforms (FFT's). Typically FFT's process each iteration one block of $N$ samples and for this approach it is necessary that all data is processed in blocks of $N$ samples. The block length $N$ can be long but certainly not as long as the ‘$\infty$’ length of sequence $x\left[n\right]$. This efficient block processing approach implies that all sequences, the signal to be filtered, the impulse response and the output of our problem at hand, as described in equation ($\text{1}$), must be split in blocks of the same length of $N$ samples. In case a sequence does not have a length of $N$ samples it can easily be extended by padding it with zeros.

In the following subsections we will discuss two different of such block processing approaches to tackle the ‘$\infty$’ long convolution problem ($\text{1}$). For both approaches we assume a block length of $N$ samples and a length $L$ impulse response $\hat{h}\left[n\right]$, with $L<N$. This impulse response is zero padded up to a length $N$ impulse response $h\left[n\right]$ as follows: $$h\left[n\right]=\{\begin{array}{cc}\hat{h}\left[n\right]& n=0,1,\cdots L-1\\ 0& n=L,\cdots ,N-1\end{array}$$ Note that with this zero padded description of the impulse response, the original convolution sum ($\text{1}$) can be written as: $$\begin{array}{}y\left[n\right]=\hat{h}\left[n\right]\star x\left[n\right]\equiv h\left[n\right]\star x\left[n\right]=\sum _{k=0}^{L-1}h\left[k\right]x[n-k]& \text{(2)}\end{array}$$

Overlap-add method

The first, so called overlap-add, approach is based on the $\text{complete convolution}$ of two blocks.

Referring to Fig. 1 this can be explained as follows:

The convolution sum of a sequence $x\left[n\right]$ of $M$ samples with an impulse response of $L$ samples results in an output sequence $y\left[n\right]$ which consists of $N=M+L-1$ samples. As indicated in the figure, the first and last $L-1$ samples are ‘fade-in’ (fi) and ‘fade-out’ (fo) samples respectively. In order not to have an overlap between fade-in and fade-out regions we assume $M\ge L$.

In the overlap-add method, as depicted in Fig. 2, the ‘$\infty$’ long sequence $x\left[n\right]$ is partitioned into $\text{non-overlapping}$ subsequences (‘blocks’) $x_i\left[n\right]$ of length $M$, thus: $$\begin{array}{ccc}x\left[n\right]=\sum _{i=0}^{\infty }{x}_i\left[n\right]& \text{with}& x_i\left[n\right]=\{\begin{array}{cc}x[n+M\cdot i]& n=0,1,\cdots M-1\\ 0& \text{else}\end{array}\end{array}$$ With this non overlapped splitting we can rewrite the convolution sum ($\text{2}$) as follows: $$\begin{array}{ccc}y\left[n\right]=h\left[n\right]\star x\left[n\right]& =& \sum _{k=0}^{L-1}h\left[k\right]x[n-k]\\ & =& \sum _{k=0}^{L-1}h\left[k\right]\left(\sum _{i=0}^{\infty }{x}_i\right[n-k\left]\right)\\ & =& \sum _{i=0}^{\infty }\left(\sum _{k=0}^{L-1}h\right[k\left]x_i\right[n-k\left]\right)\\ & =& \sum _{i=0}^{\infty }\left(h\right[n]\star x_i[n\left]\right)=\sum _{i=0}^{\infty }{y}_i\left[n\right]\end{array}$$ Each of the intermediate convolution sum results $y_i\left[n\right]$ consist of maximal $N=M+L-1$ non zero samples in which the first and last $L-1$ samples of each subsequence $y_i\left[n\right]$ are due to fade-in and fade-out.

The overlap-add procedure consists of the following steps:

• $i=0$:
  • Zero pad length $L$ impulse response up to length $N$,
  • Zero pad length $M$ input sequence $x_0\left[n\right]$ up to length $N$,
  • Calculate length $N$ convolution sum $y_0\left[n\right]=h\left[n\right]\star x_0\left[n\right]$,
  • The first $M$ samples are valid convolution sum results:
  $$y\left[n\right]=y_0\left[n\right]\text{for}n=0,\cdots M-1$$
• $i\ge 1$:
  • Zero pad length $M$ input sequence $x_i\left[n\right]$ up to length $N$,
  • Calculate length $N$ convolution sum $y_i\left[n\right]=h\left[n\right]\star x_i\left[n\right]$,
  • Add last $L-1$ 'fade-out' samples of block $i-1$ and first $L-1$ 'fade-in' samples of block $i$:
  $$y\left[n\right]=\{\begin{array}{cc}{y}_{i-1}\left[n\right]+y_i\left[n\right]& \text{for}n=i\cdot M,\cdots ,i\cdot M+L-1\\ y_i\left[n\right]& \text{for}n=i\cdot M+L,\cdots ,(i+1)\cdot M-1\end{array}$$

Overlap-save method

The second approach, which is called overlap-save, is based on the $\text{partial convolution}$ of two blocks.

Referring to Fig. 3. this can be explained as follows: The impulse response $h\left[n\right]$ consists of $L$ samples, while now the Now the sequence $x\left[n\right]$ now consists of $N$ samples and the impulse response $h\left[n\right]$ consists of $L$ samples. Again $N=L+M-1$ but now with $M\ge 1$. In this case the resulting sequence $y\left[n\right]$ consists of $N$ samples from which the first $L-1$ samples are 'fade-in' samples and the last $L-1$ 'fade-out' samples are not computed.

In the overlap-save method, as depicted in Fig. 3, the ‘$\infty$’ long sequence $x\left[n\right]$ is partitioned into $\text{overlapping}$ blocks $x_i\left[n\right]$ of length $N=L+M-1$ with an overlap of $L-1$ samples: $$x_i\left[n\right]=\{\begin{array}{cc}x[n+i\cdot M]& \text{for}n=0,1,\cdots ,N-1\\ 0& \text{else}\end{array}$$

Each intermediate convolution sum result $y_i\left[n\right]$ consists of maximal $N$ non zero samples in which the first $L-1$ samples are due to fade-in. The last $L-1$ 'fade-out' samples are not computed. The overlap-save procedure consist of the following steps:

• $i=0$:
  • Zero pad length $L$ impulse response up to length $N$,
  • Calculate the first $N$ samples of the convolution sum $y_0\left[n\right]=h\left[n\right]\star x_0\left[n\right]$:
  • The first $N$ samples are valid convolution sum results: $$y\left[n\right]=y_0\left[n\right]\text{for}n=0,\cdots N-1$$
• $i\ge 1$:
  • Calculate the first $N$ samples of the convolution sum $y_i\left[n\right]=h\left[n\right]\star x_i\left[n\right]$:
  • Discard the first $L-1$ 'fade in' samples and the last $M$ samples are valid convolution sum results: $$y\left[n\right]=y_i\left[n\right]\text{for}n=L,\cdots N-1$$

Final notes

The overlap-add procedure is based on $\text{complete convolution}$ of $\text{non-overlapping}$ blocks while the overlap-save procedure is based on $\text{partial convolution}$ of $\text{overlapping}$ blocks.

For applications in which the filter coefficients do not change during processing of the ‘$\infty$’ long sequence $x\left[n\right]$, it is valid to add the ‘fade out’ samples of iteration $i-1$ and ‘fade in’ samples of iteration $i$ since both use the same fixed impulse response. However, in adaptive filter applications the filter coefficients will change during the processing of the ‘$\infty$’ long sequence $x\left[n\right]$ and it is not valid to add the ‘fade out’ samples of iteration $i-1$ and ‘fade in’ samples of iteration $i$. For this reason the overlap-add procedure is mainly used when the filter coefficients of the impulse response do not change while overlap-save is mainly used for adaptive applications.

In a follow up module we will show how both block processing approaches can be implemented efficiently with the use of FFT's.