#!/usr/bin/env python
# coding: utf-8

# # The $z$-Transform
# 
# *This Jupyter notebook is part of a [collection of notebooks](../index.ipynb) in the bachelors module Signals and Systems, Comunications Engineering, Universität Rostock. Please direct questions and suggestions to [Sascha.Spors@uni-rostock.de](mailto:Sascha.Spors@uni-rostock.de).*

# ## Definition
# 
# The [$z$-transform](https://en.wikipedia.org/wiki/Z-transform) is a transform which represents a discrete signal $x[k]$ in the spectral domain. It bases on the complex exponential function $z^{-k}$ with $z \in \mathbb{C}$ as kernel.

# ### Two-Sided $z$-Transform
# 
# The two-sided (or bilateral) $z$-transform is defined as
# 
# \begin{equation}
# X(z) = \sum_{k = -\infty}^{\infty} x[k] \, z^{-k}
# \end{equation}
# 
# where $X(z) = \mathcal{Z} \{ x[k] \}$ denotes the $z$-transform of $x[k]$. A complex signal $x[k] \in \mathbb{C}$ with discrete index $k \in \mathbb{Z}$ is represented by its complex valued $z$-transform $X(z) \in \mathbb{C}$ with complex dependent variable $z \in \mathbb{C}$. The variable $z$ can be interpreted as [complex frequency](../discrete_signals/standard_signals.ipynb#Complex-Exponential-Signal) $z = e^{\Sigma + j \Omega}$ with $\Sigma, \Omega \in \mathbb{R}$.
# 
# Whether a $z$-transform $X(z) = \mathcal{Z} \{ x[k] \}$ exists depends on the complex frequency $z$ and the signal $x[k]$ itself. All values $z$ for which the $z$-transform converges form a region of convergence (ROC). The $z$-transforms of two different signals may differ only with respect to their ROCs. Consequently, the ROC needs to be explicitly given for a unique inversion of the $z$-transform.

# ### One-Sided $z$-Transform
# 
# Causal signals play an important role in the theory of signals and systems. For a causal signal with $x[k] = 0$ for $k <0$, the relation $x[k] = x[k] \cdot \epsilon[k]$ holds. Introducing this into the definition of the two-sided $z$-transform results in
# 
# \begin{equation}
# X(z) = \sum_{k = -\infty}^{\infty} x[k] \cdot \epsilon[k] \, z^{-k} = \sum_{k = 0}^{\infty} x[k] \, z^{-k}
# \end{equation}
# 
# This motivates the definition of the one-sided (or unilateral) $z$-transform
# 
# \begin{equation}
# X(z) = \sum_{k = 0}^{\infty} x[k] \, z^{-k}
# \end{equation}
# 
# In the literature both the one- and two-sided $z$-transform are termed as $z$-transform. For causal signals both give the same result. The one-sided $z$-transform is also useful for the solution of initial value problems, for instance as defined by [linear difference equations with constant coefficients](../discrete_systems/difference_equation.ipynb) where the initial values are e.g. defined for $k \leq 0$.

