2 Convolution and z-transforms

Consider a discrete system with transfer function $H\left(z\right)$

Figure 16

We know, from the definition of the transfer function that at zero initial conditions

$Y\left(z\right)=X\left(z\right)H\left(z\right)$ (7)

We now investigate the corresponding relation between the input sequence $\left\{x_n\right\}$ and the output sequence $\left\{y_n\right\}$ . We have seen earlier that the system itself can be characterised by its unit impulse response $\left\{h_n\right\}$ which is the inverse z-transform of $H\left(z\right)$ .

We are thus seeking the inverse z-transform of the product $X\left(z\right)H\left(z\right)$ . We emphasize immediately that this is not given by the product $\left\{x_n\right\}\left\{h_n\right\}$ , a point we also made much earlier in the workbook.

We go back to basic definitions of the z-transform:

$Y\left(z\right)=y_0+y_1{z}^{-1}+y_2{z}^{-2}+y_3{z}^{-3}+\dots$

$X\left(z\right)=x_0+x_1{z}^{-1}+x_2{z}^{-2}+x_3{z}^{-3}+\dots$

$H\left(z\right)=h_0+h_1{z}^{-1}+h_2{z}^{-2}+h_3{z}^{-3}+\dots$

Hence, multiplying $X\left(z\right)$ by $H\left(z\right)$ we obtain, collecting the terms according to the powers of $z^{-1}$ :

$x_0{h}_0+\left(x_0{h}_1+x_1{h}_0\right)z^{-1}+\left(x_0{h}_2+x_1{h}_1+x_2{h}_0\right)z^{-2}+\dots$

Task!

Write out the terms in $z^{-3}$ in the product $X\left(z\right)H\left(z\right)$ and, looking at the emerging pattern, deduce the coefficient of $z^{-n}$ .

Answer

Hence, comparing corresponding terms in $Y\left(z\right)$ and $X\left(z\right)H\left(z\right)$

$\left.\begin{array}{ccc}{z}^0:\hfill & \hfill y_0\hfill & =x_0{h}_0\hfill \\ z^{-1}:\hfill & \hfill y_1\hfill & =x_0{h}_1+x_1{h}_0\hfill \\ z^{-2}:\hfill & \hfill y_2\hfill & =x_0{h}_2+x_1{h}_1+x_2{h}_0\hfill \\ z^{-3}:\hfill & \hfill y_3\hfill & =x_0{h}_3+x_1{h}_2+x_2{h}_1+x_3{h}_0\hfill \end{array}\right\}$ (8)

$⋮⋮$

   $z^{-n}:y_n=x_0{h}_n+x_1{h}_{n-1}+x_2{h}_{n-2}+\dots +x_{n-1}{h}_1+x_n{h}_0$ (9)

$={\sum }_{k=0}^n{x}_k{h}_{n-k}$ (10a)

$={\sum }_{k=0}^n{h}_k{x}_{n-k}$ (10b)

(Can you see why (10b) also follows from (9)?)

The sequence $\left\{y_n\right\}$ whose $n^{\text{ th}}$ term is given by (9) and (10) is said to be the convolution (or more precisely the convolution summation ) of the sequences $\left\{x_n\right\}$ and $\left\{h_n\right\}$ ,

The convolution of two sequences is usually denoted by an asterisk symbol ( $\ast$ ).

We have shown therefore that

${\mathbb{Z}}^{-1}\left\{X\left(z\right)H\left(z\right)\right\}=\left\{x_n\right\}\ast \left\{h_n\right\}=\left\{h_n\right\}\ast \left\{x_n\right\}$

where the general term of $\left\{x_n\right\}\ast \left\{h_n\right\}$ is in (10a) and that of $\left\{h_n\right\}\ast \left\{x_n\right\}$ is in (10b).

In words: the output sequence $\left\{y_n\right\}$ from a linear time invariant system is given by the convolution of the input sequence with the unit impulse response sequence of the system.

This result only holds if initial conditions are zero.

Although we have developed the convolution summation in the context of linear systems the proof given actually applies to any sequences i.e.for arbitrary causal sequences say $\left\{v_n\right\}\left\{w_n\right\}$ with z-transforms $V\left(z\right)$ and $W\left(z\right)$ respectively:

