Week 9

In the next phase of the course we are going to introduce some new transforms in order to handle a class of problems that we could not handle previously with the Fourier transform. Recall some of the Fourier transform issues. We talked about


(a) {\bf absolutely summable signals}


These signals have fourier transforms that are continuously infinitely differentiable and well-defined. Let's say that we have $x(n) = \alpha^n u(n)$ where $\abs{\alpha} \lt 1$. What was the frequency response? The transform of this particular signal is $\frac{1}{1-\alpha e^{-i\omega}}$. If you were to write this in terms of $e^{i\omega}$, this expression is differentiable and smooth when you plot it. As a complex function it is a perfectly smooth function and infinitely differentiable. All finite-length signals also have this property. For example, $x(n) = \delta(n+1) + \delta(n) + \delta(n-1)$. With finite length signals we never have an issue the convergence of the fourier transform. \\

Absolutely summable signals can be defined as 

\begin{nicebox}
$$l^1 : \{ x: \Z \to \C \st \sum_{n \in \Z} \abs{x(n)} \lt \infty \}$$
\end{nicebox}

Another class of signals that we have discussed are


(b) {\bf square summable (finite-energy signals)}

\begin{nicebox}
$$l^2 : \{ x: \Z \to \C \st \sum_{n \in \Z} \abs{x(n)}^2 \lt \infty \}$$
\end{nicebox}

Consider a function that is square summable but not absolutely summable, that is, $x \in l^2 \setminus l^1$. An example of this is $x(n) = \frac{1}{\pi n} \sin(A n)$. $X(\omega)$ has discontinuities. We have also discussed signals that are


(c) not absolutely or square summable signals

If $x \notin l^1 \cup l^2 \Rightarrow$ ``All bets are off''. There are only two cases:

        i) DTFT Defined $\Rightarrow$ DTFT will have diracs. 
An example of this type of signal is $x(n) = e^{i\omega_0 n}$. $X(\omega) = \delta(\omega - \omega_0)$ for $\abs{\omega} \lt \pi$.

		ii) DTFT not defined.
An example of this type of signal is $x(n) = \alpha^n u(n)$ where $\abs{\alpha} \gt 1$.
    

There is another class of signals called bounded signals, which are given by

\begin{nicebox}
$$l^\infty : \{ x: \Z \to \C \st \abs{x(n)} \lt M \lt \infty \mbox{ } \forall n \}$$
\end{nicebox}


Why use Z-Transforms

In the time domain convolution can be well-defined even if one of the signals $x \notin l^1 \cup l^2$ (not absolutely summable or square summable) and $x$ has no DTFT. This is a category where we cannot talk about a frequency response or fourier transform. Consider where this type of a signal is passed through a system with a finite impulse response:

$$
x(n) = \alpha^n u(n) \to \fbox{FIR} \to y(n)
$$

We know that $y(n)$ is the convolution of the two signals.

\begin{align*}
y(n) &= \sum\limits_{k\in\Z}x(k)h(n-k) \\
y(n) &= \sum\limits_{k\in\Z}\alpha^{k}u(k)h(n-k) \\
\end{align*}

This system has well defined response for this growing exponential. Why is the output bounded even though the input to this system is unbounded and has no transform? We can't talk about frequency response or about multiplying $X(\omega)$ with the filter's frequency response because $X(\omega)$ does not exist. But this system has a well-defined response! Suppose for now that the domain of $h$ is in $\{-1,0,1\}$ (it is a FIR).

\begin{align*}
y(n) &= \sum\limits_{k\in\Z}h(k)x(n-k) \\
y(n) &= h(-1)x(n+1) + h(0)x(n) + h(1)x(n-1) \\
\end{align*}

We have a finite number of terms, so we are only summing a finite number of the values of the input. Another example is when you have two right-sided functions.

\begin{definition}
A function is \emph{right-sided} $\iff x(n) = 0 \mbox{ } \forall n \lt N \lt \infty$
\end{definition}


% \img{images/rightleftsided/def/r.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-4,-1)(4,3)
    
\rput(3.3,0.5){$\cdots$}

