Let $h(n)$ denote the \emph{impulse response} of systems $H$ to the input signal $x(n)$. For example, let $x(n)=\delta (n) + 2\delta (n-1)$ then $y(n) = h(n) + 2h(n-1)$, such that 
$$ x(n) = \delta(n) + 2\delta(n-1) \to \fbox{H} \to h(n) + 2h(n-1) = y(n)$$

This is because the system is defined to be time invariant. An arbitrary signal can then be decomposed into linear combinations of shifted impulses:

$$ x(n) =\cdots + x(-1)\delta(n+1) + x(0)\delta(n) + x(1)\delta(n-1) + \cdots $$
$$ y(n) =\cdots + x(-1)h(n+1) + x(0)h(n) + x(1)h(n-1) + \cdots $$

Since we are talking about DT signals, this brings us to a summation formula. The \emph{convolution sum} is denoted as 

$$ y(n) = \sum \limits _{m=-\infty}^\infty x(m)h(n-m) = (x * h)(n)$$

The convolution of the input signal with the impulse response gives us the output of a linear time-invariant system. But what about the convolution of the impulse response with the input signal? Let $k = n - m$, then we write the formula as follows:

$$ y(n) = \sum \limits _{k=\infty}^{-\infty} x(n-k)h(k) = \sum \limits _{k=-\infty}^{\infty} h(k)x(n-k) = (h * x)(n)$$

Notice that the limits did switch, but since it is a summation it does not affect the value. This demonstrates an important property of convolution sums, \emph{commutativity}:
$$ x * h = h * n $$

The roles of input response can be change or reversed:

$$ x \to \fbox{h} \to y $$
$$\mbox{  or  }$$
$$ h \to \fbox{x} \to y$$

Both produce the same output signal of the LTI. Note, if a system has an impulse response $h$, this usually implies that it is an LTI system.

Linear Time-Invariant Systems

As shown earlier, the \emph{convolution sum} can be defined as 

\begin{nicebox}
\begin{align*}
y(n) &= \sum \limits _{m \in \Z} x(m)h(n-m) = (x * h)(n)
\end{align*}
\end{nicebox}

or using the commutative property of convolution we can write 

\begin{nicebox}
\begin{align*}
y(n) &=  \sum \limits _{k \in \Z} h(k)x(n-k) = (h * x)(n)
\end{align*}
\end{nicebox}

where $h(n)$ denotes the \emph{impulse response} of systems $H$ to the input signal $x(n)$, defined as 
$$x(n) =\cdots + x(-1)\delta(n+1) + x(0)\delta(n) + x(1)\delta(n-1) + \cdots \mbox{,}$$
and the output signal of the LTI system $y(n)$ is defined as 
$$ y(n) =\cdots + x(-1)h(n+1) + x(0)h(n) + x(1)h(n-1) + \cdots \mbox{.} $$

Note that $x * \delta = \delta * x = x$. In other words, $\delta(n)$ is the identity element of the convolution sum.

\begin{problem}
Determine the output signal of the following:
%\begin{figure}[htp]
%\centering
%\includegraphics{images/conv50.ps}
%\caption{ $h(n) = \delta(n-50)$, $x(n)=\delta(n) + 2\delta(n-1)$ }
%\label{ fig:conv50 }
%\end{figure}

$h(n) = \delta(n-50)$, $x(n)=\delta(n) + 2\delta(n-1)$

\begin{center}
\begin{pspicture}(-3,-1)(3,4.3)
	% line
\psline{-*}(0,0)(0,1)
%  value
\rput(0.25,1){(1)}
%  position
\rput(0,-0.4){50}
% axes
\psline{->}(-3,0)(3,0)

\rput(3,-0.3){ $n$ }
\rput(2.5,4){ $x(n)$ }
\rput(3,1.7){ $n$ }
\rput(2.5,1.2){ $h(n)$ }


\psline{-*}(0.000,2)(0.000,3)
\psline{-*}(1.000,2)(1.000,4)
%  value
\rput(0.25,3){(1)}
\rput(1.25,4){(2)}
%  position
\rput(0,1.6){0}
\rput(1,1.6){1}
% axes
\psline{->}(-3,2)(3,2)

	
\end{pspicture}
\end{center}

