BENT 4733-DIGITAL SIGNAL PROCESSING

Chapter 3: Difference Equation

Chapter Outline
3.1 LTI System Properties
3.2 Difference Equation
3.2.1 Non-recursive difference equation
3.2.2 Recursive difference equation
3.3 Signal Flow Graph
3.3.1 Signal Flow Graph FIR
3.3.2 Signal Flow Graph IIR
3.4 FIR Calculation
3.5 IIR Calculation

2
3.1 Linear time invariant (LTI) system
• By the principle of superposition, the response 𝑦[𝑛] of a discrete-time
LTI system ℎ[𝑛] is the sum of the responses to the individual shifted
impulses making up the input signal 𝑥[𝑛].

x[n] h[n] y[n]

• Few important properties of the system include linearity, time invariant,

causality and stability.
3.1 System property - Linearity

• The linearity means that the system obeys the superposition

principle

𝐻 (𝛼𝑥1 [𝑛] + 𝛽𝑥2 [𝑛]) = 𝛼𝐻 (𝑥1 [𝑛]) + 𝛽𝐻 (𝑥2 [𝑛])

3.1 System property – Time invariant
• A time-invariant system (shift invariant system) is one in which the
internal parameters do not vary with time.

𝑦[𝑛] = 𝐻 (𝑥[𝑛]) ⇒ 𝑦[𝑛 − 𝑟] = 𝐻 (𝑥[𝑛 − 𝑟]) ∀𝑟

3.1 System property - Causality a set of orders

• A system is said to be causal, if its output at time instant n depends only

on the present and past input values, but not on the future input values.
• It implies that for every choice of 𝑛𝑜 ; if 𝑥1 [𝑛] = 𝑥2 [𝑛] for 𝑛 < 𝑛𝑜 , then
𝑦1 [𝑛] = 𝑦2 [𝑛] for 𝑛 < 𝑛𝑜 .
• A causal system is the one in which the output 𝑦[𝑛] at time 𝑛 depends
only on the current input 𝑥[𝑛] at time 𝑛, and its past input sample
values such as 𝑥[𝑛 − 1], 𝑥[n − 2],..
• Otherwise, if a system output depends on future input values such as
𝑥[𝑛 + 1], 𝑥[𝑛 + 2],., the system is noncausal. The noncausal system
cannot be realized in real time.
3.1 System property - Stability test / final

• A system is said to be stable, if and only if every bounded input

sequence produces a bounded output sequence.
• This type of stability is called bounded-input bounded-output (BIBO)
stability.
• The input 𝑥[𝑛] is bounded if there exists a fixed positive finite value 𝛽𝑥
such that
𝑥[𝑛] ≤ 𝛽𝑥 < ∞ 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛
• Similarly, the output 𝑦[𝑛] is bounded if there exists a fixed positive finite
value 𝛽𝑦 such that
𝑦[𝑛] ≤ 𝛽𝑦 < ∞ 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 or 𝑆 = σ∞
𝑘=−∞ ℎ 𝑘 , 𝑆<∞
3.1 System property - LTI

LTI system must be linear and time invariant

It can either be BIBO stable or unstable, and it
can also be causal or non-causal
3.1 System property - Example

• Check for stability, causality, linearity, and time-invariance of the system

described by
𝑦[𝑛] = −1 𝑛 𝑥[𝑛]
Solution:
• This transformation outputs the current value of 𝑥[𝑛] multiplied by
either ±1.
• It is BIBO stable, since it does not change the magnitude of 𝑥[𝑛] and
hence satisfies the conditions for bounded-input bounded-output
stability
3.1 System property - Example
• It is causal, because each output depends only on the current value of
𝑥[𝑛].
• It is linear because:
𝑦1 [𝑛] = 𝐻[𝑛]𝑥1 [𝑛] = −1 𝑛 𝑥1 [𝑛]
𝑦2 [𝑛] = 𝐻[𝑛]𝑥2 [𝑛] = −1 𝑛 𝑥2 [𝑛]

𝐻[𝑛] (𝛼𝑥1 [𝑛] + 𝛽𝑥2 [𝑛]) = 𝛼𝐻[𝑛] 𝑥1 [𝑛] + 𝛽𝐻[𝑛]𝑥2 [𝑛]

−1 𝑛 (𝛼𝑥1 [𝑛] + 𝛽𝑥2 [𝑛]) = 𝛼 −1 𝑛 (𝑥1 [𝑛]) + 𝛽 −1 𝑛 (𝑥2 [𝑛])
3.1 System property - Example
• it is time varying:
𝑦[𝑛] = 𝐻[𝑛]𝑥[𝑛] = −1 𝑛 𝑥[𝑛]
If the input is shifted by 1, the output is
𝐻 𝑛 𝑥 𝑛 − 1 = −1 𝑛 𝑥 𝑛 − 1
If the output is shifted by 1,
𝑦 𝑛 − 1 = (−1)𝑛−1 𝑥[𝑛 − 1]
By comparison
𝐻 𝑛 𝑥[𝑛 − 1] ≠ 𝑦[𝑛 − 1]
3.1 System property - Exercise
• Determine whether the given systems are linear, time
invariant, causal and stable:

