## Archive for August, 2010

### On discrete-time LTI systems

August 14, 2010

The White Rabbit put on his spectacles. “Where shall I begin, please your Majesty?” he asked. “Begin at the beginning,” the King said gravely, “and go on till you come to the end: then stop.”

Lewis Carroll, Alice’s Adventures in Wonderland

A discrete-time signal is, essentially, a sequence of numbers or symbols. A temperature time series can be viewed as a real-valued discrete-time signal, whereas the output of an A/D converter can be thought of as a symbol-valued discrete-time signal if we view each binary word as a symbol. For simplicity, in this post we will consider sequences of real numbers only. More formally, a discrete-time signal is a function from a set of indices $\mathcal{I} \subseteq \mathbb{Z}$ to $\mathbb{R}$. Again for simplicity, we will only consider the case where $\mathcal{I} = \mathbb{Z}$, i.e., we will focus on doubly-infinite sequences.

A discrete-time system transforms input discrete-time signals into output discrete-time signals. For the time being, we will consider single-input, single-output (SISO) systems only. Let $x : \mathbb{Z} \to \mathbb{R}$ and $y : \mathbb{Z} \to \mathbb{R}$ be the real-valued input and output signals of a discrete-time system. Then, we can think of the system as an operator $\mathcal{H}$ that transforms signal $x$ into signal $y$, as depicted below

The output of the system is thus $y = \mathcal{H}(x)$. We will focus on the class of linear time-invariant (LTI) systems. But, what is a linear system? Or a time-invariant one? Let us “begin at the beginning”.

__________

Linearity

A linear system is one “that possesses the important property of superposition” [1], i.e.,

$\mathcal{H}(a_1 x_1 + \dots + a_n x_n) = a_1 \mathcal{H}(x_1) + \dots + a_n \mathcal{H}(x_n)$

or, equivalently

$\mathcal{H}\left(\displaystyle\sum_{i=1}^n a_i x_i\right) =\displaystyle\sum_{i=1}^n a_i \mathcal{H}(x_i)$.

In words: “if an input consists of the weighted sum of several signals, then the output is the superposition–that is, the weighted sum–of the responses of the system to each of those signals” [1]. Note that if $\mathcal{H}$ is linear, then

$\mathcal{H}(0) = \mathcal{H}(x - x) = \mathcal{H}(x) - \mathcal{H}(x) = 0$,

i.e., “for linear systems, an input which is zero for all time results in an output which is zero for all time” [1]. Pictorially, if $\mathcal{H}$ is linear, then the following block diagram

is equivalent to the one below

This is not a mere academic curiosity. Note that the former block diagram contains $n$ multipliers, one $n$-input adder, and one $\mathcal{H}$ block; by contrast, the latter block diagram contains $n$ multipliers, one $n$-input adder, and $n$ $\mathcal{H}$ blocks. Hence, the former block diagram can be implemented using less hardware, i.e., it is cheaper to implement.

__________

Time-Invariance

A system is time-invariant “if a time-shift in the input signal results in an identical time-shift in the output signal” [1]. Let us introduce the time-shift operator $\mathcal{S}_k$, where $\mathcal{S}_k(x)$ represents:

• signal $x$ delayed by $k$ samples if $k > 0$.
• signal $x$ “anticipated” by $k$ samples if $k < 0$.

Note that $\mathcal{S}_0 (x) = x$, i.e., $\mathcal{S}_0$ is the identity operator. From the definition, if a system is time-invariant, then

$\mathcal{H}(\mathcal{S}_k(x)) = \mathcal{S}_k (y)$

and, since $y = \mathcal{H}(x)$, we obtain

$\mathcal{H}(\mathcal{S}_k(x)) = \mathcal{S}_k (\mathcal{H}(x))$.

For the sake of clarity, let us write $\mathcal{H}(\mathcal{S}_k(x)) = (\mathcal{H} \circ \mathcal{S}_k)(x)$, and $\mathcal{S}_k (\mathcal{H}(x)) = (\mathcal{S}_k \circ \mathcal{H})(x)$. Then, for time-invariant systems, the following equality

$(\mathcal{H} \circ \mathcal{S}_k)(x) = (\mathcal{S}_k \circ \mathcal{H})(x)$

