Bài giảng Digital Signal Processing - Chương 4: FIR filtering and Convolution - Nguyễn Thanh Tuấn

Click to edit Master subtitle style Nguyen Thanh Tuan, M.Eng. 
Department of Telecommunications (113B3) 
Ho Chi Minh City University of Technology 
Email: nttbk97@yahoo.com 
 FIR filtering and Convolution 
 Chapter 4 
Digital Signal Processing 
Content 
2 FIR Filtering and Convolution 
 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 
Digital Signal Processing 
 Introduction 
3 
 Block processing methods: data are collected and processed in blocks. 
FIR Filtering and Convolution 
 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 
 Digital audio effects processing 
 Digital control systems 
 Adaptive signal processing 
Digital Signal Processing 
 1. Block Processing method 
4 
 The collected signal samples x(n), n=0, 1,, L-1, can be thought as a 
block: 
The duration of the data record in second: TL=LT 
 x=[x0, x1, , xL-1] 
 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 
FIR Filtering and Convolution 
Digital Signal Processing 
 11.1. Direct form 
5 
 The convolution in the direct form: 
 Find index n: index of h(m) 0≤m≤M 
( ) ( ) ( )
m
y n h 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 
 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 yL L M=L Mx 
FIR Filtering and Convolution 
Digital Signal Processing 
 1Direct form 
6 
 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 
min( , )
max(0, 1)
( ) ( ) ( )
M n
m n L
y n h m x n m
  h x
 The direct form of convolution is given as follows: 
FIR Filtering and Convolution 
0 n M L 1 with 
 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. 
Digital Signal Processing 
 Example 1 
7 
 Consider the case of an order-3 filter and a length of 5-input signal. 
Find the output ? 
FIR Filtering and Convolution 
 h=[h0, h1, h2, h3] 
 x=[x0, x1, x2, x3, x4 ] 
y=h*x=[y0, y1, y2, y3, y4 , y5, y6, y7 ] 
Digital Signal Processing 
1.2. Convolution table 
8 
 It can be observed that 
FIR Filtering and Convolution 
,
( ) ( ) ( )
i j
i j n
y n h i x j
 
 Convolution table 
 The convolution 
table is convenient 
for quick calculation 
by hand because it 
displays all required 
operations 
compactly. 
Digital Signal Processing 
 Example 2 
9 
 Calculate the convolution of the following filter and input signals? 
FIR Filtering and Convolution 
 h=[1, 2, -1, 1], x=[1, 1, 2, 1, 2, 2, 1, 1] 
 Solution: 
 sum of the values along anti-diagonal line yields the output y: 
 y=[1, 3, 3, 5, 3, 7, 4, 3, 3, 0, 1] 
 Note that there are Ly=L+M=8+3=11 output samples. 
Digital Signal Processing 
1.3. LTI Form 
10 
 LTI form of convolution: 
FIR Filtering and Convolution 
( ) ( ) ( )
m
y n x m h n m 
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 
 Consider the filter h=[h0, h1, h2, h3] and the input signal x=[x0, x1, x2, 
x3, x4 ]. Then, the output is given by 
We can represent the input and output signals as blocks: 
Digital Signal Processing 
1.3. LTI Form 
11 FIR Filtering and Convolution 
 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. 
Digital Signal Processing 
Example 3 
12 FIR Filtering and Convolution 
 Using the LTI 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: 
Digital Signal Processing 
1.4. Matrix Form 
13 FIR Filtering and Convolution 
 Based on the convolution equations 
 y Hx
 x is the column vector of the Lx input samples. 
 y is the column vector of the Ly =Lx+M put samples. 
 H is a rectangular matrix with dimensions (Lx+M)xLx . 
we can write 
Digital Signal Processing 
1.4. Matrix Form 
14 FIR Filtering and Convolution 
 It can be observed that H has the same entry along each diagonal. 
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 
Digital Signal Processing 
Example 4 
15 FIR Filtering and Convolution 
 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 
Digital Signal Processing 
1.5. Flip-and-slide form 
16 FIR Filtering and Convolution 
0 1 1 ...n n n M n My h x h x h x 
 The output at time n is given by 
 Flip-and-slide form of convolution 
 The flip-and-slide form shows clearly the input-on and input-off 
transient and steady-state behavior of a filter. 
Digital Signal Processing 
1.6. Transient and steady-state behavior 
17 FIR Filtering and Convolution 
 Transient and steady-state filter outputs: 
 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: 
Digital Signal Processing 
1.7. Overlap-add block convolution method 
18 FIR Filtering and Convolution 
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 
manageable length, say L samples. 
Digital Signal Processing 
Example 5 
19 FIR Filtering and Convolution 
 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: 
Digital Signal Processing 
Example 5 
20 FIR Filtering and Convolution 
 The output of each block is given by 
 Following from time invariant, aligning the output blocks according 
to theirs absolute timings and adding them up gives the final results: 
Digital Signal Processing 
2. Sample processing methods 
21 FIR Filtering and Convolution 
 The direct form convolution for an FIR filter of order M is given by 
Fig: Direct form realization 
of Mth order filter 
Sample processing algorithm 
 Introduce the internal states 
 Sample processing methods are 
convenient for real-time applications 
Digital Signal Processing 
Example 6 
22 FIR Filtering and Convolution 
 Consider the filter and input given by 
 Using the sample processing algorithm to compute the output and 
show the input-off transients. 
Digital Signal Processing 
Example 6 
23 FIR Filtering and Convolution 
Digital Signal Processing 
Example 
24 FIR Filtering and Convolution 
Digital Signal Processing 
Hardware realizations 
25 FIR Filtering and Convolution 
 The FIR filtering algorithm can be realized in hardware using DSP 
chips, for example the Texas Instrument TMS320C25 
MAC: Multiplier 
Accumulator 
Digital Signal Processing 
Hardware realizations 
26 FIR Filtering and Convolution 
 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 
Digital Signal Processing 
Example 7 
27 FIR Filtering and Convolution 
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: 
Digital Signal Processing 
 Homework 1 
28 FIR Filtering and Convolution 
Digital Signal Processing 
 Homework 2 
29 FIR Filtering and Convolution 
Digital Signal Processing 
 Homework 3 
30 FIR Filtering and Convolution 
Digital Signal Processing 
 Homework 4 
31 FIR Filtering and Convolution 
 Compute the output y(n) of the filter h(n) = {1, -1, 1, -1} and input 
x(n) = {1, 2, 3, 4, @, -3, 2, -1} 
Digital Signal Processing 
 Homework 5 
32 
 Compute the convolution, y = h ∗ x, of the filter and input, 
h(n) = {1, -1, -1, 1} , x(n) = {1, 2, 3, 4, @, -3, 2, -1} using the 
following methods: 
1. The convolution table. 
2. The LTI form of convolution, arranging the computations in a 
table form. 
3. The overlap-add method of block convolution with length-3 
input blocks. 
4. The overlap-add method of block convolution with length-4 
input blocks. 
5. The overlap-add method of block convolution with length-5 
input blocks. 
FIR Filtering and Convolution