Week 1

Linear Time-Invariant (LTI) Systems have properties of \emph{linearity} and \emph{time-invariance}. Consider a system with input signal $x \in X$, where $X$ is the set of input signals (input-signal space), and the output signal $y \in Y$, where $Y$ is the set of output signals (output-signal space). 

$$ x \to \fbox{F} \to y  $$

Then we say that $F$ maps from $X$ to $Y$, or $F: X \to Y$.




LTI Systems

There are two properties that make a system linear: \emph{homogeneity} and \emph{additivity}.


{\bf Scaling (homogeneity) property}

Given $\alpha \in \C$, or $\alpha \in \R$, If you scale the input signal by $\alpha$, then the output signal will also be scaled by $\alpha$.

$$\alpha x \to \fbox{F} \to \alpha y$$

{\bf Additivity property}

Given two input signals and their respective outputs after passing them through a system $F$, the signal representing the sum of the input signals corresponds to the output signal representing the sum of the original output signals.

\begin{align*}
x_1 \to &\fbox{F} \to y_1 \\
x_2 \to &\fbox{F} \to y_2 \\
\Rightarrow x_1 + x_2 \to &\fbox{F} \to y_1 + y_2
\end{align*}


\emph{Superposition} combines these two properties and characterizes LTI systems:

$$ \alpha_1 x_1 + \alpha_2 x_2 \to \fbox{F} \to \alpha_1 y_1 + \alpha_2 y_2 $$

\begin{example}
In discrete-time (DT), consider a signal representing a 3-day moving average of a stock quote:

$$ y(n) = \frac{x(n) + x(n-1) + x(n-2)}{3} $$

where $x(n)$ is he closing price of a stock, and $y(n)$ is the 3-day moving average. It can be shown that this signal is linear.
\end{example}

\begin{example}
In continuous-time (CT), consider a circuit where the voltage across the circuit is given by Ohm's Law, $V=IR$, where $I$ is the current, and $R$ is the resistance.

%\begin{center}
%\includegraphics{images/circuits/resistor.ps}
%\end{center}

Let $\hat{x} = \alpha x$., then $\hat{y} = R\hat{x} = \alpha R x = \alpha y$. Let $\tilde{x} = x_1 +  x_2$, then $\tilde{y}=R\tilde{x}=Rx_1+Rx_2=y_1+y_2$. Therefore the system is linear. Since we never used the constancy of $R$, we can observe that in both cases we have linearity.
\end{example}


Linearity

Note we use time when describing signals, but position or other spaces may be used. Hence, this property time-invariance (TI) is generally called \emph{shift invariance}.

$$ x \to \fbox{F} \to y $$

Let us define $\hat{x} = x(t-T)$, where $x$ is closed under shifts, that is, $x, \hat{x} \in X$. Then when we pass this signal through $F$, we get the output signal $\hat{y}$:

$$ \hat{x} \to \fbox{F} \to \hat{y} $$

where $\hat{y} = y(t-T)$. Both previous examples above can be shown to be TI. In the example of the resistor, the reason for time-invariance is the fact that $R$ is constant. For example, to show that the resistor whose voltage is determined by $y(t) = R(t)x(t)$ is not TI, we need to show that $\hat{y}(t) \neq y(t-T)$.

\begin{align*}
y(t) &= R(t)x(t) \\
\hat{y}(t) &= R(t)\hat{x}(t) \\
\hat{y}(t) &= R(t)x(t-T) \neq R(t-T)x(t-T) = y(t-T) \\
\hat{y}(t) &\neq y(t-T)
\end{align*}

Time-Invariance

The properties of LTI systems are important in two aspects:
\begin{enumerate}
\item time-domain behavior
\item frequency-domain behavior
\end{enumerate}

Lets first look at the time domain. Consider a signal $x: \Z \to \R$.

%\img{images/stem/stemex.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1.35)(3.5,2)

\psline{-*}(-3,0)(-3,0)
\rput(-3,-0.4){-3}

\psline{-*}(-2,0)(-2,0)
\rput(-2,-0.4){-2}

\psline{-*}(-1,0)(-1,1)
\rput(-1,1.3){$x(-1)$}
\rput(-1,-0.4){-1}

