Bài giảng Xử lý tín hiệu số - Chương 4: Fir filtering and convolution - Hà Hoàng Kha

Chapter 4
FIR filtering and Convolution
Click to edit Master subtitle styleHa Hoang Kha, Ph.D.
Ho Chi Minh City University of Technology
Email: hhkha@hcmut.edu.vn
Content
™ Block processing methods
‰ Convolution: direct form, convolution table
‰ Convolution: LTI form, LTI table
‰ Matrix form
‰ Flip-and-slide form
‰ Overlap-add block convolution method
™ Sample processing methods 
‰ FIR filtering in direct form
Ha H. Kha 2 FIR Filtering and Convolution
Introduction
™ Block processing methods: data are collected and processed in blocks.
‰ FIR filtering of finite-duration signals by convolution 
‰ Fast convolution of long signals which are broken up in short segments
‰ DFT/FFT spectrum computations
‰ Speech analysis and synthesis
‰ Image processing
™ Sample processing methods: the data are processed one at a time-
with each input sample being subject to a DSP algorithm which 
transforms it into an output sample.
‰ Real-time applications
‰ l d ffDigita au io e ects processing
‰ Digital control systems
‰ Adaptive signal processing
3 FIR Filtering and Convolution
Ha H. Kha
1. Block Processing method
™ The collected signal samples x(n), n=0, 1,, L-1, can be thought as a 
block: [ ]x= x0, x1, , xL-1
The duration of the data record in second: TL=LT
™ Consider a casual FIR filter of order M with impulse response:
h=[h0, h1, , hM]
The length (the number of filter coefficients): Lh=M+1
4 FIR Filtering and ConvolutionHa H. Kha
11.1. Direct form
™ The convolution in the direct form: 
( ) ( ) ( )h∑
m
y n m x n m= −
™ For DSP implementation, we must determine
‰ The range of values of the output index n
‰ The precise range of summation in m
™ Find index n: index of h(m) Æ 0≤m≤M
index of x(n m) Æ 0≤n m≤L 1 - - -
Æ 0 ≤ m ≤ n ≤m+L-1 ≤ M+L-1 
0 n M L 1≤ ≤ + − 
™ Lx=L input samples which is processed by the filter with order M 
yield the output signal y(n) of length L L M=L M= + +
5
 y x
FIR Filtering and ConvolutionHa H. Kha
1Direct form
™ Find index m: index of h(m) Æ 0≤m≤M
index of x(n-m) Æ 0≤n-m≤L-1 Æ n+L-1≤ m ≤ n 
( ) ( )max 0, n L 1 m min M, n− + ≤ ≤
™ The direct form of convolution is given as follows:
min( , )
(0 1)
( ) ( ) ( )
M n
L
y n h m x n m
+
= − = ∗∑ h x 0 n M L 1≤ ≤ + −with
max ,m n= −
™ Thus, y is longer than the input x by M samples. This property 
follows from the fact that a filter of order M has memory M and 
keeps each input sample inside it for M time units.
6 FIR Filtering and ConvolutionHa H. Kha
Example
™ Consider the case of an order-3 filter and a length of 5-input signal. 
Find the o tp t ? u u 
h=[h0, h1, h2, h3]
x=[x0, x1, x2, x3, x4 ]
y=h*x=[y0, y1, y2, y3, y4 , y5, y6, y7 ] 
7 FIR Filtering and ConvolutionHa H. Kha
1.2. Convolution table
™ It can be observed that ( ) ( ) ( )
i j
y n h i x j= ∑
,
i j n+ =
™ Convolution table
™ The convolution 
table is convenient 
for quick calculation 
b h d b iy an ecause t 
displays all required 
operations 
compactly.
8 FIR Filtering and ConvolutionHa H. Kha
Example
™ Calculate the convolution of the following filter and input signals? 
h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]
™ S l io ut on: 
sum of the values along anti-diagonal line yields the output y:
=[1 3 3 5 3 7 4 3 3 0 1]y , , , , , , , , , , 
Note that there are Ly=L+M=8+3=11 output samples.
9 FIR Filtering and ConvolutionHa H. Kha
1.3. LTI Form
™ LTI form of convolution: ( ) ( ) ( )y n x m h n m= −∑
m
™ Consider the filter h=[h0, h1, h2, h3] and the input signal x=[x0, x1, x2, 
x3, x4 ]. Then, the output is given by 
0 1 2 3 4( ) ( ) ( 1) ( 2) ( 3) ( 4)y n x h n x h n x h n x h n x h n= + − + − + − + −
™We can represent the input and output signals as blocks: 
10 FIR Filtering and ConvolutionHa H. Kha
1.3. LTI Form
™ LTI form of convolution: 
™ LTI form of convolution provides a more intuitive way to under 
stand the linearity and time invariance properties of the filter
11 FIR Filtering and Convolution
 - .