# ### Signals of Finite Duration
# 
# The $z$-transform of a generic signal $x[k]$ of finite duration $x[k] = 0$ for $\{k : k < M_1 \wedge k \geq M_2\}$ with $M_1 < M_2$ reads
# 
# \begin{equation}
# X(z) = \sum_{k=M_1}^{M_2 - 1} x[k] \, z^{-k} = x[M_1] \, z^{-M_1} + x[M_1 + 1] \, z^{- (M_1 + 1)} + \dots + x[M_2 - 1] \, z^{- (M_2-1)}
# \end{equation}
# 
# The transform of a generic finite-length signal is given as a polynomial in $z$. Depending on the particular limits $M_1$ and $M_2$, the polynomial may contain powers of $z$ and $z^{-1}$. For a causal finite-length signal, above result specializes to the case $M_1 = 0$ and $M_2 > 0$ as
# 
# \begin{equation}
# X(z) = x[0] + x[1] \, z^{-1} + \dots + x[M_2 - 1] \, z^{- (M_2-1)}
# \end{equation}
# 
# The transform of a causal finite-length signal is given as a polynomial in $z^{-1}$. The ROC for this case is given as $z \in \mathbb{C} \setminus \{ 0 \}$. Similar considerations yield the $z$-transform and ROC of an anticausal signal. The ROCs for a generic finite-length signal can be summarized as
# 
# * $z \in \mathbb{C}$ for an anticausal signal ($M_1 < 0$, $M_2 \leq 0$)
# * $z \in \mathbb{C}_\infty$ if $x[k] = 0$ for $k \neq 0$ ($M_1 = 0$, $M_2 = 1$)
# * $z \in \mathbb{C} \setminus \{ 0 \}$ for a causal signal ($M_1 = 0$, $M_2 > 0$)
# 
# where $\mathbb{C}_\infty = \mathbb{C} \cup \{ \infty \}$ denotes the [set of extended complex numbers](https://en.wikipedia.org/wiki/Riemann_sphere).

# ### Transformation of the Rectangular Signal
# 
# The rectangular signal $x[k] = \text{rect}_N[k]$ is a causal signal of finite duration. Using above result its $z$-transform can be derived straightforward as
# 
# \begin{equation}
# \mathcal{Z} \{ \text{rect}_N[k] \} = \sum_{k=0}^{N-1} z^{-k} = 1 + z^{-1} + \dots + z^{-N + 1}
# \end{equation}
# 
# for $z \in \mathbb{C} \setminus \{ 0 \}$. Above sum can also be interpreted as [finite geometrical series](https://en.wikipedia.org/wiki/Geometric_series) with common ratio $\frac{1}{z}$, resulting in an alternative form of the $z$-transform of the rectangular signal
# 
# \begin{equation}
# \mathcal{Z} \{ \text{rect}_N[k] \} =  \begin{cases}
# \frac{1 - z^{-N}}{1 - z^{-1}} & \text{for } z \neq 1 \\
# N & \text{for } z = 1
# \end{cases}
# \end{equation}

# ### Transformation of the Dirac Impulse
# 
# The transform $\mathcal{Z} \{ \delta[k] \}$ of the [Dirac impulse](../discrete_signals/standard_signals.ipynb#Dirac-Impulse) is derived by introducing $\delta[k]$ into the definition of the two-sided $z$-transform and exploiting the sifting property of the Dirac impulse
# 
# \begin{equation}
# \mathcal{Z} \{ \delta[k] \} = \sum_{k = -\infty}^{\infty} \delta[k] \, z^{-k} = 1
# \end{equation}
# 
# for $z \in \mathbb{C}$. The ROC covers the entire complex plane.
# 
# The transform of the Dirac impulse is equal to one. Hence, all complex frequencies $z$ are present with equal weight. Since the Dirac impulse is used to characterize linear time-invariant (LTI) systems by their [impulse response](../discrete_systems/impulse_response.ipynb) $h[k] = \mathcal{H} \{ \delta[k] \}$, this constitutes an important property in the theory of discrete signals and systems, .

# **Example**
# 
# The $z$-transform of the Dirac impulse is computed by direct evaluation of its definition. The Dirac impulse is represented by the [Kronecker delta](https://en.wikipedia.org/wiki/Kronecker_delta) $\delta[k] = \delta_{k 0}$ in `SymPy`.

# In[1]:


import sympy as sym
sym.init_printing()
get_ipython().run_line_magic('matplotlib', 'inline')

k = sym.symbols('k', integer=True)
z = sym.symbols('z', complex=True)

X = sym.summation(sym.KroneckerDelta(k, 0) * z**(-k), (k, -sym.oo, sym.oo))
X