${\mathbb{Z}}^{-1}\left\{V\left(z\right)W\left(z\right)\right\}=\left\{v_n\right\}\ast \left\{w_n\right\}$ or, equivalently, $\mathbb{Z}\left(\left\{v_n\right\}\ast \left\{w_n\right\}\right)=V\left(z\right)W\left(z\right)$ .

Indeed it is simple to prove this second result from the definition of the z-transform for any causal sequences $\left\{v_n\right\}=\left\{v_0,v_1,v_2,\dots \right\}$ and $\left\{w_n\right\}=\left\{w_0,w_1,w_2,\dots \right\}$

Thus since the general term of $\left\{v_n\right\}\ast \left\{w_n\right\}$ is ${\sum }_{k=0}^n{v}_k{w}_{n-k}$

we have

$\mathbb{Z}\left(\left\{v_n\right\}\ast \left\{w_n\right\}\right)={\sum }_{n=0}^{\infty }\left\{{\sum }_{k=0}^n{v}_k{w}_{n-k}\right\}{z}^{-n}$

or, since $w_{n-k}=0$ if $k>n$ ,

$\mathbb{Z}\left(\left\{v_n\right\}\ast \left\{w_n\right\}\right)={\sum }_{n=0}^{\infty }{\sum }_{k=0}^{\infty }{v}_k{w}_{n-k}{z}^{-n}$

Putting $m=n-k$ or $n=m+k$ we obtain

$\mathbb{Z}\left(\left\{v_n\right\}\ast \left\{w_n\right\}\right)={\sum }_{m=0}^{\infty }{\sum }_{k=0}^{\infty }{v}_k{w}_m{z}^{-\left(m+k\right)}$ (Why is the lower limit $m=0$ correct?)

Finally,

$\mathbb{Z}\left(\left\{v_n\right\}\ast \left\{w_n\right\}\right)={\sum }_{m=0}^{\infty }{w}_m{z}^{-m}{\sum }_{k=0}^{\infty }{v}_k{z}^{-k}=W\left(z\right)V\left(z\right)$

which completes the proof.

Example 2

Calculate the convolution $\left\{y_n\right\}$ of the sequences

$\left\{v_n\right\}=\left\{a^n\right\}\left\{w_n\right\}=\left\{b^n\right\}a\ne b$

1. directly
2. (ii) using z-transforms.

Solution

1. We have from (10) $$\begin{array}{rcll}{y}_n& =& \underset{k=0}{\overset{n}{\sum }}{v}_k{w}_{n-k}=\underset{k=0}{\overset{n}{\sum }}{a}^k{b}^{n-k}& \\ & & & \\ & =& b^n\underset{k=0}{\overset{n}{\sum }}{\left(\frac{a}{b}\right)}^k& \\ & & & \\ & =& b^n\left(1+\left(\frac{a}{b}\right)+{\left(\frac{a}{b}\right)}^2+\dots {\left(\frac{a}{b}\right)}^n\right)& \end{array}$$

   The bracketed sum involves $n+1$ terms of a geometric series of common ratio $\frac{a}{b}$ .

   $$\begin{array}{rcll}\therefore y_n& =& b^n\frac{\left(1-{\left(\frac{a}{b}\right)}^{n+1}\right)}{1-\frac{a}{b}}& \\ & =& \frac{\left(b^{n+1}-a^{n+1}\right)}{\left(b-a\right)}& \end{array}$$
2. The z-transforms are

   $V\left(z\right)=\frac{z}{z-a}$

   $W\left(z\right)=\frac{z}{z-b}$

   so

   $$\begin{array}{rcll}\therefore y_n& =& {\mathbb{Z}}^{-1}\left\{\frac{z^2}{\left(z-a\right)\left(z-b\right)}\right\}& \\ & =& \frac{b^{n+1}-a^{n+1}}{\left(b-a\right)}\text{using partial fractions or residues}& \end{array}$$

Task!

Obtain by two methods the convolution of the causal sequence

$\left\{2^n\right\}=\left\{1,2,2^2,2^3,\dots \right\}$

with itself.

Answer