$h(n) = \delta(n-50)$, $\quad x(n)=\delta(n) + 2\delta(n-1)$.

\end{problem}

\begin{solution}
There are many ways to look at this, here we go over an algebraic approach:
\item $h(n) = \delta(n-50)$, $\quad x(n)=\delta(n) + 2\delta(n-1)$.


\begin{align*}
y(n) &= \sum \limits _{m \in \Z} x(m)h(n-m) = (x * h)(n) \\
y(n) &= x(0)h(n) + x(1)h(n-1) \\
y(n) &= 1\cdot h(n) + 2\cdot h(n-1) \\
y(n) &= \delta(n-50) + 2\delta(n-51) 
\end{align*}


This shows us that $y(n) = x(n-50) = \delta(n-50) + 2\delta(n-51)$. Note that this could have been done with one term if we use the formula $y(n) = (h * x)(n) = \sum_{k\in\Z} h(k)x(n-k)$. In that form we could have done $h(50)x(n-50) = \delta(n-50) + 2\delta(n-51)$. Here the system can be represented as $ x(n) \to \fbox{ $\delta(n-50)$} \to x(n-50) = y(n) $.

%\begin{figure}[htp]
%\centering
%\includegraphics{images/conv50ans.ps}
%\caption{ $y(n) = x(n-50)$ }
%\label{ fig:conv50ans }
%\end{figure}

\begin{center}
\begin{pspicture}(-1,-1)(3,3)
	% line
\psline{-*}(0.000,0)(0.000,1)
%  value
\rput(0.25,1){(1)}
%  position
\rput(0.000,-0.4){50}
% line
\psline{-*}(1.000,0)(1.000,2)
%  value
\rput(1.25,2){(2)}
%  position
\rput(1.000,-0.4){51}
% axes
\psline{->}(-1.5,0)(3,0)
\rput(2.5,-0.3){ $n$ }
\rput(2,2){ $y(n)$ }
	
\end{pspicture}
\end{center}

\end{solution}

\begin{problem}
$h(n) = \delta(n) + \delta(n-1)$, $\quad x(n)=\delta(n) + 2\delta(n-1)$.
\end{problem}

\begin{solution}
Here is our system: $$ x(n) \to \fbox{ $\delta(n) + \delta(n-1)$} \to x(n) + x(n-1) = y(n) $$

\begin{align*}
y(n) &= \sum \limits _{m \in \Z} x(m)h(n-m) = (x * h)(n) \\
y(n) &= x(0)h(n) + x(1)h(n-1) \\
y(n) &= 1\cdot h(n) + 2\cdot h(n-1) \\
y(n) &= \left[ \delta(n) + \delta(n-1) \right] + 2 \left[ \delta(n-1) + \delta(n-2) \right] \\
y(n) &= \delta(n) + 3\delta(n-1) + 2\delta(n-2)
\end{align*}
\end{solution}

Here is a cool method for solving a convolution problem in discrete time:

Let the impulse response $h(n) = 5\delta(n) + 3\delta(n-1) +5\delta(n-2) + 2\delta(n-3)$ be represented as a vector, 
$
\left[
\begin{array}{c}
5 \\
3 \\
5 \\
2
\end{array}
\right]
$.

Now, let the input signal $x(n) = 3\delta(n) + 2\delta(n-1) + \delta(n-2)$ be represented as a matrix:
$
\left[
\begin{array}{cccc}
3 & 0 & 0 & 0 \\
2 & 3 & 0 & 0 \\
1 & 2 & 3 & 0 \\
0 & 1 & 2 & 3 \\
0 & 0 & 1 & 2 \\
0 & 0 & 0 & 1 
\end{array}
\right]
$. 

Then multiply the matrices:

