Digital Signal Processing - Finite impulse response of LTI systems

By Assoc.Prof.Dr. Thuong Le-Tien 1
DIGITAL SIGNAL PROCESSING
FINITE IMPULSE RESPONSE 
OF LTI SYSTEMS
Lectured by: Assoc. Prof. Dr. Thuong Le-Tien
National Distinguished Lecturer
HCMC September, 2011
1
Practical DSP methods fall in two basis classes:
1. Block Processing Methods
2. Sample Processing Methods
In block processing methods, data are collected and 
processed in blocks (DFT/FFT spectrum 
computation, speech analysis and synthesis, image 
processing.
In sample processing methods, data are processed 
one at a time (real-time applications, audio effects 
processing , digital controls, 
2By Assoc.Prof.Dr. Thuong Le-Tien
In this chapter, block processing and sample 
processing methods applied to FIR filtering 
and Convolution. Several computational 
aspects of convolution equations are 
considered: 
* Direct form
* Convolution table
* LTI form
* Matrix form
* Flip-and-slide form
* Overlap-add block convolution form.
* Z-Transform (discussed in the Z-transform 
Chapter)
3By Assoc.Prof.Dr. Thuong Le-Tien
1. Block processing methods
1.1. Convolution
Sampling time interval, T=1/fs.
Number of time samples: L = TLfs
x(n) = [x0, x1,  , xL-1]
where n = 0, 1, , L – 1:
The direct and convolution forms
Convolution table form
 
mm
mnhmxmnxmhny )()()()()(
)()()()(
.
njijxihny
ji

4By Assoc.Prof.Dr. Thuong Le-Tien
1.2 DIRECT FORM
Consider a causal FIR filter of order M with 
impulse response h(n), 
h = [h0, h1, , hM] 
where n = 0, 1, , M 
the length of the filter or the number of filter 
coefficients LH = M + 1 
The output of the filter:
 
m
mnxmhny )()()(
5By Assoc.Prof.Dr. Thuong Le-Tien
with conditions 0  m  M
and 0  n – m  L – 1 
 m  n  L – 1 + m
The limit of output index n: 
0  m  n  L – 1 + m  L – 1 + M 
 0  n  L – 1 + M
y = [y0, y1, y2,  , yL – 1 + M]
The length of output: Ly = L + M 
Ly = Lx + Lh –1
6By Assoc.Prof.Dr. Thuong Le-Tien
M must satisfy simultaneously the inequalities
0  m  M
n – L + 1  m  n
7By Assoc.Prof.Dr. Thuong Le-Tien
It follows:
max(0, n – L + 1 )  m  min(n,M) 
The direct form of convolution 
Example: an order 3 filter and a length 5-input 
signal: h = [h0, h1, h2, h3]
x = [x0, x1, x2, x3, x4]
y = h * x = [y0, y1, y2, y3, y4, y5, y6, y7]



),min(
)1,0max(
)()()(
Mn
Lnm
mnxmhny
8By Assoc.Prof.Dr. Thuong Le-Tien
Equation applied: 
for n= 0, 1, 2,.7
max (0, 0 – 4 )  m  min(0, 3) => m = 0
max (0, 1 – 4 )  m  min(1, 3) => m = 0, 1
max (0, 2 – 4 )  m  min(2, 3) => m = 0,1 ,2
max (0, 3 – 4 )  m  min(3, 3) => m = 0, 1, 2, 3
max (0, 4 – 4 )  m  min(4, 3) => m = 0, 1, 2, 3
max (0, 5 – 4 )  m  min(5, 3) => m = 1, 2, 3
max (0, 6 – 4 )  m  min(6, 3) => m = 2, 3
max (0, 7 – 4 )  m  min(7, 3) => m = 3
i.e. n = 5, y5 = h1x4 + h2x3 + h3x2
7...,,1,0)()()(
)3,min(
)4,0max(
 

nmnxmhny
n
nm
9By Assoc.Prof.Dr. Thuong Le-Tien
All the output samples:
y0 = h0x0
y1 = h0x1 + h1x0
y2 = h0x2 + h1x1 + h2x0
y3 = h0x3 + h1x2 + h2x1 + h3x0
y4 = h0x4 + h1x3 + h2x2 + h3x1
y5 = h1x4 + h2x3 + h3x2
y6 = h2x4 + h3x3
y7 = h3x4
10By Assoc.Prof.Dr. Thuong Le-Tien
1.3. Convolution table:
11By Assoc.Prof.Dr. Thuong Le-Tien
Example: Find the convolution of the following 
filter and input signal 
h = [1, 2, -1, 1]
x = [1, 1, 2, 1, 2, 2, 1, 1]
y = [1, 3, 3, 5, 3, 7, 4, 3, 3, 0, 1]
Ly = L + M = 8 + 3 = 11
12By Assoc.Prof.Dr. Thuong Le-Tien
1.4. LTI form:
h = [h0, h0, h2, h3]
x = [x0, x1, x2, x3, x4]
Input x can be rewritten as a linear combination of delayed 
impulses
x = x0[1, 0, 0, 0, 0] + x1[0, 1, 0, 0, 0] + x2[0, 0, 1, 0, 0] + 
x3[0, 0, 0, 1, 0] + x4[0, 0, 0, 0, 1]
x(n)=x0(n)+x1(n–1)+x2(n–2)+x3(n–3)+x4(n–4)
Then:
y(n)=x0h(n)+x1h(n–1)+x2h(n–2)+x3h(n–3)+x4h(n–4) 
13By Assoc.Prof.Dr. Thuong Le-Tien
We can present the input and output signals as blocks:
14By Assoc.Prof.Dr. Thuong Le-Tien
LTI form of convolution
15By Assoc.Prof.Dr. Thuong Le-Tien
Example: h = [1, 2, -1, 1] and 
x = [1, 1, 2, 1, 2, 2, 1, 1]
16By Assoc.Prof.Dr. Thuong Le-Tien
The LTI form can also be written in a form 
similar by determine the proper limits of
For n = 0, 1, , L + M – 1 
17By Assoc.Prof.Dr. Thuong Le-Tien
1.5. Matrix form
Linear matrix form: y = Hx
The filter matrix H must be rectangular with 
dimensions:
Ly * Lx = (L + M) * L
H is also called the TOEPLITZ MATRIX in the sense of that 
it has the same entry a long each diagonal
Hx
x
x
x
x
x
h
hh
hhh
hhhh
hhhh
hhh
hh
h
y
y
y
y
y
y
y
y
y 






































































4
3
2
1
0
3
23
123
0123
0123
012
01
0
7
6
5
4
3
2
1
0
0000
000
00
0
0
00
000
0000
18By Assoc.Prof.Dr. Thuong Le-Tien
Example: 
There is also a matrix
Form written as follows
19By Assoc.Prof.Dr. Thuong Le-Tien
1.6. Flip and slide
yn = h0xn + h1xn-1 + h2xn-2 +  + hMxn-M
the first M outputs correspond to the input-on 
transient behavior of the filter, and the last M 
outputs beyond the end of the input data are 
the input-off transients. The remains are the 
steady-state outputs. 
20By Assoc.Prof.Dr. Thuong Le-Tien
1.7. Transient and Steady-State Behavior
Length of input signal is L, filter order M, the output 
can be separated into 3 parts
0  n < M (input on transient)
M  n  L – 1 (steady state)
L – 1 < n  L – 1 + M (input off transient)
21By Assoc.Prof.Dr. Thuong Le-Tien
Example: An IIR filter has xung h(n) = 
(0.75)nu(n). Using convolution to find y(n) 
when the inputs are:
a) x(n) = u(n)
b) x(n) = (-1)nu(n)
c) x(n) = u(n) – u(n – 25)
Find the steady state response for each case.
Solve:
a) 