𝑦 𝑛 = 2𝑥[𝑛 − 5]
𝑦 𝑛 = 𝑥 2 [𝑛]

Please submit your answer through Ulearn within one week!

3.2 Differential and Difference Equation
• The difference?
– Continuous-time system can be represented by
using differential equations
– Discrete-time system can be represented by using
difference equations

13
3.2 Difference Equation - Categories
• An important class of Linear Time Invariant (LTI) of discrete-
time systems is one that is characterized by a linear
difference equation with constant coefficients.
• Difference equation can be divided into two different
types:
– Non-recursive difference equation
– Recursive difference equation

14
3.2 Difference Equation – General form
• A causal LTI system can be described by a difference equation
of the following form:

σ𝑁 σ𝑀
𝑦[𝑛] = − 𝑖=1 𝑎𝑖 𝑦[𝑛 − 𝑖] + 𝑗=0 𝑏𝑗 𝑥[𝑛 − 𝑗] (3.1)

– 𝑎𝑖 and 𝑏𝑗 are a non zero system coefficient.

– Notice that 𝑦 𝑛 is the current output, which depends on the past
output samples 𝑦 𝑛 − 1 , … , 𝑦[𝑛 − 𝑁] y(n-1), the current input
sample 𝑥[𝑛], and the past input samples 𝑥 𝑛 − 1 , … , 𝑥[𝑛 − 𝑀].
3.2 Difference Equation – Example 1
• Find the non-zero system coefficients given the following
difference equation:
𝑦 𝑛 = 0.25𝑦 𝑛 − 1 + 0.5𝑦 𝑛 − 3 + 𝑥 𝑛 + 0.1𝑥[𝑛 − 1]
• Solution:
– Using equation (3.1), we can see that

𝑏0 = 1, 𝑏1 = 0.1, 𝑎1 = −0.25, 𝑎3 = −0.5

3.2 Difference Equation – System Representation
• An LTI system can be completely described by its unit-impulse
response, which is defined as the system response ℎ[𝑛]due to
the impulse input 𝛿[𝑛] with zero initial conditions.

• I.e. when 𝑥 𝑛 = 𝛿[𝑛], 𝑦 𝑛 = ℎ[𝑛]

3.2 Difference Equation – Example 2
• Assume we have a LTI system 𝑦 𝑛 = 0.5𝑥 𝑛 + 0.25𝑥[𝑛 − 1]
with an initial conditon 𝑥 −1 = 0.

a. Determine the unit-impulse response ℎ[𝑛].

b. Draw the system block diagram.
c. Write the output using the obtained impulse response.
3.2 Difference Equation – Example 2
• The unit-impulse response ℎ[𝑛] can be obtained by replacing
𝑥[𝑛] with 𝛿[𝑛]. Thus
𝑦 𝑛 = 0.5𝑥 𝑛 + 0.25𝑥[𝑛 − 1]

ℎ 𝑛 = 0.5𝛿 𝑛 + 0.25𝛿[𝑛 − 1]
I.e. we have an impulse response of
0.5 𝑛=0
ℎ 𝑛 = 0.25 𝑛=1
0 𝑒𝑙𝑠𝑒𝑤ℎ𝑒𝑟𝑒
3.2 Difference Equation – Example 2
• The block diagram can be drawn as follow:

• The output can be written in terms of impulse response as:

𝑦 𝑛 = ℎ 0 𝑥 𝑛 + ℎ 1 𝑥[𝑛 − 1]
3.2.1 Non-recursive difference equation
• A non-recursive LTI discrete-time system can be characterized by a linear
constant coefficient difference equation of the form below (for causal
and non recursive):

𝑦[𝑛] = σ𝑁
𝑚=0 𝑏𝑚 𝑥[𝑛 − 𝑚] (3.2)

with 𝑥 𝑛 = 0 if 𝑛 < 0 and 𝑏𝑚 = 0 for 𝑚 > 𝑁

• Thus a LTI, causal, and non-recursive system can be characterized by an
Nth-order linear non-recursive difference equation.
• The Nth-order non-recursive difference equation has a finite impulse
response (FIR).
3.2.1 Non-recursive difference equation – Example
• Write the equation for a second order FIR
2

𝑦[𝑛] = ෍ 𝑏𝑚 𝑥[𝑛 − 𝑚]
𝑚=0

𝑦 𝑛 = 𝑏0 𝑥 𝑛 + 𝑏1 𝑥[𝑛 − 1] + 𝑏2 𝑥[𝑛 − 2]

22
3.2.2 Recursive difference equation
• The response of a discrete-time system depends on the present and
previous values of the input as well as the previous values of the output.
• A LTI, causal, and recursive discrete-time system can be represented by
the following Nth-order linear recursive difference equation:

𝑦[𝑛] = σ𝑁 𝑏
𝑚=0 𝑚 𝑥[𝑛 − 𝑚] − σ𝑁
𝑚=1 𝑎𝑚 𝑦[𝑛 − 𝑚] (3.3)

where 𝑎𝑚 and 𝑏𝑚 are constants.

• The Nth-order recursive difference equation has an infinite impulse
response (IIR).
• Hence, an IIR filter is characterized by a recursive difference equation.
3.2.2 Recursive difference equation - Example
• Write the equation for a second order IIR.

2 2

𝑦 𝑛 + ෍ 𝑎𝑚 𝑦[𝑛 − 𝑚] = ෍ 𝑏𝑚 𝑥[𝑛 − 𝑚]
𝑚=1 𝑚=0

𝑦[𝑛] + 𝑎1 𝑦[𝑛 − 1] + 𝑎2 𝑦[𝑛 − 2] = 𝑏0 𝑥[𝑛] + 𝑏1 𝑥[𝑛 − 1] + 𝑏2 𝑥[𝑛 − 2]

24
3.3 Signal Flow Graph
• Signal flow graph (SFG) represents digital system signal
processing routine in the illustration/graphical form.
• There are basic components generally used to illustrate the
SFG which are
Multiplier Adder Unit Delay
x(n) kk k
x(n)
x(n) kx(n)
kx(n)
kx(n) x(n) x(n)
x(n) y(n)=x(n)+w(n)
y(n)=x(n)+w(n)
y(n)=x(n)+w(n) x(n)
x(n)x(n) Z
-1 -1 -1 x(n-1)
Z Zx(n-1)
x(n-1)

Signal Flow Graph w(n)w(n)

w(n)

25
3.3.1 Signal Flow Graph-FIR
• A 2nd order FIR can be represented as:
2
y[ n]  

b[ ]x[ n   ]
0

 b[0] x[ n]  b[1]x[n  1]  b[ 2]x[n  2]

• The signal flow graph describing this equation is:

z 1 z 1

x[n]

b[0] b[1] b[2]

y[n]
26
3.3.2 Signal Flow Graph-IIR
• A 2nd order IIR can be represented as:
2 2
y[n]   a[ ]y[n   ]   b[ ]x[n   ]
 1  0
y[n]  a[1] y[n  1]  a[2] y[n  2]  b[0]x[n]  b[1]x[n  1]  b[2]x[n  2]

• The Type I (Direct Form I) signal flow graph for this is:

x[n] z 1 b[0] z 1 y[n]

z 1 b[1]  a[1] z 1

b[2]  a[2]
27
3.3.2 Signal Flow Graph-IIR
• A 2nd order of IIR can be represented as:
2 2
y[n]   a[ ]y[n   ]   b[ ]x[n   ]
 1  0

y[n]  a[1] y[n  1]  a[2] y[n  2]  b[0]x[n]  b[1]x[n  1]  b[2]x[n  2]

• The Type II (Direct Form II) signal flow graph for this is:

x[n] 1 b[0] y[n]

z
 a[1] z 1 b[1]

 a[2] b[2]
28
3.3.2 Signal Flow Graph-IIR
 A digital filter is canonic if the number of delays in the block
diagram representation is equal to the order of the difference
equation.
 Otherwise it is referred as non-canonic structure.
p0
x[n] + y[n]

z-1 z-1 First-order LTI digital filter

p1 -d1

y[n]  d1 y[n  1]  p0 x[n]  p1 x[n  1]

 The above structure is a non-canonic since it employs two delays to realize
the first-order difference equation.
29
3.4 FIR calculation - Example
A discrete-time system is a 2nd order FIR defined as

y[n]  0.5x[n] 1x[n 1]  0.5x[n  2]

It is assumed that the input 𝑥[𝑛] is valid for n 0, and zero for
n<0. The input is an impulse function

𝑥 𝑛 = [1 0 0 0 0 0 0 … ]

Calculate the output of the system.

30
3.4 FIR calculation - Example
y[n]  0.5x[n] 1x[n 1]  0.5x[n  2]
𝑥 𝑛 = [1 0 0 0 0 0 0 … ]
The computation for the output 𝑦[𝑛] is shown in the following
table.

Note that the output is zero for n  3.

31
3.4 IIR calculation - Example
A discrete-time system is 1st order IIR defined as

y[n]  0.5 y[n 1]  x[n]

It is assumed that the input 𝑥[𝑛] and output are valid for n  0,
and zero for n<0. The input is an impulse function

𝑥 𝑛 = [1 0 0 0 0 0 0 … ]

Calculate the output of the system.

32
3.4 IIR calculation - Example
y[n]  0.5 y[n 1]  x[n]
𝑥 𝑛 = [1 0 0 0 0 0 0 … ]
The computation for the output 𝑦[𝑛] is shown in the following
table.

Note that the output does not reach zero but approaches a small value as n
increases
33