$
\left[
\begin{array}{cccc}
3 & 0 & 0 & 0 \\
2 & 3 & 0 & 0 \\
1 & 2 & 3 & 0 \\
0 & 1 & 2 & 3 \\
0 & 0 & 1 & 2 \\
0 & 0 & 0 & 1 
\end{array}
\right]
\cdot
\left[
\begin{array}{c}
5 \\
3 \\
5 \\
2
\end{array}
\right]
=
\left[
\begin{array}{c}
15 \\
19 \\
26 \\
19 \\
9 \\
2
\end{array}
\right]
= 15\delta(n) + 19\delta(n-1) + 26\delta(n-2) + 19\delta(n-3) + 9\delta(n-4) + 2\delta(n-5)
$


Convolution

When determining $y(n) = (x * h)(n)$, what if we use $x(n) = e^{i\omega n}$?

\begin{align*}
y(n) &= \sum \limits_{k\in\Z}h(k)x(n-k) \\
y(n) &= \sum \limits_{k\in\Z}h(k)e^{i \omega (n-k)} \\ 
y(n) &= \left( \sum \limits_{k\in\Z}h(k)e^{-i \omega k} \right) e^{i \omega n} \\ 
y(n) &= H(\omega)e^{i \omega n}
\end{align*}

Since the summation part of the formula has no dependency on $n$, it relies entirely on the frequency $\omega$, thus $H(\omega)$ is the \emph{frequency response}. $H(\omega)$ is generally complex-valued. The magnitude $\left| H(\omega) \right|$ is known as the \emph{magnitude response}, or magnitude of frequency response, and the phase $\angle H(\omega)$ is the \emph{phase response}.

A system where the input signal is a complex exponential can be described as follows:

$$ e^{i \omega n} \to \fbox{H} \to H(\omega) e^{i \omega n}$$

We say that complex exponentials are eigenfunctions of LTI systems($A\vec{v}=\lambda\vec{v}$). Note that $\omega$ plots are continuous, even though the output signal is in discrete time. Generally we plot $\omega$ in $2\pi$ intervals from $-\pi$ to $\pi$.

\begin{problem}
Can the system be LTI?
$$ e^{i\frac{\pi}{4}n} \to \fbox{F} \to e^{i\frac{\pi}{3}n} $$
\end{problem}

\begin{solution}
Not linear time-invariant, since LTI systems cannot create new frequencies. They can, however, eliminate frequencies in the input.
\end{solution}


Frequency Response

\begin{problem}
Determine if the following signals are time-invariant.
\begin{enumerate}
\item $y(t) = \Re(x(t))$
\item $y(t) = \cos ( x(t) )$
\item $y(t) = \sum \limits_{k=0}^{n}x(k)$
\item $y(t) = x(4n+1)$
\item $y(t) = \int^{2t}_{-\infty}x(\tau)d\tau$
\end{enumerate}
\end{problem}

\begin{solution}
Here are the solutions:
\begin{enumerate}
\item $y(t) = \Re(x(t))$ is time invariant.
Let $\hat{x}(t) = x(t-T)$, then $\hat{y}(t) = \Re(\hat{x}(t)) = \Re{x(t-T)} = \frac{x(t-T) + x^*(t-T)}{2} = y(t-T) $

\item $y(t) = \cos ( x(t) )$ is time invariant.
Let $\hat{x}(t) = x(t-T)$, then $\hat{y}(t) = \cos(\hat{x}(t)) = \cos(x(t-T)) = y(t-T)$

\item $y(n) = \sum \limits_{k=0}^{n} x(k)$ is not time invariant.
Let $\hat{x}(n) = x(n-N)$. Then we have:
\begin{align*}
\hat{y}(n) &= \sum \limits_{k=0}^{n} \hat{x}(k)  \quad \mbox{note that the sum uses }k \mbox{, } n \mbox{ is in the limit} \\
\hat{y}(n) &= \sum \limits_{k=0}^{n} x(k-N)\\
\hat{y}(n) &= \sum \limits_{\omega=-N}^{n-N} x(\omega) \quad \mbox{change of variable } (\omega = k-N) \\
\hat{y}(n) &\neq y(n-N)
\end{align*}

\item $y(n) = x(4n+1)$ is not time invariant. This one can be slightly tricky:

Let $\hat{x}(n) = x(n-N)$, then $\hat{y}(n) = \hat{x}(4n+1) = x((4n + 1) - N) \neq x(4(n-N) + 1) = y(n-N)$

