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.

Tags:, ,
Posted in LTI Systems | Leave a Comment »

Follow

Get every new post delivered to your Inbox.

Join 77 other followers