\psline{-*}(-3,0)(-3,0)
\psline{-*}(-2,0)(-2,0)
\psline{-*}(-1,0)(-1,0)
\psline{-*}(0,0)(0,1)
\rput(0,-0.3){N}
\psline{-*}(1,0)(1,0.1)
\psline{-*}(2,0)(2,0.4)
\psline{-*}(3,0)(3,0.9)

% axes
\psline{->}(-4,0)(4,0)
\rput(4,-0.3){ $n$ }
\rput(4,1){ $x(n)$ }

\end{pspicture}
\end{center}


Note that $x$ is causal if $N=0$. This implies that causal signals are a subset of right-sided signals.

\begin{definition}
A function is \emph{left-sided} $\iff x(n) = 0 \mbox{ } \forall M \lt n \lt \infty$
\end{definition}

% \img{images/rightleftsided/def/l.ps}

\begin{center}
\begin{pspicture}(-4,-1)(4,3)
    
\psline{-*}(-3,0)(-3,0.7)
\psline{-*}(-2,0)(-2,0.4)
\psline{-*}(-1,0)(-1,1)
\psline{-*}(0,0)(0,0.4)
\rput(0,-0.3){M}
\psline{-*}(1,0)(1,0)
\psline{-*}(2,0)(2,0)
\psline{-*}(3,0)(3,0)
% axes
\psline{->}(-4,0)(4,0)
\rput(4,-0.3){ $n$ }
\rput(4,1){ $x(n)$ }
\rput(-3.3,0.5){ $\cdots$ }

\end{pspicture}
\end{center}

Note that $x$ is anti-causal if $M=0$. This implies that anti-causal signals are a subset of left-sided signals. Lets continue with some examples.

\begin{example}

Lets look at a situation where convolution is well-defined but at least one of the functions doesn't have a DTFT.

$$
x(n) = \alpha^n u(n) \to \bbox[5px,border:1px solid black]{\beta^n u(n)} \to y(n)
$$

Note that convolution is defined if $\abs{\alpha} \gt 1$ or $\abs{\beta} \gt 1$ or both.

\begin{align*}
y(n) &= \sum\limits_{k\in\Z} \alpha^k u(k) \beta^{n-k} u(n-k) \\
y(n) &= \sum\limits_{k = 0}^{\infty} \alpha^k \beta^{n-k} u(n-k) \\
y(n) &= \begin{cases} \sum\limits_{k=0}^{n}\alpha^k\beta^{n-k} & n\geq0 \\ 0 & \mbox{otherwise} \\ \end{cases}
\end{align*}

We can also see that the ``overlap'' of the signals is finite because we are convolving two right-sided signals. When you have $x(n)$ and $h(n-m)$, there must be some $N$ that zeros out all values $n \lt N$ due to $x$, and zeros for all $n \gt n-M$ due to $h$. There are two finite endpoints, and they have a finite overlap.

% \img{images/rightleftsided/finite/comb.ps}

\begin{center}
\begin{pspicture}(-3,-4)(6,3)
    
\psframe[linestyle=dashed](0.5,-3.5)(3.5,1.5)

% axes
\psline{->}(-2,-3)(6,-3)
\rput(6,-3.3){ $k$ }
\rput(-1.75,-1.5){ $\cdots$ }
\rput(6,-1.5){ $h(n-k)$ }
% axes
\psline{->}(-2,0)(6,0)
\rput(6,-0.3){ $k$ }
\rput(6,2.5){ $x(k)$ }
\rput(5.75,1.5){ $\cdots$ }

\psline{-*}(-1,-3)(-1,-0.5)
\psline{-*}(0,-3)(0,-1.4)
\psline{-*}(1,-3)(1,-2.1)
\psline{-*}(2,-3)(2,-2.6)
\psline{-*}(3,-3)(3,-2.9)
\rput(3,-3.2){n-M}

\psline{-*}(1,0)(1,0.1)
\rput(1,-0.3){N}
\psline{-*}(2,0)(2,0.4)
\psline{-*}(3,0)(3,0.9)
\psline{-*}(4,0)(4,1.6)
\psline{-*}(5,0)(5,2.5)