n
m
n
m
ny
00
)( m)-u(m)u(n(0.75)m)-h(m)x(n n







n
m
n
n
0
1
)75.0(34
75.01
)75.0(1n(0.75)
4
75.01
1
)( 

nylim
22By Assoc.Prof.Dr. Thuong Le-Tien
b)
Steady state response:



n
m 0
( mn (0.75)-1)



n
m
n
m
ny
00
)( m-nm(-1)(0.75) m)-h(m)x(n
 (0.75)
7
3
 + 
7
4
(-1) =
75.01
)75.0(1
(-1) nn
1
n



n
7
4
)1(
75.01
1
1)(- y(n) n n


23By Assoc.Prof.Dr. Thuong Le-Tien


 
n
Lnm
m
n
Lnm
mnmn xhy
)1,0max()1,0max(
)75.0(
c)
Two cases:
24By Assoc.Prof.Dr. Thuong Le-Tien
n
nn
m
ny )75.0(34
75.01
)75.0(1
(0.75)
1
0
m 









n
nm
ny
24
25
24-nm 
0.75-1
(0.75)-1
(0.75) = (0.75)
1.8. Overlap-Add Block Convolution Method
Overlap-add convolution method 
25By Assoc.Prof.Dr. Thuong Le-Tien
Example: 
26By Assoc.Prof.Dr. Thuong Le-Tien
2. Sample processing method
Adder
Multiplier
Delay
27By Assoc.Prof.Dr. Thuong Le-Tien
FIR Filtering in Direct Form
Direct form realization of third-order filter. 
28By Assoc.Prof.Dr. Thuong Le-Tien