Digital linear time-invariant systems

Digital Imaging and Deconvolution: The ABCs of Seismic Exploration and Processing

Series	Geophysical References Series
Title	Digital Imaging and Deconvolution: The ABCs of Seismic Exploration and Processing
Author	Enders A. Robinson and Sven Treitel
Chapter	15
DOI	http://dx.doi.org/10.1190/1.9781560801610
ISBN	9781560801481
Store	SEG Online Store

A discrete-time signal $x_{k}$ is a signal of (real or complex) numbers defined for every integer k. The index k represents the set of discrete, equally spaced time points. A discrete time signal often is called a digital signal. It is customary to denote time spacing between the discrete time points as $\Delta t$. Actual time t is related to the index k by the equation $t=k\Delta t$. Usually, time is measured in seconds.

An important type of digital signal is the impulse function. The discrete impulse function ${\delta }_{k}$ is defined as the signal made up entirely of zeros except for a value of one at time index $k=0$. That is, ${\delta }_{k}$ is given by

${\begin{aligned}{\delta }_{k}=1\mathrm {\;\;\;\;for\;\;\;\;} k=0\\{\delta }_{k}=0\mathrm {\;\;\;\;for\;\;\;\;} k\neq 0.\end{aligned}}$

(1)

The impulse function ${\delta }_{k}$ is also called the Kronecker delta function. A more popular name for the delta function is the unit spike.

A digital system is a discrete time system that can be represented by a rule that transforms a signal $u_{k}$ into another signal $y_{k}$. The signal $u_{k}$ is called the input, and the signal $y_{k}$ is the output. This relationship is indicated by the notation

${\begin{aligned}y_{k}=S\left(u_{k}\right),\end{aligned}}$

(2)

where S denotes the digital system. A system L is linear if

${\begin{aligned}L\left(au_{k}+bv_{k}\right)=aL\left(u_{k}\right)+bL\left(v_{k}\right).\end{aligned}}$

(3)

for any constants a and b and for any digital signals $u_{k}$ and $v_{k}$. In particular, if $y_{k}$ is the output of a linear system for input $u_{k}$, then $ay_{k}$ is the output for input $au_{k}$. That is, if we amplify the input of a linear system by a constant factor, the output also is amplified by this same constant factor. In addition, if $y_{k}$ and $z_{k}$ are the respective outputs of a linear system for the inputs $u_{k}$ and $v_{k}$, then $y_{k}+z_{k}$ is the output for input $u_{k}+v_{k}$. That is, if we add the inputs of a linear system, the outputs also are added.

A digital system $y_{k}=S\left(u_{k}\right)$ is said to be time invariant if $y_{k-n}=S\left(u_{k-n}\right)$ for any integer n. That is, a system is time invariant if a shift in the input produces the same shift in the output.

Let us give some examples. We begin with the delay line $y_{k}=u_{k-n}$, where n is a constant. The delay line $y_{k}=u_{k-n}$ is linear and time invariant. The rectifier $y_{k}=|u_{k}|$ is nonlinear and time invariant. The amplifier $y_{k}=k^{2}u_{k}$ is linear and time varying. It is time varying because (1) a shift in the input $u_{k}$ produces the output $L\left(u_{k-n}\right)=k^{2}u_{k-n;}\left(2\right)$ a shift in the output $y_{k}=k^{2}u_{k}$ produces $y_{k-n}={\left(k-n\right)}^{2}u_{k-n}$; and (3) the two outputs are not the same.

A signal $u_{k}$ is one-sided, or causal, if $u_{k}=0$ for $k<0$. A signal $u_{k}$ is anticausal if $u_{k}=0$ for $k\geq 0$. Finally, a signal $u_{k}$ is noncausal if it has an anticausal component.

