One of the most important concepts of DSP is to be able to
properly represent the input/output relationship to a given LTI
system. A linear constant-coefficient difference
equation (LCCDE) serves as a way to express just this
relationship in a discrete-time system. Writing the sequence
of inputs and outputs, which represent the characteristics of
the LTI system, as a difference equation help in understanding
and manipulating a system.
- Definition 1: difference equation
An equation that shows the relationship between
consecutive values of a sequence and the differences among
them. They are often rearranged as a recursive formula so
that a systems output can be computed from the input
signal and past outputs.
yn+7yn−1+2yn−2=xn−4xn−1
y
n
7
y
n
1
2
y
n
2
x
n
4
x
n
1
(1)
As stated briefly in the definition above, a difference
equation is a very useful tool in describing and calculating
the output of the system described by the formula for a given
sample nn. The key property of
the difference equation is its ability to help easily find the
transform,
Hz
H
z
,
of a system. In the following two subsections, we will look at
the general form of the difference equation and the general
conversion to a z-transform directly from the difference
equation.
The general form of a linear, constant-coefficient
difference equation (LCCDE), is shown below:
∑k=0N
a
k
yn−k=∑k=0M
b
k
xn−k
k
0
N
a
k
y
n
k
k
0
M
b
k
x
n
k
(2)
We can also write the general form to easily express a
recursive output, which looks like this:
yn=-∑k=1N
a
k
yn−k+∑k=0M
b
k
xn−k
y
n
k
1
N
a
k
y
n
k
k
0
M
b
k
x
n
k
(3)
From this equation, note that
yn−k
y
n
k
represents the outputs and
xn−k
x
n
k
represents the inputs. The value of
NN represents the
order of the difference equation and
corresponds to the memory of the system being represented.
Because this equation relies on past values of the output,
in order to compute a numerical solution, certain past outputs,
referred to as the
initial conditions, must be known.
Using the above formula,
Equation 2, we can
easily generalize the transfer function,
Hz
H
z
, for any difference equation. Below are the steps
taken to convert any difference equation into its transfer
function, i.e. z-transform. The first
step involves taking the Fourier Transform of all the terms in
Equation 2. Then we use
the linearity property to pull the transform inside the
summation and the time-shifting property of the z-transform
to change the time-shifting terms to exponentials. Once
this is done, we arrive at the following equation:
a
0
=1
a
0
1
.
Yz=-∑k=1N
a
k
Yzz-k+∑k=0M
b
k
Xzz-k
Y
z
k
1
N
a
k
Y
z
z
k
k
0
M
b
k
X
z
z
k
(4)
Hz=YzXz=∑k=0M
b
k
z-k1+∑k=1N
a
k
z-k
H
z
Y
z
X
z
k
0
M
b
k
z
k
1
k
1
N
a
k
z
k
(5)
Once the z-transform has been calculated from the difference
equation, we can go one step further to define the frequency
response of the system, or filter, that is being
represented by the difference equation.
Remember that the reason we are dealing with these
formulas is to be able to aid us in filter design. A LCCDE
is one of the easiest ways to represent FIR filters. By
being able to find the frequency response, we will be able to
look at the basic properties of any filter represented by a
simple LCCDE.
Below is the general formula for the frequency response of a
z-transform. The conversion is simple a matter of taking
the z-transform formula,
Hz
H
z
,
and replacing every instance of
zz
with
ⅇⅈw
w
.
Hw=Hz|z,z=ⅇⅈw=∑k=0M
b
k
ⅇ-ⅈwk∑k=0N
a
k
ⅇ-ⅈwk
H
w
z
w
Hz
k
0
M
b
k
w
k
k
0
N
a
k
w
k
(6)
Once you understand the derivation of this formula, look at
the module concerning
Filter Design
from the Z-Transform for a look into how all of these
ideas of the
Z-transform, Difference Equation, and
Pole/Zero Plots
play a role in filter design.
Below is a basic example showing the opposite of the steps
above: given a transfer function one can easily calculate the
systems difference equation.
Hz=z+12z−12z+34
H
z
z
1
2
z
1
2
z
3
4
(7)
Given this transfer function of a time-domain filter, we want
to find the difference equation. To begin with, expand both
polynomials and divide them by the highest order
zz.
Hz=z+1z+1z−12z+34=z2+2z+1z2+2z+1−38=1+2z-1+z-21+14z-1−38z-2
H
z
z
1
z
1
z
1
2
z
3
4
z
2
2
z
1
z
2
2
z
1
3
8
1
2
z
-1
z
-2
1
1
4
z
-1
3
8
z
-2
(8)
From this transfer function, the coefficients of the two
polynomials will be our
a
k
a
k
and
b
k
b
k
values found in the general difference equation
formula,
Equation 2.
Using these coefficients and the above form of the transfer
function, we can easily write the difference equation:
xn+2xn−1+xn−2=yn+14yn−1−38yn−2
x
n
2
x
n
1
x
n
2
y
n
1
4
y
n
1
3
8
y
n
2
(9)
In our final step, we can rewrite the difference equation in
its more common form showing the recursive nature of the system.
yn=xn+2xn−1+xn−2+-14yn−1+38yn−2
y
n
x
n
2
x
n
1
x
n
2
-1
4
y
n
1
3
8
y
n
2
(10)
In order for a linear constant-coefficient difference equation
to be useful in analyzing a LTI system, we must be able to
find the systems output based upon a known input,
xn
x
n
, and a set of initial conditions. Two common
methods exist for solving a LCCDE: the direct
method and the indirect method, the later
being based on the z-transform. Below we will briefly discuss
the formulas for solving a LCCDE using each of these methods.
The final solution to the output based on the direct method
is the sum of two parts, expressed in the following
equation:
yn=
y
h
n+
y
p
n
y
n
y
h
n
y
p
n
(11)
The first part,
y
h
n
y
h
n
, is referred to as the
homogeneous
solution and the second part,
y
h
n
y
h
n
, is referred to as
particular
solution. The following method is very similar to
that used to solve many differential equations, so if you
have taken a differential calculus course or used
differential equations before then this should seem very
familiar.
We begin by assuming that the input is zero,
xn=0
x
n
0
.
Now we simply need to solve the homogeneous difference
equation:
∑k=0N
a
k
yn−k=0
k
0
N
a
k
y
n
k
0
(12)
In order to solve this, we will make the assumption that
the solution is in the form of an exponential. We will
use lambda,
λλ, to
represent our exponential terms. We now have to solve the
following equation:
∑k=0N
a
k
λn−k=0
k
0
N
a
k
λ
n
k
0
(13)
We can expand this equation out and factor out all of the
lambda terms. This will give us a large polynomial in
parenthesis, which is referred to as the
characteristic polynomial. The roots of this
polynomial will be the key to solving the homogeneous
equation. If there are all distinct roots, then the
general solution to the equation will be as follows:
y
h
n=
C
1
λ
1
n+
C
2
λ
2
n+…+
C
N
λ
N
n
y
h
n
C
1
λ
1
n
C
2
λ
2
n
…
C
N
λ
N
n
(14)
However, if the characteristic equation contains multiple
roots then the above general solution will be slightly
different. Below we have the modified version for an
equation where
λ
1
λ
1
has
KK multiple
roots:
y
h
n=
C
1
λ
1
n+
C
1
n
λ
1
n+
C
1
n2
λ
1
n+…+
C
1
nK−1
λ
1
n+
C
2
λ
2
n+…+
C
N
λ
N
n
y
h
n
C
1
λ
1
n
C
1
n
λ
1
n
C
1
n
2
λ
1
n
…
C
1
n
K
1
λ
1
n
C
2
λ
2
n
…
C
N
λ
N
n
(15)
The particular solution,
y
p
n
y
p
n
, will be any solution that will solve the
general difference equation:
∑k=0N
a
k
y
p
n−k=∑k=0M
b
k
xn−k
k
0
N
a
k
y
p
n
k
k
0
M
b
k
x
n
k
(16)
In order to solve, our guess for the solution to
y
p
n
y
p
n
will take on the form of the input,
xn
x
n
. After guessing at a solution to the above
equation involving the particular solution, one only
needs to plug the solution into the difference equation
and solve it out.
The indirect method utilizes the relationship between the
difference equation and z-transform, discussed earlier, to find a
solution. The basic idea is to convert the difference
equation into a z-transform, as described above, to get the
resulting output,
Yz
Y
z
.
Then by inverse transforming this and using partial-fraction
expansion, we can arrive at the solution.
"My introduction to signal processing course at Rice University."