\psline{-*}(0,0)(0,-1)
\rput(0.45,-1){$x(0)$}
\rput(0.000,0.4){0}

\psline{-*}(1,0)(1,1.5)
\rput(1.4,1.5){$x(1)$}
\rput(1,-0.4){1}


\psline{-*}(2,0)(2,1)
\rput(2.4,1){$x(2)$}
\rput(2,-0.4){2}

\psline{-*}(3,0)(3,0)
\rput(3,-0.4){3}


% axes
\psline{->}(-3,0)(3,0)
\rput(3.3,-0.3){ $n$ }
\rput(3.4,1.5){ $x(n)$ }
    
\end{pspicture}
\end{center}

How do we split the signal into its components? We can write the signal as a sum of scaled and shifted versions of the most fundamental signal, the Kronecker delta. Therefore, we can write the signal as $x(n) = \sum_k x(k)\delta(n-k)$. The \emph{Kronecker Delta} function, also known as \emph{Discrete-Time Impulse Signal} (aka Unit Impulse), is defined by

$$\delta(n) = \begin{cases}
1 & n=0 \\
0 & \mbox{otherwise} \\
\end{cases}
$$

%\img{images/kronecker.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1)(3.5,2)

\psline{-*}(-3,0)(-3,0)
\rput(-3,-0.4){-3}

\psline{-*}(-2,0)(-2,0)
\rput(-2,-0.4){-2}

\psline{-*}(-1,0)(-1,0)
\rput(-1,-0.4){-1}

\psline{-*}(0.000,0)(0.000,1)

\rput(0.25,1){(1)}

\rput(0.000,-0.4){0}

\psline{-*}(1,0)(1,0)
\rput(1,-0.4){1}

\psline{-*}(2,0)(2,0)
\rput(2,-0.4){2}

\psline{-*}(3,0)(3,0)
\rput(3,-0.4){3}

% axes
\psline{->}(-3,0)(3.428,0)
\rput(3.4,-0.3){ $n$ }
\rput(3,1.857){ $\delta(n)$ }
	
\end{pspicture}
\end{center}

In the case of the signal below, we have $x(n) = x(-1)\delta(n+1) + x(0)\delta(n) + x(1)\delta(n-1) + x(2)\delta(n-2)$.

%\img{images/stem/stemex.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1.35)(3.5,2)

\psline{-*}(-3,0)(-3,0)
\rput(-3,-0.4){-3}

\psline{-*}(-2,0)(-2,0)
\rput(-2,-0.4){-2}

\psline{-*}(-1,0)(-1,1)
\rput(-1,1.2){$x(-1)$}
\rput(-1,-0.4){-1}

\psline{-*}(0,0)(0,-1)

\rput(0.4,-1.2){$x(0)$}
\rput(0,0.4){0}

\psline{-*}(1,0)(1,1.5)
\rput(1.4,1.5){$x(1)$}
\rput(1,-0.4){1}

\psline{-*}(2,0)(2,1)
\rput(2.4,1){$x(2)$}

\rput(2,-0.4){2}

\psline{-*}(3,0)(3,0)

\rput(3,-0.4){3}


% axes
\psline{->}(-3,0)(3,0)
\rput(3.4,-0.3){ $n$ }
\rput(3,1.5){ $x(n)$ }
    
\end{pspicture}
\end{center}

%%%

If $\delta(n) \to \fbox{F} \to f(n)$, then $f(n)$ is the \emph{impulse response} of the LTI system $F$. This is important because for any LTI system in discrete-time, if the response to the unit impulse ($\delta(n)$) is known, then the output can be determined.

\begin{align*}
x(n)& = x(-1)\delta(n+1) + x(0)\delta(n) + x(1)\delta(n-1) + x(2)\delta(n-2) \\
y(n)& = x(-1)f(n+1) + x(0)f(n) + x(1)f(n-1) + x(2)f(n-2) 
\end{align*}

More generally, any input signal can be represented as a linear combination of scaled and shifted impulses.
\begin{align*}
x(n) &= \sum \limits_{m\in\Z} x(m)\delta(n-m) \\
y(n) &= \sum \limits_{m\in\Z} x(m)f(n-m) \\
\end{align*}