A system is said to be causal if a causal input yields a causal output. That is, a causal system is a system with this property: If $u_{k}=0$ for $k<0$, then $y_{k}=0$ for $k<0$. If the system represents a physical phenomenon operating in real time, then the system must be causal. However, if the system represents an analysis of past recordings (such as a seismic record) so that k represents nominal time (i.e., time marks on the record), then the system need not be causal.

A linear time-invariant system is characterized by its impulse response. The impulse response $h_{k}$ is defined as the output resulting from a spike input ${\delta }_{k}$; that is,

${\begin{aligned}h_{k}=L\left({\delta }_{k}\right).\end{aligned}}$

(4)

Because the impulse ${\delta }_{k}$ is causal, we see that a causal system has a causal impulse response, whereas a noncausal system has a noncausal impulse response. Let us now express, in terms of $h_{k}$, the output $y_{k}$ of a linear time-invariant system that has an arbitrary input $u_{k}$. Because of time invariance, the output resulting from the input ${\delta }_{k-n}$ is $h_{k-n}$ for any n; that is,

${\begin{aligned}L\left({\delta }_{k-n}\right)=h_{k-n}.\end{aligned}}$

(5)

Because of linearity, the output resulting from the input $u_{n}{\delta }_{k-n}$ is $u_{n}h_{k-n}$. The input $u_{k}$ can be written as

${\begin{aligned}u_{k}=\sum _{n=-\infty }^{\infty }{u_{n}}{\delta }_{k-n}.\end{aligned}}$

(6)

The output resulting from this input is

${\begin{aligned}y_{k}=L\left(u_{k}\right)=L\left(\sum _{n=-\infty }^{\infty }{u_{n}}{\delta }_{k-n}\right)=\sum _{n=-\propto }^{\infty }{u_{n}}L\left({\delta }_{k-n}\right),\end{aligned}}$

(7)

which is

${\begin{aligned}y_{k}=\sum _{n=-\infty }^{\infty }{u_{n}}h_{k-n}.\end{aligned}}$

(8)

The expression on the right is a convolution. It represents the convolution of $u_{k}$ with $h_{k}$ and is denoted by $u_{k}*h_{k}$. Convolution is commutative, so we can write the input-output relationship as

${\begin{aligned}y_{k}=u_{k}*h_{k}=\sum _{n=-\infty }^{\infty }{u_{n}}h_{k-n}=\sum _{n=-\infty }^{\infty }{h_{n}}u_{k-n}.\end{aligned}}$

(9)

The most important class of linear time-invariant digital systems is the class represented by a finite-difference equation (with constant coefficients) of the form

${\begin{aligned}y_{k}+{\alpha }_{1}y_{k-1}+\ldots +{\alpha }_{p}y_{k-p}={\beta }_{0}u_{k}+{\beta }_{1}u_{k-1}+\ldots +{\beta }_{q}y_{k-q}.\end{aligned}}$

(10)

This difference equation represents an ARMA(p,q) system. In the case of q = 0 and $\beta _{0}=1$, it reduces to the AR(p) system

${\begin{aligned}y_{k}+{\alpha }_{1}y_{k-1}+\ldots +{\alpha }_{p}y_{k-p}=u_{k}.\end{aligned}}$

(11)

On the other hand, if p = 0, the ARMA(p,q) system reduces to the MA(q) system

${\begin{aligned}y_{k}={\beta }_{0}u_{k}+{\beta }_{1}u_{k-1}+\ldots +{\beta }_{q}u_{k-q}.\end{aligned}}$

(12)

Most of our work will deal with the three difference equations 10, 11, and 12. Let us now make some remarks about these three equations. In the form in which they are written above, we want index k to represent the present instant of time, so $u_{k}$ would be the present input and $y_{k}$ the present output. As a result, the other input values $u_{k-1}$, $u_{k-2},\ldots ,u_{k-q}$ represent past values, and the other output values $y_{k-1},\;y_{k-2},\;\ldots ,y_{k-p}$ represent past values. Thus, the above difference equations, so interpreted, involve only present and past values of the input and output and no future values. Under this interpretation, the systems represented by equations 10, 11, and 12 are causal — that is, they can be implemented in real time. Conceptually, the MA system is the easiest one to visualize.

