# Inverse Z-transform

## Inverse Z-Transform

The forward Z-transform helped us express samples in time as an analytic function on which we can use our algebra tools. Eventually, we have to return to the time domain using the Inverse Z-transform.

The inverse Z-transform can be derived using Cauchy’s integral theorem.

\def\lfz#1{\overset{\Large#1}{\,\circ\kern-6mu-\kern-7mu-\kern-7mu-\kern-6mu\bullet\,}} \def\ztransform{\lfz{\mathcal{Z}}} \begin{align} f[m]\,\ztransform\,&F(z)=\sum_{m=0}^\infty z^{-m}\ f[m]\nonumber \end{align} \nonumber

Multiply both sides by $$z^{n-1}$$

\begin{align} F(z)\,\color{purple}{z^{n-1}}&=\sum_{m=0}^\infty z^{-m\color{purple}{+n-1}}\,f[m] \end{align}

Integrate with a counterclockwise contour integral for which the contour encloses the origin and lies entirely within the region of convergence of $$F(z)$$

\begin{align} \color{purple}{\frac{1}{2\pi j}\oint_C} F(z)\,z^{n-1}\,\color{purple}{\mathrm{d}z}&=\color{purple}{\frac{1}{2\pi j}\oint_C} \sum_{m=0}^\infty z^{-m+n-1}\,f[m]\,\color{purple}{\mathrm{d}z} \nonumber \\ &= \sum_{m=0}^\infty\,f[m]\ \underbrace{\frac{1}{2\pi j}\oint_C \,z^{-(m-n+1)}\,\mathrm{d}z}_{\color{blue}{\text{?}}} \end{align}

A special case of Caughy integral theorem states

$$\frac{1}{2\pi j}\,\oint_Cz^{-l}\,\mathrm{d}z\,=\, \begin{cases} 1 & l = 1 \\ 0 & l\neq1 \end{cases} \nonumber$$

That implies we can replace the integral with a $$\delta$$ function.

\begin{align} \frac{1}{2\pi j}\oint_C F(z)\,z^{n-1}\,\mathrm{d}z &= \sum_{m=0}^\infty\,f[m]\ \underbrace{\frac{1}{2\pi j}\oint_C \,z^{-(m-n+1)}\,\mathrm{d}z}_{\color{purple}{=1\text{ only when m-n+1=1}}} \nonumber \\ &= \sum_{m=0}^\infty\,f[m]\ \color{purple}{\delta[m-n]} \end{align}

The Inverse Z-transform follows as

$$\shaded{ f[n] = \frac{1}{2\pi j}\oint_C F(z)\,z^{n-1}\,\mathrm{d}z }$$
where the contour integral is taken over a counter-clockwise closed contour $$C$$ in the region of converge (ROC). The contour $$C$$ must encircle all the poles and zeroes of $$F(z)$$.

### Cauchy’s Residue Theorem

When the transfer functions is rational, a ratio of polynomials, we may use the method described below to calculate the Inverse Z-transform.

Denote the unique poles of $$F(z)$$ as $$p_{1\ldots{\small N}}$$ and their algebraic multiplicities as $$m_{1\ldots{\small N}}$$. As long as $$N$$ is finite, which is the case if $$F(z)$$ is rational, we can evaluate the inverse Z-Transform via Cauchy’s residue theorem that states

$$f[n] = \frac{1}{2\pi j}\oint_C F(z)\,z^{n-1}\,\mathrm{d}z=\sum_{p_k\text{ inside }C}\mathrm{Res}\large{(}\,F(z)\,z^{n-1},\,p_k,\,m_k\,{\large{)}} \nonumber$$ where $$\mathrm{Res}{\Large(}\,F(z)\,z^{n-1},\,p_k,\,m_k\,{\Large)}=\frac{1}{(m_k-1)!}\left[\frac{\text{d}^{(m_k-1)}}{\text{d}z^{(m_k-1)}}\,{\Large[}\,(z-p_k)^{m_k}\,F(z)\,z^{n-1}\,{\Large]}\right]_{z=p_k} \nonumber$$ for a single pole $$\mathrm{Res}{\Large(}\,F(z)\,z^{n-1},\,p_k,\,1\,{\Large)}=\left.\,(z-p_k)\,F(z)\,z^{n-1}\,\right|_{z=p_k} \nonumber$$