%%% CONVOLUTION SUM

The output signal $y$ can be written as a sum, also known as the convolution sum:
$$y(n) = \sum \limits_{m\in\Z} x(m)f(n-m) = (x * f)(n)$$.

Convolution has the property of commutativity: Let $m = n-k$:   % k = n-m
$$y(n) = \sum \limits_{k\in\Z} f(m)x(n-k) = (f*x)(n)$$.

Hence, $(x*f)(n) = (f*x)(n)$:

\begin{align*}
x \to & \fbox{f} \to y = x * f \\
f \to & \fbox{x} \to y = f * x
\end{align*}

Any function can be thought of as a signal, and any signal may be thought of as a response---but the input signal and the impulse response must share the same domain.


{\bf Continuous-time}


We also have a continuous-time impulse, the Dirac Delta, which allows us to characterize continuous-time signals. This function can be characterized by integration: $ \int_{-\infty}^{\infty} \delta(\tau)d\tau = 1 $

%\img{images/dirac/dirac.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3,-1)(3,2)

\rput(-3,-0.4){-3}
\rput(-2,-0.4){-2}
\rput(-1,-0.4){-1}

\psline{->}(0,0)(0,1)

\rput(1,1){(1)}

\rput(0,-0.4){0}
\rput(1,-0.4){1}
\rput(2,-0.4){2}
\rput(3,-0.4){3}


\psline{->}(-3.428,0)(3.428,0)

\rput(3.428,-0.3){ $t$ }
	
\end{pspicture}
\end{center}

Hence, the input signal can be written as scaled and shifted versions of the Dirac delta:

$$ x(t) = \infint x(\tau)\delta(t-\tau) $$

Which leads us to the convolution integral. The corresponding convolution formula in continuous-time is given by

$$ y(t) = \infint x(\tau) f(t-\tau) d\tau $$


Time-Domain Behavior

Lets look at the frequency domain behavior of LTI systems. To do this, we pass in a pure frequency by letting $x(n) = e^{i\omega n}$, or $x(t) = e^{i\omega t}$. We know that we can write a signal as a convolution sum, so lets start with this and pass in a pure frequency:

\begin{align*}
y(n) &= \sum \limits_{k\in\Z} f(k) x(n-k) \\
y(n) &= \sum \limits_{k\in\Z} f(k) e^{i\omega(n-k)} \\
y(n) &= \sum \limits_{k\in\Z} f(k) e^{i\omega n}e^{i\omega k} \\
y(n) &= \lr{\sum \limits_{k\in\Z} f(k)e^{i\omega k}} e^{i\omega n} \\
y(n) &= F(\omega) e^{i\omega n} \\
\end{align*}

The same frequency came out of the signal, only scaled by the frequency response of the system.

\begin{nicebox}
$$ F(\omega) = \sum \limits_{k \in \Z} f(k) e^{-i\omega k} $$
\end{nicebox}


The meaning of $F(\omega)$, the frequency response, has to do with frequency content. This tells us how much the system "likes" $\omega$, by suppressing or amplifying it. This motivates the term "filter", since certain frequencies are removed, kept, or amplified. In general, $F(\omega) \in \C$, since it is a linear combination of complex exponentials.

\begin{example}
Given a the impulse response in the graph below,
\begin{enumerate}
\item Express $y(n)$ in terms of $x$
\item Determine expression for $F(\omega)$
\item Plot $\abs{F(\omega)}$
\item Plot $ \angle F(\omega)$
\end{enumerate}

% \img{images/stem/stemex2.ps}

\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-2.25,-1)(3.5,2)
    % line
\psline{-*}(-2.000,0)(-2.000,0)
%  position
\rput(-2.000,-0.4){-2}
% line
\psline{-*}(-1.000,0)(-1.000,0)
%  position
\rput(-1.000,-0.4){-1}
% line
\psline{-*}(0.000,0)(0.000,0.5)
%  value
\rput(0.36,0.5){(0.5)}
%  position
\rput(0.000,-0.4){0}
% line
\psline{-*}(1.000,0)(1.000,0.5)
%  value
\rput(1.36,0.5){(0.5)}
%  position
\rput(1.000,-0.4){1}
% line
\psline{-*}(2.000,0)(2.000,0)
%  position
\rput(2.000,-0.4){2}