\end{pspicture}
\end{center}

\end{example}

Right and Left-sided Functions

Consider an LTI system with an impulse response $h(n)$:

$$ 
x(n) \to \bbox[5px,border:1px solid black]{h(n)} \to y(n) 
$$

What happens when $x(n) = z^n$, where $z = r e^{i\omega}$? Plug these two functions in to the convolution sum and solve:

\begin{align*}
y(n) &= \sum \limits_{k\in\Z} h(k) z^{n-k} \\
y(n) &= z^n \lr{\sum \limits_{k\in\Z} h(k) z^{-k}} \\
\end{align*}


We get $z^n \sum_{k\in\Z} h(k) z^{-k}$. We did exactly this in EE20 when we talked about the Eigen function properties of the complex exponential. It turns out $e^{i\omega n}$ does not define the entire space of complex exponentials that can have that property. \emph{Any} complex number raised to the $n^{th}$ power will come out at the other end scaled by some number. With that said, $\sum \limits_{k\in\Z} h(k) z^{-k}$ defines the transfer function of the system, $\hat{H}(z)$, a.k.a. the system function. This function is the \emph{Z-Transform} of the impulse response:

\begin{nicebox}
$$
\hat{X}(z) = \sum \limits_{n\in\Z} h(n) z^{-n}
$$
\end{nicebox}

Just as before we had a frequency response with fourier transforms, we have the transfer function with Z transforms.

\begin{nicebox}
\begin{align*}
h(n) &\ftp H(\omega) = \sum \limits_{n\in\Z} h(n) e^{-i\omega n} \\
h(n) &\ztp \hat{H}(z) = \sum \limits_{n\in\Z} h(n) z^{-n}
\end{align*}
\end{nicebox}

Lets expand this where $z = re^{i\omega}$:

$$
\hat{H}(z) = \sum \limits_{n\in\Z} h(n) r^{-n}e^{-i\omega n} = \ftrans{h(n)r^{-n}}
$$

This $r$ allows us to fly off the nest, which has been the unit circle. In the Z-transform we allow ourselves to go inside or outside the unit circle and gain flexibility in that way it is possible to deal with a function $h(n)$ that does not have fourier transform, because $h(n)r^{-n}$ does. We can potentially pick values of $r$, not on the unit circle, such that multiplying the function $h(n)$ with $r^{-n}$ tames whatever growth might occur.   

\begin{example}

Consider an impulse response given by $h(n) = 3^n u(n)$. $H(\omega)$ is undefined. Lets use the transfer function:

\begin{align*}
\hat{H}(z) &= \sum \limits_{n\in\Z} h(n)z^{-n} \\
\hat{H}(z) &= \sum \limits_{n\in\Z} 3^n u(n) z^{-n} \\
\hat{H}(z) &= \sum \limits_{n = 0}^{\infty} 3^n z^{-n} \\
\hat{H}(z) &= \sum \limits_{n = 0}^{\infty} \lr{3z^{-1}}^n \\
\hat{H}(z) &= \frac{1}{1 - 3z^{-1}} \mbox { if } \abs{3z^{-1}} \lt 1 \\
\end{align*}

The sum converges provided $\abs{3z^{-1}} \lt 1$, which is reduces to $\abs{z} \gt 3$. This makes sense because the radius is the magnitude of $z$. If we look at the sum and explicity solve with $r$, we get the same result:

\begin{align*}
\hat{H}(z) &= \sum \limits_{n = 0}^{\infty} 3^n \lr{re^{i\omega}}^{-n} \\
\hat{H}(z) &= \sum \limits_{n = 0}^{\infty} \lr{\frac{3}{z}}^n e^{-i\omega n} \\
\end{align*}

We found that the Z-transform was associated with a \emph{Region of Convergence}, an $RoC$. This regions contains the set of points in the complex plane which correspond to values of $z$ which provide convergence for the Z-transform. Note that when you break up $z$ into its polar form, $re^{i\omega}$, only the radius $r$ determines the range of convergence. If you find a particular radius for which an infinite series converges, any point on that circle will be perfectly fine as far as convergence is concerned.