\item $y(t) = \int^{2t}_{-\infty}x(\tau)d\tau$ is not time invariant.
Let $\hat{x}(t) = x(t-T)$, then
\begin{align*}
\hat{y}(t) &= \int^{2t}_{-\infty}\hat{x}(\tau)d\tau \\
\hat{y}(t) &= \int^{2t}_{-\infty}x(\tau -T)d\tau \\
\hat{y}(t) &= \int^{2t-T}_{-\infty}x(\lambda)d\lambda \quad \mbox{variable change } (\lambda = \tau - T) \\
\hat{y}(t) &\neq \int^{2t-2T}_{-\infty}x(\lambda)d\lambda = y(t-T)
\end{align*}
\end{enumerate}
\end{solution}



Additional Problems

What will a system do in response to a pure frequency? In other words, when we pass a complex exponential through a system, what does its frequency response tell us about that system?

\begin{problem}
Determine the frequency response when the impulse response is defined $h(n) = \delta(n-N)$, $N \in \Z$, where  the system takes an arbitrary signal $x(n)$:
$$ x(n) \to \fbox{$h(n)$} \to y(n) $$
\end{problem}

\begin{solution}
\begin{align*}
y(n) &= \sum \limits_{\ell \in \Z} = 1 \cdot x(n-N) \\
H(\omega_0) &= \sum \limits_{\ell \in \Z} h(\ell)e^{-i\omega_0\ell} = 1 \cdot e^{-i\omega_0N}
\end{align*}

If $N=0$, $h(n)=\delta(n)$, nothing happens. $\left| H(\omega_0) \right| = 1$, doesn't alter frequency content. The frequency response passes the signal through with the same amplitude and frequency --- it only alters \emph{phase}.

$\angle H(\omega) = -\omega N$
\end{solution}

\begin{problem}
Given a \emph{two-point moving average filter} $y(n) = \frac{x(n) + x(n-1)}{2}$, determine the impulse response $h(n)$ and frequency response $H(\omega)$. Also sketch a graph of the magnitude response.
\end{problem}

\begin{solution}
To find the impulse response, simply let $x(n) = \delta(n)$ to get $h(n) = \frac{1}{2}\delta(n) + \frac{1}{2}\delta(n-1)$.

What about the frequency response? Well, we know that $H(\omega) = \sum \limits_{\ell \in \Z} h(\ell)e^{-i\omega\ell}$ First thing to think about --- how many non-zero terms?

\begin{align*}
H(\omega) &= \sum \limits_{\ell \in \Z} h(\ell)e^{-i\omega\ell} \\
H(\omega) &= \sum \limits_{\ell = 0}^1 h(\ell)e^{-i\omega\ell} \quad \mbox{only looking at } \ell \in \{0,1\}\\
H(\omega) &= h(0)e^{0} + h(1)e^{-i\omega}\\
H(\omega) &= \frac{1}{2} + \frac{1}{2}e^{-i\omega}\\
H(\omega) &= e^{-i\omega/2} \left[ \frac{1}{2}e^{i\omega/2} + \frac{1}{2}e^{-i\omega/2} \right] \quad \mbox{factor out } e^{-i\omega/2} \\
H(\omega) &= e^{-i\omega/2} \frac{\left[ e^{i\omega/2} + e^{-i\omega/2} \right]}{2} \\
H(\omega) &= e^{-i\omega/2} \cos(\omega/2) \\
H(\omega) &= \cos(\omega/2) e^{-i\omega/2}
\end{align*}

Since $\cos(\omega/2)$ is not always positive, we need to take a slight detour. $H(\omega + 2\pi) = H(\omega)$ in \emph{discrete time}.
\begin{proof}
\begin{align*}
H(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} h(\ell)e^{-i(\omega + 2\pi)\ell} \\
H(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} h(\ell)e^{-i\omega} e^{-i 2\pi\ell} \\
H(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} h(\ell)e^{-i\omega} \quad \mbox{since } \ell \in \Z \to e^{-i 2\pi\ell} = 1 \\
H(\omega + 2\pi) &= H(\omega)
\end{align*}
\end{proof}