% axes
\psline{->}(-2,0)(3,0)
\rput(3,-0.3){ $n$ }
\rput(2.5,0.5){ $f(n)$ }
    
\end{pspicture}
\end{center}

\begin{align*}
f(n) &= \frac{1}{2}\delta(n) + \frac{1}{2}\delta(n-1) \\
y(n) &= \frac{1}{2}x(n) + \frac{1}{2}x(n-1)
\end{align*}

What about the frequency response? Well, we know that $F(\omega) = \sum \limits_{\ell \in \Z} f(\ell)e^{-i\omega\ell}$ Think about how many non-zero terms there are:

\begin{align*}
F(\omega) &= \sum \limits_{\ell \in \Z} f(\ell)e^{-i\omega\ell} \\
F(\omega) &= \sum \limits_{\ell = 0}^1 f(\ell)e^{-i\omega\ell} \quad \mbox{only looking at } \ell \in \{0,1\}\\
F(\omega) &= h(0)e^{0} + h(1)e^{-i\omega}\\
F(\omega) &= \frac{1}{2} + \frac{1}{2}e^{-i\omega}
\end{align*}

Note that we could have used another method to find $F(\omega)$

\begin{align*}
y(n) &= \frac{1}{2}x(n) + \frac{1}{2}x(n-1) \\
y(n) &= \frac{1}{2}e^{i\omega n} + \frac{1}{2}e^{i\omega (n-1)} \quad \mbox{let } x(n) = e^{i\omega n} \\
y(n) &= \lr{\frac{1}{2} + \frac{1}{2}e^{-i\omega}}e^{i\omega n} \\
F(\omega)e^{i\omega n} &= \lr{\frac{1}{2} + \frac{1}{2}e^{-i\omega}}e^{i\omega n} \quad \mbox{since } y(n) = F(\omega)e^{i\omega n} \\
F(\omega) &= \frac{1}{2} + \frac{1}{2}e^{-i\omega}
\end{align*}

We can simplify this expression for $F(\omega)$ further by realizing the symmetry in the coefficients. We can factor out half of the power:

\begin{align*}
F(\omega) &= \frac{1}{2} + \frac{1}{2}e^{-i\omega} \\
F(\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} \\
F(\omega) &= e^{-i\omega/2} \frac{\left[ e^{i\omega/2} + e^{-i\omega/2} \right]}{2} \\
F(\omega) &= e^{-i\omega/2} \cos(\omega/2) \\
F(\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. $F(\omega + 2\pi) = F(\omega)$ in \emph{discrete time}.

\end{example}

\begin{proof}

\begin{align*}
F(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} f(\ell)e^{-i(\omega + 2\pi)\ell} \\
F(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} f(\ell)e^{-i\omega} e^{-i 2\pi\ell} \\
F(\omega + 2\pi) &= \sum \limits_{\ell \in \Z} f(\ell)e^{-i\omega} \quad \mbox{since } \ell \in \Z \to e^{-i 2\pi\ell} = 1 \\
F(\omega + 2\pi) &= F(\omega)
\end{align*}

\end{proof}

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

% \img{images/magres.ps}

% \psset{xunit=1, yunit=1, algebraic, arrowscale=1.5}
\psset{unit=1cm}
\begin{center}
\begin{pspicture}(-3.5,-1.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}

To determine the phase, we can recognize a pattern by looking at the frequency response in terms of its magnitude and phase:

\begin{align*}
F(\omega) &= \abs{F(\omega)}e^{i\angle F(\omega)} 
\end{align*}

if $F(\omega) = \cos(\omega/2) e^{-i\omega/2}$, then by pattern recognition, $\abs{F(\omega)} = \cos(\omega/2)$, and $\angle F(\omega) = -\omega/2$. In this case, we have established that the cosine is positive on $(-\pi,\pi)$, but if it were to have been negative, we would have to shift the phase by $\pm \pi$.



1.1 LTI Systems