1
g(x) = [0.5, 0, −0.4]
.
x2
x3
194
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
The function f :
N
N
R → R
given by
∀
x
x ∈ N
n+1,
if n < N
R ,
f (x)n =
,
x1,
if n = N
is linear. Here f (x)n refers to the n-th element of the vector f (x). The matrix
representation is
0
1
0
··· 0
0
0
1
··· 0
f (x) = ··· ··· ··· ···
x.
1
0
0
··· 0
5.3
The [A, B,C, D] representation of a system
We consider an arbitrary system with
States =
N
M
K
R , Inputs = R , Outputs = R .
Its state-space model is given by the state update and output equations: ∀n ∈ Z+,
s(n + 1)
=
nextState(s(n), x(n)),
y(n)
=
output(s(n), x(n)).
This system is said to be a linear system if the initial state is an N-tuple of zeros, and
the nextState and output functions are linear. If it is also time invariant (the nextState and
output functions do not change with time), then we have a linear time-invariant system,
or LTI system. We can then represent the nextState function by a N × (N + M) matrix
and the output function by a K × (N + M) matrix.
Consider the N × (N + M) matrix representing the nextState function. This matrix has
N + M columns. We denote the N × N matrix comprising the first N columns by A, and
the N × M matrix comprising the last M columns as B, so that
nextState(s(n), x(n)) = As(n) + Bx(n).
We similarly partition the K × (N + M) matrix representing the output function into the
K × N matrix C comprising the first N columns and the K × M matrix D comprising the
Lee & Varaiya, Signals and Systems
195
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
last M columns. Then
output(s(n), x(n)) = Cs(n) + Dx(n).
With this notation, the state-space model is represented as
s(n + 1)
=
As(n) + Bx(n),
(5.16)
y(n)
= Cs(n) + Dx(n).
This is the [A, B,C, D] representation of the LTI system. This compact representation
is very powerful. All the results in this chapter and the next are in terms of these four
matrices. The A matrix is the most important, since it characterizes the system dynamics
as we will see in the sections below.
Example 5.5: Take [A, B,C, D] as
1
1
0
0
A
=
,
,
0
1
1
B = 0
0
0
1
1
C
=
1
0
0
,
D =
1
.
So N = 3, M = 1, K = 1. (This is a 3-dimensional, SISO system.) Using these in
(5.16) gives the state-space model in tuple form,
s1(n + 1) = s1(n) + s2(n),
s2(n + 1) = s2(n) + s3(n),
s3(n + 1) = s3(n) + x(n),
y(n)
=
s1(n) + x(n).
The first three equations together give the nextState function, the fourth equation
gives the output function.
196
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
Observe in (5.16) that if initialState is zero, s(0) = 0, and the input x(n) = 0, for all n ≥ 0,
then the state is unchanged, s(n) = 0. That is why we say that 0 is an equilibrium or rest
state of the [A, B,C, D] system.
Example 5.6: An echo effect can be obtained for audio signals by realizing the
following difference equation,
y(n) = x(n) + αy(n − N),
where the (discrete-time) audio input is x, the output is y, 0 ≤ α < 1 is a real con-
stant, and N ∈ N is an integer constant. Together, α and N determine how long
the echo lasts and what it sounds like. Once again, this is a SISO system, with
M = 1, K = 1. This works simply because the output sample at n is a combination
of the current input x(n) and a scaled old output αy(n − N), called the echo term.
Typically, N needs to be a large number to hear this as an echo. For example, if the
sample rate is 8, 000 samples per second, then if N = 8000, the echo term αy(n−N)
is the previous output one second earlier. This will be heard as a distinct echo.
To construct a state-space model, we need to figure out what will work as the state.
Since the output depends on y(n − N), which is past history, the state will have to
yield y(n − N). The following state definition will work,
y(n − 1)
y(n − 2)
s(n) =
.
···
y(n − N)
It is easy to check that with this state definition, [A, B,C, D] are given by
0
0
··· 0 0
α
1
0
··· 0 0 0
1
0
1
··· 0 0 0
0
A
=
.
.
.
.
. ,
B = . ,
.
.
.
.
.
.
.
.
.
.
.
.
0
0
··· 1 0 0
0
0
0
··· 0 1 0
C
=
0
0
··· 0 α ,
D =
1
,
Lee & Varaiya, Signals and Systems
197
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
5.3.1
Impulse response
The [A, B,C, D] representation provides a complete description of an LTI system. It is a
complete in the sense that given any input sequence, we can calculate the output sequence
using the state and output equations of (5.16) (or (5.19) and (5.20) for the scalar case).
We will discover that there are several other descriptions of LTI systems that are also
complete. The first of these that we will consider is the impulse response. For systems
that are initially at rest, the impulse response gives enough information to calculate the
output sequence given any input sequence. The calculation is performed using what is
known as a convolution sum.
Suppose that M = 1, and the input sequence x is given by x = δ, where
∀
1,
if n = 0
n ∈ Z,
δ(n) =
.
(5.17)
0,
if n = 0
This function δ : Z → R is called an impulse, or a Kronecker delta function (this func-
tion figures prominently in chapters 8 and 9). Remarkably, the response of an LTI system to this particular input is a complete description of the LTI system.
Assuming the system is initially at rest, we can use (5.16) to write the state response to
input δ as
s(0)
=
0
s(1)
=
B
s(2)
=
AB
s(3)
=
A2B
···
s(n)
=
An−1B
···
This is because if x = δ, then x(0) = 1 and x(n) = 0 for all n = 0.
To avoid confusion, we will use the name h instead of y for the output of a system when
the input is the impulse δ. In other words, while y is the output for any input x, h is the
output for the specific input δ. This output is called the impulse response. Using (5.16),
198
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
it can be written as
h(0)
=
D
h(1)
= CB
h(2)
= CAB
h(3)
= CA2B
···
h(n)
= CAn−1B
···
Of course, since the system is initially at rest, h(n) = 0 for all n < 0. We can recognize
the pattern and write the impulse response as
0,
if n < 0
∀ n ∈ Z, h(n) =
D,
if n = 0 .
(5.18)
CAn−1B,
if n ≥ 1
This formula is rarely the right way to compute an impulse response (usually it is easier
to directly determine the output when the input is an impulse), but it does relate the im-
pulse response to the [A, B,C, D] representation. The remarkable fact, developed below,
is that knowing the impulse response is sufficient to calculate the output given any input
(assuming the system is initially at rest).
The impulse response only makes sense if the dimension M of the input is one (otherwise
the input could not be an impulse as defined above). We can gain insight by considering
even more special systems where N = K = 1, as done in the next section.
5.3.2
One-dimensional SISO systems
The simplest LTI system is the one-dimensional, SISO system. Since N = M = K = 1,
the [A, B,C, D] representation is simply [a, b, c, d] where a, b, c, d are scalar constants. The
state-space model (5.16) is ∀n ∈ Z+,
s(n + 1)
=
as(n) + bx(n),
(5.19)
y(n)
=
cs(n) + dx(n).
(5.20)
The initial state s(0) = initialState. For this system, the state at a given time index is a
real number, as are the input and the output.
Lee & Varaiya, Signals and Systems
199
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
Let us consider an example where we construct a state-space model from an input-output
description of a system.
Example 5.7: In Section 2.3.3 we considered a simple moving average example, where the output y is given in terms of the input x by
∀ n ∈ Z+, y(n) = (x(n) + x(n − 1))/2.
(5.21)
This is not a state-space model because it gives the output directly in terms of the
current and past input. To construct a state-space model for it, we first need to
decide what the state is. Usually, there are multiple answers, so we face a choice.
The state is a summary of the past. Examining (5.21), it is evident that we need
to remember the previous input, x(n − 1), in order to produce an output y(n) (of
course, we also need the current input, x(n), but that is not part of the past; that is
the present). So we can define the state to be
∀ n ∈ Z+, s(n) = x(n − 1).
We assume that the system is initially at rest, i.e., s(0) = 0. (If we knew x(−1), we
would take that to be the initial state.) With this choice of state, we need to choose
a, b, c, and d so that (5.19) and (5.20) are equivalent to (5.21). Let us look first at
(5.20), which reads
y(n) = cs(n) + dx(n).
Observing that s(n) = x(n − 1), can you determine c and d? From (5.21), it is
obvious that c = d = 1/2.
Next, we determine a and b in
s(n + 1) = as(n) + bx(n).
Since s(n) = x(n − 1), it follows that s(n + 1) = x(n), and this becomes
x(n) = ax(n − 1) + bx(n),
from which we can see that a = 0 and b = 1.
Note that we could have chosen the state differently. For example,
∀ n ∈ Z+, s(n) = x(n − 1)/2
would work fine. How would that change a, b, c, and d?
200
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
In the preceding example, we started with an input-output description and obtained a
state-space model. The next example shows we can also go the other way.
Example 5.8: Consider a one-dimensional SISO system
s(n + 1)
=
as(n) + bx(n),
y(n)
=
cs(n) + dx(n).
From these equations we get
y(n)
=
c[as(n − 1) + bx(n − 1)] + dx(n),
y(n − 1) = cs(n − 1) + dx(n − 1).
Multiplying the second equation by a and subtracting from the first eliminates the
state to yield a difference equation description of the system,
y(n) − ay(n − 1) = dx(n) + (cb − ad)x(n − 1).
There is a generalization of this example that works for state-space models of any
dimension.
In the following example, we use a state-space model to calculate the output of a system
given an input sequence.
Example 5.9: Suppose the state s(n) is your bank balance at the beginning of day
n, and x(n) is the amount you deposit or withdraw during day n. If x(n) > 0, it
means that you are making a deposit of x(n) dollars, and if x(n) < 0, it means that
you are withdrawing x(n) dollars. The output of the system at time index n is the
bank balance on day n. Thus,
States = Inputs = Outputs = R.
Note that these sets are probably not, strictly speaking, equal to R , since deposits
and withdrawals can only be a whole number of cents. Using R is a considerable
simplification.
Lee & Varaiya, Signals and Systems
201
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
Suppose that the daily interest rate is r. Then your balance at the beginning of day
n + 1 is given by
∀ n ∈ Z, s(n + 1) = (1 + r)s(n) + x(n).
(5.22)
The output of the system is your current balance,
∀ n ∈ Z, y(n) = s(n).
Comparing to (5.19)-(5.20), we have a = 1 + r, b = 1, c = 1, and d = 0. The initial
condition is initialState, your bank balance at the beginning of day 0. Suppose
the daily interest rate is 0.01, or one percent (this would only be reasonable in an
economy with hyperinflation). Suppose that initialState = 100, and you deposit
1, 000 dollars on day 0 and withdraw 30 every subsequent day for the next 30 days.
What is your balance s(31) on day 31? You can compute s(31) recursively from
s(0)
=
100,
s(1)
=
1.01s(0) + 1000,
···
s(n + 1)
=
1.01s(n) − 30, n = 1, · · · , 30,
but this would be tedious. We can develop a formula that is easier to use. We will
do this for a general one-dimensional [a, b, c, d] system.
202
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
Suppose we are given an input sequence x(0), x(1), · · · for an [a, b, c, d] system. As in
example 5.9, if we repeatedly use (5.19) we obtain the first few terms of a sequence, s(0)
=
initialState,
(5.23)
s(1)
=
as(0) + bx(0),
s(2)
=
as(1) + bx(1)
=
a{as(0) + bx(0)} + bx(1)
=
a2s(0) + abx(0) + bx(1),
s(3)
=
as(2) + bx(2)
=
a{a2s(0) + abx(0) + bx(10)} + bx(2)
=
a3s(0) + a2bx(0) + abx(1) + bx(2),
···
From this it is not difficult to guess the general pattern for the state response and the output
response. The state response of (5.19) is given by
n−1
s(n) = aninitialState + ∑ an−1−mbx(m)
(5.24)
m=0
for all n ≥ 0, and the output response of (5.20) is given by
n−1
y(n) = caninitialState +
∑ can−1−mbx(m)
+ dx(n)
(5.25)
m=0
for all n ≥ 0.
We use induction to show that these are correct. Induction is where we show that these are
correct for some fixed n, and then show that if it is correct for any n, then it is correct for
n + 1. For n = 0, (5.24) gives s(0) = a0initialState = initialState, which matches (5.23),
and hence is correct.1 Now suppose that the right-hand side of (5.24) gives the correct value of the response for some n ≥ 0. We must show that it gives the correct value of
the response for n + 1. From (5.19) and using the hypothesis that (5.24) is the correct 1For any real number a, a0 = 1 by definition of exponentiation.
Lee & Varaiya, Signals and Systems
203
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
expression for s(n), we get
s(n + 1)
=
as(n) + bx(n)
n−1
=
a{aninitialState + ∑ an−1−mbx(m)} + bx(n)
m=0
n−1
=
an+1initialState + ∑ an−mbx(m) + bx(n)
m=0
n
=
an+1initialState + ∑ an−mbx(m),
m=0
which is the expression on the right-hand side of (5.24) for n + 1. It follows by induction
that the response is indeed given by (5.24) for all n ≥ 0. The fact that the output response
is given by (5.25) follows immediately from (5.20) and (5.24).
Example 5.10: We use formula (5.24) in example 5.9 to figure out the monthly payment of $w on a $10,000, 32-month loan with a monthly interest of 0.01. So
in (5.24) we substitute n = 32, a = 1.01, b = 1, s(0) = −10, 000, s(32) = 0, and
x(0) = · · · = x(31) = w, to get
31
0 = −1.0132 × 10000 + ∑ 1.0131−mw.
m=0
Using the identity (valid for ρ = 1)
M
1+M − 1
m
ρ
∑ ρ =
,
m=0
ρ − 1
we get
31
1.0132 − 1
∑ 1.0131−mw =
w.
0.01
m=0
So the monthly payment is
w = 0.01 × 10000 × 1.0132 = 366.7.
1.0132 − 1
204
Lee & Varaiya, Signals and Systems
5. LINEAR SYSTEMS
In the next example we identify the unknown parameter a of an [a, b, c, d] representation
given input-output data.
Example 5.11:
Financial analysts compare alternative investment opportunities
using a measure called the internal rate of return. Suppose an investment of
$10,000 at the beginning of year 0 yields an income stream of $2,000 for each of
10 successive years, and nothing thereafter. By definition, the investment’s internal
rate of return is the annual interest rate r that a bank should give so that you can get
the same income stream. So we need to find r such that
s(n + 1) = (1 + r)s(n) + x(n),
with s(0) = 10, 000, s(10) = 0, and x(0) = · · · = x(9) = −2000. We recognize this
as a state update with a = 1 + r and b = 1. Substituting in (5.24) gives
9
0
=
(1 + r)1010000 − ∑ (1 + r)9−m × 2000
m=0
=
(1 + r)1010000 − (1 + r)10 − 1 × 2000,
r
so
1 − (1 + r)−10 = 5r,
which we can solve by trial-and-error to obtain r ≈ 0.15 or 15 percent. Suppose
there is another investment opportunity for the same $10,000 investment that yields
an internal rate of return smaller than 15 percent. Then, all else being equal, one
would choose the first opportunity.
5.3.3
Zero-state and zero-input response
The expressions (5.24) for the state response and (5.25) for the output are each the sum of two terms. The role of these two terms will be better understood if we consider them
in isolation.
If the system is initially at rest, initialState = 0, the first term vanishes, and only the second
term is left. This second term is called the zero-state response. It gives the response of
Lee & Varaiya, Signals and Systems
205
5.3. THE [A, B,C, D] REPRESENTATION OF A SYSTEM
the system to an input sequence when the initial state is zero. For many applications,
particularly when modeling a physical system, the zero-state response is what we are
interested in.
If the input sequence is zero, i.e. 0 = x(0) = x(1) = · · · , the second term vanishes, and
only the first term is left. The first term is called the zero-input response. It gives the
response of the system to some initial condition, with zero input stimulus applied. Of
course, if the system is initially at rest and the input is zero, then the state remains at zero.
So the zero-input response is only interesting if the system is not initially at rest.
So the right-hand side of both equations (5.24) and (5.25) are a sum of a zero-state response and a zero-input response. To make it clear which equation we are talking about,
we use the following terminology:
The state sequence s(n) when the
zero-state state response
initial state is zero.