Chapter 4 Discrete-time systems

In previous chapters, we have explored a little about discrete-time signals and one way to draw a connection between these and continuous-time signals. Largely, our goal was to establish the utility of studying discete-time signals from the perspective of real world applications. In this chapter, we will focus on systems, and specifically, linear time-invariant (LTI) systems, owing to their special properties. Since some of these topics are expected to be covered in prior courses, we will just have a simple revision using a video, followed by a focus on LTI systems.

A system is one that takes one or more signals as an input, and produces one or more signals as an output. Such transformations are part and parcel of DSP, since processing signals to remove noise, enhance it, or draw inferences from it is the basic aim of our DSP study. The number of possible transformations of signals is unlimited. However, for the particular case of LTI systems, the output for all inputs can be succinctly described because we can describe the system using a unique signal, called the impulse response. This is something that is a natural property of LTI systems that we will exploit significantly.

4.1 LTI systems

As you have seen, LTI systems have the distinct property that the complete description of the LTI system can be obtained using just the impulse response. This is very convenient, since the system properties can directly be expressed using a signal, and this allows us to characterize the output for every possible input. In particular, as you have seen in the video above, if you know the output for the input \(\delta[n]\), which is referred to as the impulse response \(h[n]\), then the output for any input can be inferred using superpositions this is the key understanding that we should have about LTI systems.

The other aspect of LTI systems is on how we can practically implement them. In other words, the abstract notion of having an input/output relationship is clear, but how does this translate to an implementation? Let us look at this using some examples. In all of the scenarios below, assume that we get input samples in arrays (typically labeled x), and the ouput samples are also stored in arrays (typically labeled y). Our starting point for this would be the convolution relationship

\[\begin{equation} y[n] = \sum_{k = -\infty}^\infty h[k]x[n - k] = \sum_{k = -\infty}^\infty x[k]h[n - k] \end{equation}\]

We first begin with the two sample average, i.e. \(h[n] = 0.5(x[n] + x[n - 1])\). In this case, the convolution operation yields:

\[\begin{equation} y[n] = (x[n] + x[n - 1]) * 0.5 \end{equation}\]

If we were to come up with a realization of this system, the question is, what operations would allow you to take the array x and give you an array y? Here is one example:

So, we now have a for loop that can actually perform the operation that corresponds to this system (Pythonistas may frown at the above solution and come up with a better solution, but this is a start).

Let us now consider a different system. Let us suppose that this LTI system has impulse response \(h[n] = (0.9)^n u[n]\). Writing the convolution equation, we get:

\[\begin{equation} y[n] = \sum_{k=-\infty}^\infty (0.9)^ku[k]x[n - k] = \sum_{k = 0}^\infty x[n - k] \end{equation}\]

Note that the above is an infinite summation. This makes it difficult to realize, since we cannot implement it in a practical way using loops. However, things can get simplified if we can define a start point for \(x[n]\). For example, let us assume that \(x[n]\) is zero for \(n < 0\). Then, the convolution summation becomes:

\[\begin{equation} y[n] = \sum_{k=0}^n (0.9)^ku[k]x[n - k] \end{equation}\]

However, the above form is still not very convenient for implementing directly. But one can realize that there is a recursive formulation for this that can permit an easier realization. That is:

\[\begin{align} y[0] &= x[0]\\ y[1] &= x[1] + 0.9x[0]\\ y[2] &= x[2] + 0.9x[1] + (0.9)^2 x[0]\\ \vdots &= \vdots \\ y[n] &= x[n] + 0.9x[n - 1] + (0.9)^2x[n - 2] + \cdots + (0.9)^{n-1}x[0]\\ \end{align}\]

If you look carefully, the last equation above points to a recursive implementation. That is, you can express \(y[n]\) as \(x[n] + 0.9y[n - 1]\). This is the so-called recursive realization of IIR filters.

In general, one can express the realization of LTI systems in terms of simple equations that relate the input \(x[n]\) with the output \(y[n]\). These are called linear constant coefficient difference equations (LCCDEs). More generally, it consists of linear combinations of \(x[\cdot]\) and \(y[\cdot]\).