holds for every input signal $x$, i.e., for time-invariant systems the operators $\mathcal{H}$ and $\mathcal{S}_k$ do commute. Pictorially, we have that the following block diagrams

are equivalent. Discrete-time LTI systems are sometimes called linear shift-invariant (LSI) systems [2].

__________

Response of LTI Systems

Let the unit impulse signal $\delta : \mathbb{Z} \to \mathbb{R}$ be defined by

$\delta (n) := \begin{cases} 1, & n=0\\ 0, & n \neq 0\end{cases}$

and let $\delta_k := \mathcal{S}_k (\delta)$ be the unit impulse signal shifted by $k$ samples. An arbitrary discrete-time signal $x : \mathbb{Z} \to \mathbb{R}$ can thus be represented as a linear combination of shifted unit impulses

$x = \displaystyle \sum_{k \in \mathbb{Z}} x(k) \delta_k$

which is known as the sifting property of the discrete-time unit impulse signal [1]. If the input signal is $x$, the output signal will be

$y = \mathcal{H} (x) = \mathcal{H} \left(\displaystyle \sum_{k \in \mathbb{Z}} x(k) \delta_k\right)$.

If the system is linear (we demand no time-invariance at this point), then

$y = \mathcal{H} \left(\displaystyle \sum_{k \in \mathbb{Z}} x(k) \delta_k\right) = \displaystyle \sum_{k \in \mathbb{Z}} x(k) \mathcal{H}(\delta_k)$

i.e., the response of a linear system to a discrete-time signal $x$ is “the superposition of the scaled responses of the system to each of these shifted impulses” [1]. Let $h_k := \mathcal{H}(\delta_k)$ denote the system’s response to the shifted unit impulse signal $\delta_k$. Then we can write the output signal as

$y = \displaystyle \sum_{k \in \mathbb{Z}} x(k) h_k$.

Hence, a linear system is characterized by the set of responses to shifted unit impulses, $\{h_k\}_{k \in \mathbb{Z}}$, an infinite set. Note that

$h_k = \mathcal{H} (\delta_k) = \mathcal{H} (\mathcal{S}_k (\delta_0)) = (\mathcal{H} \circ \mathcal{S}_k) (\delta_0)$

If the system is also time-invariant, then $\mathcal{H}$ and $\mathcal{S}_k$ commute and, thus

$h_k = (\mathcal{H} \circ \mathcal{S}_k) (\delta_0) = (\mathcal{S}_k \circ \mathcal{H})(\delta_0) = \mathcal{S}_k (\mathcal{H}(\delta_0)) = \mathcal{S}_k (h_0)$.

In words: time-invariance means that “the responses of a time-invariant system to the time-shifted unit impulses are simply time-shifted versions of one another” [1]. The system’s output is thus

$y = \displaystyle \sum_{k \in \mathbb{Z}} x(k) h_k = \displaystyle \sum_{k \in \mathbb{Z}} x(k) \mathcal{S}_k (h_0)$

i.e., the system’s output signal is the superposition of scaled, time-shifted versions of the response to the unit impulse signal $\delta = \delta_0$. Let $h := h_0$, which we call the system’s impulse response. Then we have that

$\{h_k\}_{k \in \mathbb{Z}} = \{\mathcal{S}_k (h)\}_{k \in \mathbb{Z}}$.

Hence, from one single discrete-time signal $h$ we can generate the entire set $\{h_k\}_{k \in \mathbb{Z}}$. Therefore, the LTI system can be characterized by one signal, $h = \mathcal{H}(\delta)$, or by one transfer function (which is the Z-transform of the impulse response).

Finally, we have that the output of a discrete-time LTI system is

$y = \displaystyle \sum_{k \in \mathbb{Z}} x(k) \mathcal{S}_k (h)$

where the $n$-th sample of the output signal is, thus, given by the following convolution sum

$y(n) = \displaystyle \sum_{k \in \mathbb{Z}} x(k) h(n-k) =: (x * h)(n)$

where $(\mathcal{S}_k (h))(n) = h(n-k)$.

__________

References

[1] Alan V. Oppenheim, Alan S. Willsky, S. Hamid Nawab, Signals & Systems, 2nd edition, Prentice-Hall, 1996.

[2] Alan V. Oppenheim, Ronald W. Schafer, Digital Signal Processing, Prentice-Hall, 1975.