Convolution implementation

If we want to perform a filter operation in practice then we need a linear and not a circular convolution. In this section we will show how a circular convolution can be used to realize a linear convolution between two signals $x [n]$ and $h [n]$ .

Convolution of two finite duration signals

In the FTD module we have seen that the linear convolution $y [n] = x [n] ⋆ h [n]$ of a finite duration signal $x [n]$ of $N_{1}$ samples with a finite duration impulse response $h [n]$ of $N_{2}$ samples results in a finite duration signal $y [n]$ of length $N = N_{1} + N_{2} - 1$ samples.

Fig. 2 shows an example of the linear convolution of

x [n]

and

h [n]

, which are defined as follows:

\begin{array}{rcl} x [n] & = & δ [n] + δ [n - 1] + δ [n - 2] + \frac{1}{2} δ [n - 3] \\ h [n] & = & δ [n] + \frac{3}{4} δ [n - 1] + \frac{1}{2} δ [n - 2] + \frac{1}{4} δ [n - 3] \end{array}

The result

y [n] = x [n] ⋆ h [n]

has finite duration of

N = N_{1} + N_{2} - 1 = 7

samples:

y [n] = δ [n] + \frac{7}{4} δ [n - 1] + \frac{9}{4} δ [n - 2] + 2 δ [n - 3] + \frac{9}{8} δ [n - 4] + \frac{1}{2} δ [n - 5] + \frac{1}{8} δ [n - 6]

Despite the fact that within the FP both

x_{p} [n]

and

h_{p} [n]

of Fig. 1 are the same as the signals

x [n]

and

h [n]

of Fig. 2, it is clear that the FP of the circular convolution result

y_{p} [n]

does not result in the desired linear convolution result

y [n]

. However when first pad both

x_{p} [n]

and

h_{p} [n]

with zeros up to a length of

N = 7

, as depicted in Fig. 3 by

x_{p, b} [n]

and

h_{p, b} [n]

, then applying a circular convolution the result of

y_{p, b} [n] = x_{p, b} [n] ⊛ h_{p, b} [n]

within the FP is exactly the same as the linear convolution result.

Linear by circular convolution of zero padded signals.

In general we can conclude with the following procedure:

If signal $x [n]$ consists of $N_{1}$ samples and impulse response $h [n]$ of $N_{2}$ samples the result of the linear convolution $y [n] = x [n] ⋆ h [n]$ can be obtained from a circular convolution $y_{p} [n] = x_{p} [n] ⊛ h_{p} [n]$ in which both periodic extended $x_{p} [n]$ and $h_{p} [n]$ are padded with zeros up to a length of $N \geq N_{1} + N_{2} - 1$ samples.

Combining the previous procedure with the fact that a circular convolution is equivalent to a multiplication in the DFT frequency domain we will present a procedure to calculate a linear convolution by a circular one which is implemented in the DFT frequency domain. Referring to Fig. 4 the derivation of this procedure goes as follows:

Linear by circular convolution in DFT domain.

The left hand side of the figure represents a linear convolution result of a finite length signal $x [n]$ of $N_{1}$ samples with a finite length impulse response $h [n]$ of $N_{2}$ samples, resulting in a finite length signal $y [n] = x [n] ⋆ h [n]$ of $N = N_{1} + N_{2} - 1$ samples. The middle figure represents the linear- by circular procedure as explained above: When padding both $x [n]$ and $h [n]$ up to a length of at least $N$ samples and then Periodic Extend both $x_{p} [n]$ and $h_{p} [n]$ , the result of the samples in the FP of the circular convolution $y_{p} [n] = x_{p} [n] ⊛ h_{p} [n]$ is the same as the linear convolution $y [n] = x [n] ⋆ h [n]$ . Finally, the right hand figure represents the the equivalence of a circular convolution to a multiplication in the DFT frequency domain: The circular convolution operation, as denoted in the red box of the middle figure, can be implemented by by the length $N$ Inverse DFT of an element-wise multiplication of the length $N$ DFT results of $x_{p} [n]$ and $h_{p} [n]$ .

In one of the following sections we will show that the DFT can be implemented very efficiently by a so called Fast Fourier Transform (abbreviated by FFT). When applying FFT's it follows that the above described procedure is an extremely efficient way to implement a filter (or convolution) operation. This complexity reduction is one of the main reasons for existence of the DFT and FFT.

Example

Given two finite duration signals:

\begin{array}{rcl} x [n] = δ [n] + δ [n - 1] & and & h [n] = δ [n - 1] + δ [n - 2] \end{array}

Calculate the linear convolution result

y [n] = x [n] ⋆ h [n]

and show how you can obtain this result by using a circular convolution of the periodic extended signals. Finally show that this result can be achieved via the DFT domain.

The linear convolution result is

y [n] = δ [n - 1] + 2 δ [n - 2] + δ [n - 3]

. The 3-point circular convolution result of the periodic extended signals

\begin{array}{rcl} x_{p} [n] & = & δ [n mod (3)] + δ [(n - 1) mod (3)] \\ h_{p} [n] & = & δ [(n - 1) mod (3)] + δ [(n - 2) mod (3)] \end{array}

results in

y_{p} [n] = δ [n mod (3)] + δ [(n - 1) mod (3)] + 2 δ [(n - 2) mod (3)]

, which is not the same as the linear convolution result. Because of the fact that the length of the linear convolution result

y [n]

is 4 samples long, we need to pad the periodic extended signals up to length 4, thus:

\begin{array}{rcl} x_{p} [n] & = & δ [n mod (4)] + δ [(n - 1) mod (4)] \\ h_{p} [n] & = & δ [(n - 1) mod (4)] + δ [(n - 2) mod (4)] \end{array}

The resulting circular convolution

y_{p} [n] = δ [(n - 1) mod (4)] + 2 δ [(n - 2) mod (4)] + δ [(n - 3) mod (4)]

which is, within the FP, the same result as the linear convolution

y [n]

. Via the 4-point DFT we can obtain the same result. For simplicity reasons we calculate the 4-point DFT and IDFT results for indices within the FI and FP respectively, so we can skip the modulo notation:

\begin{array}{rcl} X_{p} [k] & = & 1 + e^{- j \frac{2 π}{4} k} \\ H_{p} [k] & = & e^{- j \frac{2 π}{4} k} + e^{- j \frac{2 π}{4} 2 k} \\ Y_{p} [k] & = & X_{p} [k] \cdot H_{p} [k] = e^{- j \frac{2 π}{4} k} + 2 e^{- j \frac{2 π}{4} 2 k} + e^{- j \frac{2 π}{4} 3 k} \\ y_{p} [k] & = & I D F T {Y_{p} [k]} = δ [n - 1] + 2 δ [n - 2] + δ [n - 3] \end{array}

Last updated on Mar 22, 2020