Linear Time-Invariant Systems
Table of Contents
1. Linear Time-Invariant Systems
We can model a system as a map of a set of inputs \(\mathcal{X}\) to a set of outputs \(\mathcal{Y}\):
We can view \(H(x)\) as a function \(H: \mathcal{X} \rightarrow \mathcal{Y}\) that maps inputs to outputs. We will often be dealing with discrete-time signals \(x \in \mathcal{X}\).
Linear time-invariant (LTI) systems are systems that satisfy the properties of linearity and time invariance.
1.1. Linearity
Linearity means that if \(H(x) = y\), we satisfy scaling and additivity:
- Scaling: if \(H(x) = y\), then \(H(\alpha x)=\alpha y\).
- Additivity: if \(H(x_1) = y_1\) and \(H(x_2)=y_2\), then \(H(x_1+x_2) = y_1+y_2\).
Using superposition, we can say that if \(H(x_1)=y_1\) and \(H(x_2)=y_2\), then if \(H(\alpha x_1 + x_2) = \alpha y_1 + y_2\) for all inputs \(x_1,x_2 \in \mathcal{X}\) and scalars \(\alpha\), \(H\) is linear.
The zero-input zero-output (ZIZO) property follows from linearity: if \(H\) is linear, then \(H(0) = 0\). Similarly, if \(H(0) \neq 0\), then \(H\) is not linear. This is clear when we consider scaling with $α =0 $: \(H((0)x) = H(0) = (0)y = 0\).
1.2. Time Invariance
Time invariance (also called shift invariance) means that given an input signal \(\hat{x}[n]\) that corresponds to an output signal \(\hat{y}[n]\), shifting the input signal by \(N\) also shifts the output signal by exactly \(N\); that is, \(\hat{x}[n-N]\) corresponds to \(\hat{y}[n-N]\).
Example: Two-Point Moving Average Filter
Consider the system \(y[n] = \frac{x[n] + x[n-1]}{2}\). The input is \(x[n]\) and the output we get is \(y[n]\).
We see that this system satisfies scaling, as the input \(\alpha x[n]\) results in \(\frac{\alpha x[n] + \alpha x[n-1]}{2}=x\frac{x[n]+x[n-1]}{2}=\alpha y[n]\).
Then, given \(y_1[n] = \frac{x_1[n]+x_1[n-1]}{2}\) and \(y_2[n] = \frac{x_2[n] + x_2[n-1]}{2}\), inputting \(x_1[n]+x_2[n]\) gives \(y_1[n]+y_2[n]\) which also satisfies additivity.
Finally, we see that shifting \(x[n]\) to \(x[n-N]\) results in \(\frac{x[n-N]+x[n-N-1]}{2}=y[n-N]\), which means it is time-invariant. Thus, the two-point moving average filter is an LTI system.
Example: Modulator
Consider the following system:
It can be shown that the above system is linear. However, if we use the shifted signal \(x(t-T)\), we get \(x(t-T)\cos(\omega_0 t) \neq y(t-T)\). Thus, this system is not time-invariant.
This system is an example of a modulator, which is used by AM (amplitude modulation) radios to convert a sound input \(x(t)\) to a higher frequency by way of a carrier signal. This process is linear but time-varying.
1.3. Causality
We say a system \(H: \mathcal{X} \to \mathcal{Y}\) is causal if for every pair of \(x_1,x_2 \in \mathcal{X}\) and \(\forall N \in \mathbb{Z}\) such that \(x_1[n]=x_2[n] \; \forall n \leq N\) then \(y_1[n]=y_2[n] \; \forall n \leq N\). In other words, if two different input signals have the same value in a range \(n \leq N\), then the resulting outut signals will also have the same value in that range; the system does not peek ahead in time. To produce \(y[n]\), the system uses \(x[m]\) for \(m \leq n\) only.
Thus, a DT LTI system is causal if and only if the terms in the future are zero:
\begin{align} y[n] &= \sum_{k=-\infty}^{\infty} h[k] x[n-k] \notag \\ &= \cdots + 0x[2] + 0x[n+1] + h[0]x[n] + h[1]x[n-1] + \cdots \notag \end{align}Therefore, a DT LTI system is causal if and only if \(h[n]=0\) for \(n < 0\).
2. Convolutions
A DT-LTI (discrete-time linear time-invariant) system is characterized completely by its response to the DT impulse (Kronecker Delta). In other words, given a DT-LTI system \(H\), the impulse response \(h[n]\) of \(H\) when given the input \(\delta[n]\) describes \(H\) completely.
This is because any DT signal can be expressed as a linear combo of scaled and shifted impulses:
\begin{align} x[n] = \sum_{k=-\infty}^{\infty} x[k] \delta[n-k] \notag \end{align}Then, by linearity and time-invariance, we can use the impulse response to reproduce the response of any DT input signal:
\begin{align} y[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] \notag \end{align}This operation is called the convolution of \(x\) and \(h\), and can be written as:
\begin{align} x*h = \sum_{k=-\infty}^{\infty} x[k]h[n-k] \end{align}If we do the change of variables \(l=n-k\), then we see that \(\sum_{k=-\infty}^{\infty} x[k]h[n-k] = \sum_{l=-\infty}^{\infty} h[l]x[n-l] = h*x\), so convolution is commutative:
\begin{align} x*h=h*x \end{align}Additionally, convolution distributes over addition, so the convolution of a function with a linear combination is the same as the linear combination of the individual convolutions.
2.1. Echo Model
Intuitively, we can view a signal as a train of pulses happening one after each other. Imagine that each pulse in time creates an instantaneous “echo” that rings and fades away. Then, each point on the convolved signal is the sum of all previous rings that haven’t faded out yet. When we convolve \(x*h\), \(h\) is the impulse response, which tells us the weights of all the past echoes:
\begin{align} y[n] = \sum_{k=-\infty}^{\infty} x[k]h[n-k] = \cdots + x[-1]h[n+1] + x[0]h[n] + x[1]h[n-1] + \cdots \end{align}\(k\) represents the specific time a pulse occurred, and \(x[k]\) represents the force of that pulse. \(n\) represents “now,” and the \(n-k\) represents the elapsed time since that pulse. The multiplication of the terms \(x[k]h[n-k]\) is how strong an echo is currently, and the sum of all the echoes gives the convolution.
2.2. Flip and Shift
To calculate a convolution, we can view the convolution as a flip and shift operation. Given the convolution of two signals \(x\) and \(h\):
\begin{align} x*h = \sum_{k=-\infty}^{\infty} x[k]h[n-k] \notag \end{align}The \(h[n-k]\) term means that we first flip the signal along the horizontal axis, and then shift it to the right by \(n\) steps. Each point in the convolved signal is essentially a linear combination of the current and past inputs of \(x\), whose weights are determined by \(h\). We flip \(h\) because time runs backwards into the past, and shifting it aligns the starts. Then, we multiply the two signals and add them up to get the magnitude of the convolved signal at a particular point \(n\).
2.3. Convolution with an Impulse
The Kronecker delta is the identity element for convolution:
\begin{align} \delta * h &= \sum_{k=-\infty}^{\infty} \delta[k]h[n-k] \notag \\ &= \delta[0]h[n-0] \notag \\ &= h[n] \notag \end{align}Additionally, convolution with a shifted impulse shifts the signal by the amount of the shift of the impulse.
Therefore, if we can represent \(x\) in \(x*h\) as a linear combination of Kronecker deltas, we can distribute the convolution operation among them. For example, if \(x[n] = \delta[n] + \delta[n-2]\), then \((x*h)[n] = (\delta[n] + \delta[n-2])*h[n] = h[n] + h[n-2]\).
2.4. Interconnections of DT-LTI Systems
Say we have two DT-LTI systems represented by the functions \(f[n]\) and \(g[n]\) respectively, and an interconnected DT-LTI system composed of \(f[n]\) and \(g[n]\) represented by the function \(h[n]\). If the interconnection is in series, then the total system is just the convolution of the two subsystems, i.e. \(h[n] = (f*g)[n]\). If the interconnection is in parallel, then the total system is the sum of the two subsystems, i.e. \(h[n] = f[n] + g[n]\).
3. Frequency Response
If we send as input into a DT-LTI system \(h[n]\) the complex exponential \(e^{i\omega n}\), then the output is:
\begin{align} y[n] &= (h*x)[n] \notag \\ &= \sum_{k=-\infty}^{\infty} h[k]e^{-i\omega k}e^{i\omega n} \notag \\ &= \left(\sum_{k=-\infty}^{\infty}h[k]e^{-i\omega k}\right)e^{i\omega n} \notag \end{align}The term in the parantheses is \(H(\omega)\), the frequency response of the system:
\begin{align} y[n] = H(\omega)e^{i\omega n} \end{align}Notice that sending in the signal \(e^{i\omega n}\) returns the same signal, but scaled by \(H(\omega)\). This is called the eigenfunction property of DT-LTI systems with respect to complex exponentials. The impulse signal also satisfies tihs property; these eigenfunction signals can be used to break down input signals.
DTFS tells us that we can decompose any DT p-periodic signal into:
\begin{align} x[n] = \sum_{k\in\langle p \rangle} X_ke^{ik\omega_0 n} \notag \end{align}Then, if we feed this function into a DT-LTI system with frequency response \(H(\omega)\), we get:
\begin{align} y[n] = \sum_{k\in\langle p \rangle}X_kH(k\omega_0)e^{ik\omega_0 n} \notag \end{align}Thus, the response of a DT-LTI system to a p-periodic input is also p-periodic with DTFS coefficients \(Y_k=X_kH(k\omega_0)\).
3.1. Region of Support
The support of a DT signal \(x: \mathbb{Z} \rightarrow \mathbb{R}\) is defined as:
\begin{align} \text{supp}(x) = \{n \in \mathbb{Z} | x[n] \neq 0 \} \end{align}If \(|\text{supp}(x)|<\infty\), then the function has a fin.ite support DT signals that have finite support are called finite impulse response (FIR) signals. On the other hand, a signal that has infinite support are called infinite impulse response (IIR) signals.
4. Bounded-Input Bounded-Output Stability
A DT signal \(x: \mathbb{Z} \to \mathbb{R}\) is bounded if there exists \(B_x \in \mathbb{R}\) such that:
\begin{align} |x[n]| \leq B_x \quad \forall n \in \mathbb{Z} \end{align}In other words, a DT signal is bounded if there exists some \(B_x \in \mathbb{R}\) such that the output magnitude of the signal never exceeds \(B_x\).
A system is bounded-input bounded-output stable (BIBO stable) if every bounded input produces a bounded output. A DT LTI system is BIBO stable if and only if:
\begin{align} \sum_{n=-\infty}^{\infty} |h[n]| < \infty \end{align}To prove sufficiency, let \(x\) be a bounded input signal with bound \(B_x\). Then, the magnitude of the output of the system is:
\begin{align} |y[n]| = \left| \sum_{n=-\infty}^{\infty} h[k]x[n-k] \right| \notag \end{align}Using the triangle inequality, we can bound this like so:
\begin{align} |y[n]| &\leq \sum_{n=-\infty}^{\infty}|h[k]x[n-k]| \notag \\ &= \sum_{n=-\infty}^{\infty} |h[k]||x[n-k]| \notag \\ &\leq B_x \sum_{n=-\infty}^{\infty}|h[k]| \notag \end{align}Since \(\sum_{n=-\infty}^{\infty}|h[k]| < \infty\), the output is also bounded.
To prove necessity, we use contraposition to prove that if \(h\) is not absolutely summable, then there exists some bounded input signal such that \(H\) is not BIBO stable.
Using this theorem, we can see that every FIR DT LTI filter is BIBO stable.
5. Dirac Delta
5.1. Motivation
Say we have a ball that is falling towards a surface, makes impact at time \(-\frac{\epsilon}{2}\), and bounces back up at time \(\frac{\epsilon}{2}\). We can plot a graph of the instantaneous force imparted on the ball during this interval, as well as the average force imparted over this time:
Notably, the area under the curve of \(f(t)\) must be the same as the area under \(F_{\text{avg}}\).
The Dirac delta “function” is created by keeping this area constant as we reduce the interval \([-\frac{\epsilon}{2},\frac{\epsilon}{2}]\) to zero, and we get an impulse with magnitude infinity.
5.2. Definition
The Dirac delta is a distribution whose value is zero everywhere except at zero, where it is infinite, and whose integral over the entire real line is equal to one. Thus, it can be represented as:
\begin{align} \delta(x) = \begin{cases} 0 &x \neq 0 \\ \infty &x = 0 \end{cases} \end{align}such that
\begin{align} \int_{-\infty}^{\infty} \delta(x) \text{ d}x = 1 \end{align}The Dirac delta can be visualized like so:
An important property of the Dirac delta is that integrating a function \(\phi(t)\) multipled by the Dirac delta over an interval that includes where the Dirac delta is nonzero returns the value of \(\phi(0)\):
\begin{align} \int_a^b \phi(t)\delta(t)\text{ d}t = \phi(0) \end{align}if \(0 \in [a,b]\).
5.3. CT-LTI Systems
Just like for discrete time LTI systems, if we know the response to \(\delta(t)\), we know the response to any arbitrary input. Call the impulse response of the system \(h(t)\). Then,
\begin{align} y(t) = \int_{-\infty}^{\infty}x(\tau)\delta(t-\tau)\text{ d}\tau \end{align}This is just the continuous time convolution \((x * h)(t)\).