We now want to introduce the backward-shift (or unit-delay) operator Z, which is defined as $Zx_{k}=x_{k-1}$ for any signal $x_{k}$. In terms of the backward-shift operator, the MA(q) equation is

${\begin{aligned}y_{k}={\beta }_{0}u_{k}+{\beta }_{1}Zu_{k}+{\beta }_{2}Z^{2}u_{k}+\ldots +{\beta }_{q}Z^{q}u_{k}\end{aligned}}$

(13)

or

${\begin{aligned}y_{k=}\left({\beta }_{0}+{\beta }_{1}Z+{\beta }_{2}Z^{2}+\ldots +{\beta }_{q}Z^{q}\right)u_{k}.\end{aligned}}$

(14)

A diagram for this system is shown in Figure 1. In such diagrams, a branch point is indicated by a solid circle. At a branch point, the signal that goes out on each branch is the same as the signal that enters the branch point. A small open circle represents a summation point.

Figure 1.  Digital MA(q) (moving-average) system.

At a summation point, all the incoming signals are added to produce the outgoing signal.

In Figure 1, the forward direction (i.e., the direction from input to output) is from left to right. Because all of the arrows associated with the constant multipliers ${\beta }_{0},{\beta }_{1}$, ${\beta }_{2}...,\beta _{q}$ are in the forward direction, an MA system is seen to be a feedforward system. In a feedforward system, the present output $y_{k}$ depends on the present and past values $u_{k}$, $u_{k-1}$, $u_{k-2}$, ... of the input. In the case of an MA system, only a finite number q of past values are involved.

Next, let us construct a diagram for an AR(p) system, which we can write as

${\begin{array}{l}(1+\alpha _{1}Z+\alpha _{2}Z^{2}+...\\\;\;\;\;+\alpha _{p}Z^{p})y_{k}=u_{k}.\\\end{array}}$

(15)

Figure 2.  Digital AR(p) (autoregressive) system.

A diagram for this system is shown in Figure 2. Because all the arrows associated with the multipliers ${\alpha }_{1}$, ${\alpha }_{2},...,p$ are in the backward direction, an AR system is seen to be a (pure) feedback system. In a feedback system, the present input $u_{k}$ can be expressed in terms of the present and past values $y_{k}$, $y_{k-1}$, $y_{k-2}$, ... of the output. In the case of an AR system, only a finite number pof past values are involved.

Finally, let us construct a diagram of the ARMA(p, q) system

${\begin{aligned}\left(1+{\alpha }_{1}Z+{\alpha }_{2}Z^{2}+\dots +{\alpha }_{p}Z^{p}\right)y_{k}=\left({\beta }_{0}+{\beta }_{1}Z+{\beta }_{2}Z^{2}+\dots +{\beta }_{q}Z^{q}\right)u_{k}.\end{aligned}}$

(16)

An ARMA(p, q) system can be regarded as the combination in series of an AR(p) system and an MA(q) system. A diagram for an ARMA system is shown in Figure 3.

Figure 3.  Representation of a digital ARMA(p, q) system involving the smallest possible number of delay elements Z. Here, m is the larger of p and q, and some of the coefficients might be zero.

Continue reading

Previous section	Next section
Introduction	Analog linear time-invariant systems
Previous chapter	Next chapter
Absorption	none
Table of Contents (book)

Also in this chapter

• Introduction
• Analog linear time-invariant systems
• Digital transfer functions
• Analog transfer functions
• Causality and stability of digital systems
• Causality and stability of analog systems
• Frequency response of a digital system
• Digital prediction
• Digital prediction error
• Analog prediction error

External links

find literature about Digital linear time-invariant systems