# **Exercise**
# 
# * Derive the two-sided $z$-transform of a shifted Dirac impulse $\delta[t - \kappa]$ for $\kappa \in \mathbb{Z}$ by manual evaluation of its definition and by modification of above example. Provide the ROC for the three cases $\kappa<0$, $\kappa=0$ and $\kappa>0$.
# 
# * Derive the one-sided $z$-transform of a shifted Dirac impulse $\delta[t - \kappa]$. Hint: Differentiate between the cases $\kappa < 0$ and $\kappa \geq 0$.

# ### Transformation of the Causal Complex Exponential Signal
# 
# The transform $X(z) = \mathcal{Z} \{ x[k] \}$ of the causal complex exponential signal
# 
# \begin{equation}
# x[k] = \epsilon[k] \cdot z_0^k
# \end{equation}
# 
# with complex frequency $z_0 \in \mathbb{C}$ is derived by evaluation of the definition of the one-sided $z$-transform
# 
# \begin{equation}
# X(z) = \sum_{k=0}^{\infty} z_0^k \cdot z^{-k} = \sum_{k=0}^{\infty} \left( \frac{z_0}{z} \right)^k = \frac{z}{z - z_0}
# \end{equation}
# 
# The last equality has been derived by noting that the sum constitutes an [infinite geometrical series](https://en.wikipedia.org/wiki/Geometric_series) with common ratio $\frac{z_0}{z}$ which converges for $\left| \frac{z_0}{z} \right| < 1$. The ROC is consequently given as
# 
# \begin{equation}
# |z| > |z_0|
# \end{equation}
# 
# Combining above results, the transformation of the causal complex exponential signal reads
# 
# \begin{equation}
# \mathcal{Z} \{ \epsilon[k] \cdot z_0^k \} = \frac{z}{z - z_0} \qquad \text{for } |z| > |z_0|
# \end{equation}

# **Example**
# 
# The $z$-transform of the causal complex exponential signal $x[k] = z_0^k \cdot \epsilon[k]$ with $z_0 \in \mathbb{C}$ is computed by direct evaluation of its definition.

# In[2]:


z0 = sym.symbols('z0')

X = sym.summation(z0**k * z**(-k), (k, 0, sym.oo))
X


# Note that the sum is returned in case that it cannot be evaluated. It hence can be concluded that the series converges only for $|\frac{z_0}{z}| < 1$. This is in line with the analytic result derived above.

# ## Convergence
# 
# The definition of the $z$-transform constitutes an infinite series. A sufficient but not necessary condition for the convergence of an infinite series is that its elements are absolutely summable. Applying this to the definition of the two-sided $z$-transform $X(z) = \mathcal{Z} \{ [k] \}$ of a given signal $x[k]$ yields
# 
# \begin{equation}
# \sum_{k = -\infty}^{\infty} | x[k] \cdot z^{- k} | = \sum_{k = -\infty}^{\infty} | x[k] | \cdot | z |^{- k}  < \infty
# \end{equation}
# 
# It can be concluded from this result that the ROC is determined solely by the magnitude $|z|$ of the complex frequency. It follows further that the ROC is given as a ring in the $z$-plane which may include $z=0$ and/or $z=\infty$. The phase $\Omega$ of the complex frequency $z$ has no effect in terms of convergence, as $z = e^{\Sigma} \cdot e^{j \Omega}$.
# 
# For a right-sided signal of infinite length with $x[k] = 0$ for $k < M$, the ROC is given in the form of $|z| > a$ with $a \in \mathbb{R}^+$. This can be concluded from the decay of the term $| z |^{- k}$ for $k \to \infty$, which ensures convergence for a given $a$. However this holds only for signals $x[k]$ with [exponential growth](https://en.wikipedia.org/wiki/Exponential_growth). Please refer to the $z$-transform of the causal exponential signal derived above. 
# 
# The same reasoning leads to the ROCs of a left-sided and two-sided signal. The resulting ROCs are illustrated in the following
# 
# ![Region of convergence for left-/two-/right-sided signals](ROC.png)
# 
# The gray areas denote the values $z$ for which the $z$-transform converges. The borders $a$ of these areas (dashed lines) depend on the signal $x[k]$. In case that the $z$-transform $X(z)$ is given in terms of a rational function in $z$, the ROC has to be chosen such that it does not include zeros of the denominator polynomial. A more detailed discussion of the ROCs for the $z$-transform can be found in the literature, e.g. [[Girod et al.](index.ipynb#Literature)].