The concept of causality is one that appears frequently. A causal system is one whose output depends only on current and past inputs. This matters for real-time implementations, since the current outputs can only be a function of the inputs that you already have or those that came in the past. However, for contexts that involve offline processing, or something like images, where the concept of time doesn’t make sense, causality is not a necessity. Mathematically, for LTI systems, causality implies that the impulse response satisfies \(h[n] = 0\) for \(n < 0\).

4.2 Stability of LTI systems

In the context of DSP, stability is an important concept that is connected with the design and analysis of systems. In particular, the concept of stability refers to whether the output of a system is guaranteed to be bounded if the input is bounded. Why is this important?

One practical constraint in many DSP implementations is that these are typically implemented using finite precision systems. Therefore, if we are not careful with regard to the design of LTI systems, finite inputs can cause the outputs to become large, and go out of bounds. As an example, if we are focusing on a noise reduction system, if the system actually amplifies inputs and the corresponding outputs cannot be represented without any distortion. One way to prevent this from happening is to ensure that our systems satisfy the bounded-input bounded-output (BIBO) condition. That is, whenever the input \(x[n]\) satisfies \(|x[n]| < M_x\) for a positive real number \(M_x\), then the output \(y[n]\) satisfies \(|y[n]| < M_y\) for a positive real number \(M_y\). One key way to check this for LTI systems is to just evaluate the absolute sum of the impulse response. If this absolute sum is finite, then the system is stable, and vice-versa. How? Let us first verify that if the system is indeed stable, then the absolute sum of \(h[n]\) is finite. For this, choose the input \(x[n]\) as \(\text{sgn}(h[-n])\). That is, \(x[n] = 1\) if \(h[n] > 0\), and \(x[n] = -1\) when \(h[n] < 0\). Then, we have:

\[\begin{align} y[0] &= \sum_{k = -\infty}^\infty x[k]h[k] \\ &= \sum_{k = -\infty}^\infty x[k]\text{sgn}(h[k]) \\ &= \sum_{k = -\infty}^\infty |x[k]| < M_y \end{align}\]

Thus, it is clear that stablity translates to absolute summability for LTI systems. But does the converse hold true? That is, if the impulse response of the LTI system is absolutely summable, then can you conclude that the system is stable?

For this situation, let us assume that the impulse response LTI system \(|h[n]|\) is absolutely summable, but that the system is not stable. Then, there must exist a bounded input \(x[n]\) with \(|x[n]| < M_x\) such that the output \(y[n]\) is unbounded. Therefore, \(\sum_k x[k]h[n - k]\) is unbounded. However, this is not possible, since \(\sum_k |x[k]||h[k]| \leq M\sum_k|h[k]|\), which is finite due to the absolute summability of \(h[k]\). This leads to a contradiction. Thus, absolute summability and stability have an if-and-only-if relationship.

4.3 Complex exponentials are eigenfunctions of LTI systems

Another important property of LTI systems is the fact that, if the input to these systems is the complex exponential, the output is just a scaled version of the same complex exponential. That is, if the input \(e^{j\omega_0 n}\) is given to the system whose impulse response is \(h[n]\), we have

\[\begin{equation} y[n] = \sum_{k = -\infty}^\infty h[k] e^{j\omega_0 (n - k)} = e^{j\omega_0 n}\sum_{k = -\infty}^\infty h[k] e^{-j\omega_0 k}. \end{equation}\]

In other words, the output is just a scaled version of the same complex exponential. This provides a natural concept of the relationship between frequency and LTI systems: LTI systems only scale existing frequency components. They do not add new frequencies. This also provides you a hint on what filters are. For example, in the context of audio equalizers (where you can change the bass, treble etc.), scaling various frequencies up and down is something that can be done using filters. Another example that is common is for correcting channel effects across frequencies in communication systems. This will become more clear as we discuss the discrete-time fourier transform (DTFT) in the next chapter.