Cauchy’s residue theorem allows us to compute the contour integral by computing derivatives, however tedious.

### Other techniques

Given that the $$z$$-transform is a particular type of Laurent series, and the Laurent series in a given annulus of convergence is unique, any technique can be used to generate a power series for $$F(z)$$ that converges in the outermost annulus of convergence to obtain the inverse $$z$$-transform.

Inversion techniques available are

• using the binomial theorem
• using the convolution theorem
• performing long division
• using the initial-value theorem
• expanding $$F(z)$$ in partial fractions
• power series expansion (for non-rational z-transforms).

## Inverse Unilateral Z-Transform

The inverse Z-transform, can be evaluated using Cauchy’s integral. Which is an integral taken over a counter-clockwise closed contour $$C$$ in the region of converge of $$Y(z)$$. When the ROC is causal, this means the path $$C$$ must encircle all the poles of $$Y(z)$$.

$$y[n] = \frac{1}{2\pi j}\oint_C Y(z)\,z^{n-1}\,\mathrm{d}z$$

Let’s try some simplifications:

1. When all poles of $$Y(z)$$ poles are inside the unit circle, $$Y(z)$$ is stable and $$C$$ can be the unit circle. Thus the contour integral simplifies to the inverse discrete-time Fourier transform (DTFT) of the periodic values of the Z-transform around the unit circle . To proof we take the unit circle $$|z|=1$$, and parameterize contour $$C$$ by $$z(\omega)=\mathrm{e}^{j\omega}$$, with $$-\pi\leq \omega\leq\pi$$ so $$\frac{\text{d}z}{\text{d}\omega}=j\mathrm{e}^{j\omega}$$
\begin{align} y[n] &= \frac{1}{2\pi j}\oint_C Y(z)\,z^{n-1}\,\mathrm{d}z \nonumber \\ &= \frac{1}{2\pi \bcancel{j}}\int_{-\pi}^{\pi} Y(\mathrm{e}^{j\omega})\,(\mathrm{e}^{j\omega})^{n\cancel{-1}}\bcancel{j}\cancel{{\mathrm{e}^{j\omega}}}\,\,\mathrm{d}\omega \nonumber \\ &= \frac{1}{2\pi}\int_{-\pi}^{\pi} Y(\mathrm{e}^{j\omega })\,\mathrm{e}^{j\omega n}\,\mathrm{d}\omega \nonumber \end{align}
2. If a system is represented by a linear constant-coefficient difference equations (LCCDE), it is said to be rational. The output is in the form $$(N\gt M)$$
$$\sum_{k=0}^N a_k y[n-k]=\sum_{k=0}^M b_k x[n-k] \label{eq:rational}$$
this allows us to find the impulse response $$h[n]$$ and frequency response $$H(\mathrm{e}^{j\omega})$$ of this LTI system similarly to the methods to solve a continuous LCCDE problems.

For rational systems captured by equation $$\eqref{eq:rational}$$ the output in the Z-domain output can be expressed as

$$Y(z)=\frac{b_0+b_1z+b_2z^2+\ldots+b_Mz^M}{a_0+a_1z+a_2z^2+\ldots+a_Nz^N}$$

We will examine solution methods for rational systems in the following sections.

### Long Division

Long-division of the polynomials directly is a simple but not so practical method for obtaining a power series expansion for $$Y(z)$$. Using the definition of the Z-transform, the terms of the sequence can then be identified one at a time. Problem with this method is that it is labor intensive, and does not produce a closed-form expression for $$y[n]$$.

### Direct Computation

When $$x[n]=\delta[n]$$, $$y[n]=h[n]$$. For $$n=0$$, we obtain the initial condition:

$$h[0]-ah[-1]=h[0]=\delta[0]=1$$

For $$n>0$$, we plug the general solution $$h[n]=Az^n$$ into the DE and get

$$Az^n-aAz^{n-1}=\delta[n]=0,\ \ n\gt 0$$

From which we get $$z=a$$ and $$h[n]=Aa^n$$. But as $$h[0]=1$$, we have $$A=1$$ and

$$h[n]=a^n \gamma[n]$$

The Fourier spectrum of $$h[n]$$ is the corresponding frequency response

\begin{align} H(e^{j\omega})&: {\cal F}[h[n]]=\sum_{n=-\infty}^\infty h[n]e^{-jn\omega}\\ &:\sum_{n=0}^\infty a^n e^{-jn\omega}=\frac{1}{1-ae^{-j\omega}} \end{align}