# ## Relation to the Laplace Transform of a Sampled Signal
# 
# The link between the Laplace transform of a sampled signal $x_\text{s}(t)$ and the $z$-transform of its discrete counterpart $x[k] = x(k T)$ is established in the following. Under the assumption of [ideal sampling](../sampling/ideal.ipynb#Model-of-Ideal-Sampling), the sampled signal reads
# 
# \begin{equation}
# x_\text{s}(t) = \sum_{k = -\infty}^{\infty} x(k T) \cdot \delta(t - k T) = \sum_{k = -\infty}^{\infty} x[k] \cdot \delta(t - k T)
# \end{equation}
# 
# where $x(t)$ denotes the continuous signal and $T$ the sampling interval. Introducing the sampled signal into the [definition of the Laplace transform](../laplace_transform/definition.ipynb) yields the transform of the sampled signal
# 
# \begin{equation}
# X_\text{s}(s) = \int_{-\infty}^{\infty} \sum_{k = -\infty}^{\infty} x[k] \cdot \delta(t - k T) \, e^{- s t} \; dt = \sum_{k = -\infty}^{\infty} x[k] \, e^{-s k T}
# \end{equation}
# 
# where the last equality has been derived by changing the order of summation/integration and exploiting the [sifting property of the Dirac impulse](../continuous_signals/standard_signals.ipynb#Dirac-Impulse). Comparison with the definition of the $z$-transform yields
# 
# \begin{equation}
# X_\text{s}(s) = X(z) \big\rvert_{z = e^{s T}}
# \end{equation}
# 
# The spectrum of the sampled signal $X_\text{s}(s)$ is equal to the $z$-transform of the discrete Signal $X(z)$ for $z = e^{s T}$. The resulting mapping from the $s$-plane to the $z$-plane is illustrated by the shading and the colors in the following figure
# 
# ![Mapping of the $s$-plane onto the $z$-plane](mapping_s_z_plane.png)
# 
# The Laplace transform of a sampled signal is peridoic with respect to the frequency $\omega$. It sufficient to consider the strip $-\frac{\pi}{T} < \Im \{ s \} < \frac{\pi}{T}$ of the $s$-plane for the mapping. The left half-plane of the $s$-plane is mapped into the unit circle of the $z$-plane. The corresponding right half-plane is mapped to the outside of the unit circle. The imaginary axis of the $s$-plane is mapped onto the unit circle $|z|=1$. The frequency $s=0$ is mapped onto $z=1$ and the frequencies $s=\pm j \frac{\pi}{T}$ are mapped onto $z=-1$.