Ha H. Kha
Example
™ Using the LTI form to calculate the convolution of the following 
filter and inp t signals? u 
h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]
™ S l io ut on: 
12 FIR Filtering and ConvolutionHa H. Kha
1.3. Matrix Form
™ Based on the convolution equations
=y Hx
‰ x is the column vector of the Lx input samples.
we can write
‰ y is the column vector of the Ly =Lx+M put samples.
‰ H is a rectangular matrix with dimensions (L +M)xL x x .
13 FIR Filtering and ConvolutionHa H. Kha
1.3. Matrix Form
™ It b b d th t H h th t l h di l can e o serve a as e same en ry a ong eac agona . 
Such a matrix is known as Toeplitz matrix.
™Matrix representations of convolution are very useful in some 
applications:
‰ Image processing
‰ Advanced DSP methods such as parametric spectrum estimation and adaptive 
filtering
14 FIR Filtering and ConvolutionHa H. Kha
Example
™ Using the matrix form to calculate the convolution of the following 
filter and input signals? 
h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]
™ Solution: since Lx=8, M=3 Æ Ly=Lx+M=11, the filter matrix is 
11x8 dimensional 
15 FIR Filtering and ConvolutionHa H. Kha
1.4. Flip-and-slide form
™ The output at time n is given by
0 1 1 ...n n n M n My h x h x h x− −= + + +
™ li d lid f f l iF p-an -s e orm o convo ut on
™ The flip-and-slide form shows clearly the input-on and input-off 
transient and steady-state behavior of a filter.
16 FIR Filtering and Convolution
Ha H. Kha
1.5. Transient and steady-state behavior
™ From LTI convolution: 0 1 1
0
( ) ( ) ( ) ...
M
n n M n M
m
y n h m x n m h x h x h x− −
=
= − = + + +∑
™ The output is divided into 3 subranges:
™ T i d d filrans ent an stea y-state ter outputs:
17 FIR Filtering and ConvolutionHa H. Kha
1.6. Overlap-add block convolution method
™ As the input signal is infinite or extremely large, a practical approach 
is to divide the long input into contiguous non-overlapping blocks of 
™Overlap-add block convolution method:
manageable length, say L samples. 
18 FIR Filtering and ConvolutionHa H. Kha
Example
™ Using the overlap-add method of block convolution with each bock 
length L=3, calculate the convolution of the following filter and 
input signals? h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1]
™ Solution: The input is divided into block of length L=3 
The output of each block is found by the convolution table:
19 FIR Filtering and ConvolutionHa H. Kha
Example
™ The output of each block is given by
™ F ll i f i i i li i h bl k dio ow ng rom t me nvar ant, a gn ng t e output oc s accor ng 
to theirs absolute timings and adding them up gives the final results:
20 FIR Filtering and ConvolutionHa H. Kha
2. Sample processing methods
™ The direct form convolution for an FIR filter of order M is given by
™ Introduce the internal states
Sample processing algorithm
Fig: Direct form realization 
f M h d fil
™ Sample processing methods are
convenient for real time applications
21 FIR Filtering and Convolution
o t or er ter -
Ha H. Kha
Example
™ Consider the filter and input given by
Using the sample processing algorithm to compute the output and 
show the input-off transients.
22 FIR Filtering and ConvolutionHa H. Kha
Example
23 FIR Filtering and ConvolutionHa H. Kha
Example
24 FIR Filtering and ConvolutionHa H. Kha
Hardware realizations
™ The FIR filtering algorithm can be realized in hardware using DSP 
chips, for example the Texas Instrument TMS320C25
™MAC: Multiplier 
Accumulator
25 FIR Filtering and ConvolutionHa H. Kha
Hardware realizations
™ The signal processing methods can efficiently rewritten as
™ In modern DSP chips, the two 
operations 
can carried out with a single instruction. 
™ The total processing time for each input sample of Mth order filter:
where Tinstr is one instruction cycle in about 30-80 nanoseconds.
™ For real-time application, it requires that 
26 FIR Filtering and ConvolutionHa H. Kha
Example
™What is the longest FIR filter that can be implemented with a 50 nsec
per instruction DSP chip for digital audio applications with sampling 
frequency fs=44.1 kHz ?
Solution:
27 FIR Filtering and ConvolutionHa H. Kha
Homework
™ Problems 4.1, 4.2, 4.3, 4.5, 4.15, 4.18
28 FIR Filtering and ConvolutionHa H. Kha