So we only plot in some contiguous interval of length $2\pi$. So we have $H(\omega) = \cos(\omega/2)e^{-i\omega/2}$ This gives us $\left| H(\omega) \right| = \left| \cos(\omega/2) \right| = \cos(\omega/2) $ for $\left| \omega \right| \leq \pi$.

%\begin{figure}[htp]
%\centering
%\includegraphics{images/magres.ps}
%\caption{ Magnitude response of a low pass filter }
%\label{ fig:magres }
%\end{figure}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\begin{center}
\begin{pspicture}(-3.5,-3.25)(3.5,2)
  \psplot[algebraic,linewidth=1.5pt]{-3.14}{3.14}{cos(x/2)}
  \psaxes[showorigin=false,labels=none, Dx=3.14](0,0)(-3.25,0)(3.25,0)
\rput(3.14, -0.35){$\pi$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}
\rput(1.25,1.25 ){$\left| H(\omega) \right| =\cos(\omega/2)$}

\end{pspicture}
\end{center}

If we look at the graph of the magnitude response $\left| H(\omega) \right|$, we find that it favors lower frequencies. Therefore, we can determine that this system is a \emph{Low Pass Filter}. This is because it zeros out any frequencies near $\pi$ or $-\pi$, and is roughly 1 for values near 0. In general, values near $0$ represent lower frequencies, values near $\pi$ and $-\pi$ represent higher frequencies, and values near $\pi/2$ and $-\pi/2$ represent the fequencies in the range between. The highest frequency discrete-time signal = $(-1)^n = e^{i\pi n}$
\end{solution}

\begin{problem}
Consider the \emph{High Pass Filter} defined by $y(n) = \frac{x(n)-x(n-1)}{2}$. Determine its impulse response $g(n)$ and frequency response $G(\omega)$. Graph its magnitude response $\left| G(\omega) \right|$. Also find the phase response $\angle G(\omega)$
\end{problem}

\begin{solution}
Plugging in $x(n) = \delta(n)$, we get $g(n) = \frac{1}{2}\delta(n) - \frac{1}{2}\delta(n-1)$. Solving for the frequency response we get:
\begin{align*}
G(\omega) &= \sum \limits_{\ell \in \Z} g(\ell)e^{-i\omega\ell} \\
G(\omega) &= \frac{1}{2} - \frac{1}{2}e^{-i\omega} \\
G(\omega) &= e^{-i\omega/2} \left[ \frac{1}{2}e^{i\omega/2} - \frac{1}{2}e^{-i\omega/2} \right] \\
G(\omega) &= e^{-i\omega/2} i\sin(\omega/2) \\
G(\omega) &= e^{-i\omega/2} e^{i\pi/2}\sin(\omega/2) \\
G(\omega) &= \sin(\omega/2)e^{-i(\pi/2 -\omega/2)}
\end{align*}

We can then come up with the phase response, subtracting $\pi$ from $\omega \in (-\pi,0) $ to make sure we have positive values:

$$\angle G(\omega) = \begin{cases} \frac{\pi}{2}-\frac{\omega}{2} & 0 \leq \omega \lt \pi \\ (\frac{\pi}{2}-\frac{\omega}{2})-\pi & -\pi \lt \omega \lt 0 \\ \end{cases}$$


%\begin{figure}[htp]
%\centering
%\includegraphics{images/magres2.ps}
%\caption{ Magnitude response of a high pass filter }
%\label{ fig:magres2 }
%\end{figure}

%\psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\begin{center}
\begin{pspicture}(-3.5,-1.25)(3.5,2)
  \psplot[algebraic,linewidth=1.5pt]{-3.14}{3.14}{abs(sin(x/2))}
  \psaxes[showorigin=false,labels=none, Dx=3.14](0,0)(-3.25,0)(3.25,0)
\rput(3.14, -0.35){$\pi$}
\rput(-3.14, -0.35){$-\pi$}
\rput(0, -0.35){$0$}
\rput(1,1.25 ){$\left| G(\omega) \right| =\left| \sin(\omega/2) \right|$}

\end{pspicture}
\end{center}


\end{solution}

4 Week 4