\end{example}

{\bf Question}

1) For a function to have both a Z-transform and a DTFT, what must be true about the $RoC$ of the function? 

2) How can you get $H(\omega)$ from $\hat{H}(z)$?

{\bf Answer}


1) The $RoC$ must include the unit circle. That is, $\abs{z} = 1 \subset RoC(h)$. 

2) $H(\omega) = \left. \hat{H}(z) \right|_{z = e^{i\omega}}$


The Z-Transform


1) Given a signal $x(n) = \lr{\frac{3}{4}}^nu(n)$, find the Z-transform and the DTFT.



First, the Z-transform:

\begin{align*}
x(n) &= \lr{\frac{3}{4}}^n u(n) \\
\hat{X}(z) &= \sum \limits_{n\in\Z}\lr{\frac{3}{4}}^n u(n)z^{-n} \\
\hat{X}(z) &= \sum \limits_{n = 0}^{\infty}\lr{\frac{3}{4}}^n z^{-n} \\
\hat{X}(z) &= \sum \limits_{n = 0}^{\infty}\lr{\frac{3}{4} z^{-1}}^n \\
\hat{X}(z) &= \frac{1}{1 - \frac{3}{4} z^{-1}} \mbox{ if } \abs{\frac{3}{4} z^{-1}} \lt 1 \\
\end{align*}

The convergence of this sum relies on $\abs{\frac{3}{4} z^{-1}} \lt 1$, which reduces to $\frac{3}{4} \lt \abs{z}$. Now lets find the DTFT:

\begin{align*}
X(\omega) &= \sum \limits_{n \in \Z} \lr{\frac{3}{4}}^n u(n) e^{-i\omega n} \\
X(\omega) &= \sum \limits_{n \in \Z_\oplus} \lr{\frac{3}{4}}^n e^{-i\omega n} \\
X(\omega) &= \sum \limits_{n \in \Z_\oplus} \lr{\frac{3}{4} e^{-i\omega}}^n \\
X(\omega) &= \frac{1}{1 - \frac{3}{4} e^{-i\omega}} \\
\end{align*}

Note that we could have also used the fact that $X(\omega) = \left. \hat{X}(z)\right|_{z = e^{i\omega}}$. 




2) Given a signal $g(n) = -\lr{\frac{3}{4}}^n u(-n-1)$, what is $\hat{G}(z)$?



We know that $u(-n-1) = 0 $ whenever $-n -1 \lt 0 \Rightarrow u(-n-1) = 0 \mbox { } \forall n \gt -1$.

\begin{align*}
\hat{G}(z) &= \sum \limits_{n = -\infty}^{\infty}-\lr{\frac{3}{4}}^n u(-n-1)z^{-n} \\
\hat{G}(z) &= -\sum \limits_{n = -\infty}^{-1}\lr{\frac{3}{4}}^n z^{-n}  \\
\hat{G}(z) &= -\sum \limits_{n = -\infty}^{-1}\lr{\frac{3}{4}z^{-1}}^n  \\
\hat{G}(z) &= -\sum \limits_{n = 1}^{\infty}\lr{\frac{3}{4}z^{-1}}^{-n} \quad \mbox{ let } n = -n  \\
\hat{G}(z) &= -\sum \limits_{n = 1}^{\infty}\lr{\frac{4}{3}z}^n \\
\hat{G}(z) &= -\sum \limits_{n = 0}^{\infty}\lr{\frac{4}{3}z}^{n+1} \quad \mbox{ shift index by } 1 \\
\hat{G}(z) &= -\frac{4}{3}z \sum \limits_{n = 0}^{\infty}\lr{\frac{4}{3}z}^n\\
\hat{G}(z) &= -\frac{\frac{4}{3}z}{1- \frac{4}{3}z} \quad \mbox{ if } \abs{\frac{4}{3}z} \lt 1\\
\end{align*}

The region of convergence reduces to $\abs{Z} \lt \frac{3}{4}$, and the expression for $\hat{G}(z)$ reduces to $\frac{4z}{4z-3}$.


9.2 Z-Transforms