# ## Representation
# 
# The $z$-transform $X(z) = \mathcal{Z} \{ x[k] \}$ depends on the complex frequency $z \in \mathbb{C}$ and is in general complex valued $X(z) \in \mathbb{C}$. It can be illustrated by plotting its magnitude $|X(z)|$ and phase $\varphi(z)$ or real $\Re \{ X(z) \}$ and imaginary $\Im \{ X(z) \}$ part in the complex $z$-plane. The resulting three-dimensional plots are often not very illustrative.
# 
# However, many $z$-transforms of interest in the theory of signals and systems are [rational functions](https://en.wikipedia.org/wiki/Rational_function) in $z$. The polynomials of the numerator and denominator can be represented by their complex [roots](https://en.wikipedia.org/wiki/Zero_of_a_function#Polynomial_roots) and a constant factor. The roots of the numerator are termed as *zeros* while the roots of the denominator a termed as *poles* of $X(z)$. The polynomial and the zero/pole representation of a rational $z$-transform are equivalent
# 
# \begin{equation}
# X(z) = \frac{\sum_{m=0}^{M} \beta_m \, z^{-m}}{\sum_{n=0}^{N} \alpha_n \, z^{-n}} = K \cdot \frac{\prod_{\mu=0}^{Q} (z - z_{0 \mu})}{\prod_{\nu=0}^{P} (z - z_{\infty \nu})}
# \end{equation}
# 
# where $M$ and $N$ denote the order of the numerator/denominator polynomial, $z_{0 \mu}$ and $z_{\infty \nu}$ the $\mu$-th zero/$\nu$-th pole of $X(z)$, and $Q = M-1$ and $P = N-1$ the total number of zeros and poles, respectively. For $M=N$ the factor $K = \frac{\beta_M}{\alpha_N}$. If 
# 
# * $M > N$ at least one pole is located at $|z| = \infty$,
# * $M < N$ at least one pole is located at $z = 0$.
# 
# It is common to illustrate the poles and zeros in a [pole-zero plot](https://en.wikipedia.org/wiki/Pole%E2%80%93zero_plot). Here the locations of the complex poles and zeros, their degrees and the factor $K$ are plotted in the $z$-plane. It is common to include the unit circle $|z| = 1$ in the plot due to its relevance in the theory of discrete signals and systems. An example for a pole-zero plot is shown in the following
# 
# ![Exemplary pole-zero plot](pz_plot.png)
# 
# The locations of the poles and zeros provide insights into the composition of a signal. For instance, the $z$-transform of the [complex exponential signal](#Transformation-of-the-Causal-Complex-Exponential-Signal) has a zero at $z=0$ and a pole at $z = z_0$. A signal which is composed from a superposition of complex exponential signals will have multiple poles whose positions are related to the complex frequencies of the signals it is composed of.

# **Exercise**
# 
# * Derive $X(z)$ together with its ROC from above pole-zero plot under the assumption that it represents a right-sided signal $x[k]$.

# **Example**
# 
# The $z$-transform of the causal complex exponential signal
# 
# \begin{equation}
# X(z) = \frac{z}{z - z_0} \qquad \text{for } |z| > |z_0|
# \end{equation}
# 
# derived above is illustrated by plotting its magnitude $|X(z)|$ over the $z$-plane for $z_0 = 1 + j$

# In[3]:


rez, imz = sym.symbols('rez imz', real=True)

X = z / (z - z0)
X1 = X.subs({z: rez+sym.I*imz, z0: 1+sym.I})

sym.plotting.plot3d(abs(X1), (rez, -2, 2), (imz, -2, 2),
                    xlabel=r'$\Re\{z\}$', ylabel=r'$\Im\{z\}$', title=r'$|X(z)|$');


# Alternatively, the $z$-transform $X(z)$ is illustrated by its pole-zero plot. First the poles

# In[4]:


poles = sym.roots(sym.denom(X), z)
poles


# and zeros are computed

# In[5]:


zeros = sym.roots(sym.numer(X), z)
zeros


# Above dictionaries are composed from the poles and zeros, and their degrees. 
# 
# In order to illustrate the location of poles and zeros in the $z$-plane, the pole-zero plot is shown for $z_0 = 1 + j$

# In[6]:


from pole_zero_plot import pole_zero_plot

X2 = X.subs(z0, 1+sym.I)
pole_zero_plot(sym.roots(sym.denom(X2), z), sym.roots(sym.numer(X2), z))


# **Copyright**
# 
# The notebooks are provided as [Open Educational Resource](https://de.wikipedia.org/wiki/Open_Educational_Resources). Feel free to use the notebooks for your own educational purposes. The text is licensed under [Creative Commons Attribution 4.0](https://creativecommons.org/licenses/by/4.0/), the code of the IPython examples under the [MIT license](https://opensource.org/licenses/MIT). Please attribute the work as follows: *Lecture Notes on Signals and Systems* by Sascha Spors.