src: http://fourier.eng.hmc.edu/e101/lectures/handout3/node9.html

### Partial Fraction Expansion

2BD: see “discrete transfer functions

### Eigenequation method ??

Consider a linear time invariant system $$H$$ with impulse response $$h$$ operating on some space of infinite length continuous time signals. Recall that the output $$H\big(x(t)\big)$$ of the system for a given input $$x(t)$$ is given by the continuous time convolution of the impulse response with the input

$$H\big(x(t)\big)=\int_{-\infty}^{\infty}h(\tau)\,x(t−\tau)\,d\tau$$

Consider the input $$x(t)=\mathrm{e}^{st}$$ where $$s\in \mathbb{C}$$, the output

\begin{align} H\big(\mathrm{e}^{st}\big) &= \int_{-\infty}^{\infty}h(\tau)\,\mathrm{e}^{s(t-\tau)}\,d\tau \nonumber \\ &= \int_{-\infty}^{\infty}h(\tau)\,\mathrm{e}^{st}\mathrm{e}^{-s\tau}\,d\tau \nonumber \\ &= \mathrm{e}^{st}\int_{-\infty}^{\infty}h(\tau)\,\mathrm{e}^{-s\tau}\,d\tau \end{align}

Define

$$\lambda_s=\int_{-\infty}^{\infty}h(\tau)\,\mathrm{e}^{-s\tau}\,d\tau$$

The eigenvalue follows as

$$H\big(\mathrm{e}^{st}\big)=\lambda_s\mathrm{e}^{st}$$
corresponding with eigenvector $$\mathrm{e}^{st}$$.

This makes it particularly easy to calculate the output of a system when an eigenfunction is the input because the output is simply the eigenfunction scaled by the associated eigenvalue.

src: http://pilot.cnxproject.org/content/collection/col10064/latest/module/m34639/latest

Use the eigenequation of the LTI system.

——– If the input is a complex exponential

$$\def\lfz#1{\overset{\Large#1}{\,\circ\kern-6mu-\kern-7mu-\kern-7mu-\kern-6mu\bullet\,}} \def\ztransform{\lfz{\mathcal{Z}}} x[n]\ztransform z^n\\$$
an eigenfunction of the LTI system, then
$$\def\lfz#1{\overset{\Large#1}{\,\circ\kern-6mu-\kern-7mu-\kern-7mu-\kern-6mu\bullet\,}} \def\ztransform{\lfz{\mathcal{Z}}} y[n]=\ztransform z^n\,H(z)$$

Substitute $$z=e^{j\omega}$$

$$y[\omega]=e^{j\omega n}\,H(e^{j\omega})$$

Substituting $$x[n]$$ and $$y[n]$$ into the given DE, we can obtain $$H(e^{j\omega})$$.

### Fourier transform ??

Take Fourier transform on both sides of the given DE, and use the linearity and time-shifting properties:

$${\cal F}[\sum_{k=0}^N a_k y[n-k]]={\cal F}[\sum_{k=0}^M b_k x[n-k]]$$

Due to the linearity property, this becomes

$$\sum_{k=0}^N a_k {\cal F}[y[n-k]]=\sum_{k=0}^M b_k {\cal F}[x[n-k]]$$

and due to the time shifting property, we get

$$Y(e^{j\omega})[\sum_{k=0}^N a_k e^{-jk\omega}] = X(e^{j\omega})[\sum_{k=0}^M b_k e^{-jk\omega}]$$

From which we find

$$H(e^{j\omega})=\frac{Y(e^{j\omega})}{X(e^{j\omega})} = \frac{\sum_{k=0}^M b_k e^{-jk\omega}}{\sum_{k=0}^N a_k e^{-jk\omega}}$$

2BD …

src: http://fourier.eng.hmc.edu/e101/lectures/handout3/node9.html

Similar to Laplace: http://ocw.usu.edu/Electrical_and_Computer_Engineering/Signals_and_Systems/node2.html

… page 111 in http://web.stanford.edu/~kairouzp/teaching/ece310/secure/Chapter5.pdf

Digital filters can be designed using the Z-transform, similar to how analog filters are designed using the Laplace transform. The properties and functions listed in the tables provide a foundation the design and analysis of such digital filters.