Bài giảng Digital signal processing - Chapter 4: FIR filtering and Convolution - Nguyễn Thanh Tuấn

Download

Chapter 4

FIR filtering and Convolution

Nguyen Thanh Tuan,_CM_lic._kE_ton_eg_d._{it Master subtitle style}

Department of Telecommunications (113B3)

Ho Chi Minh City University of Technology

Email: [email protected]om

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

Digital Signal Processing

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

 Digital audio effects processing

 Digital control systems

 Adaptive signal processing

Digital Signal Processing

FIR Filtering and Convolution

1. Block Processing method

 The collected signal samples x(n), n=0, 1,…, L-1, can be thought as a

block:

x=[x₀, x₁, …, x_L-1]

The duration of the data record in second: T_L=LT

 Consider a casual FIR filter of order M with impulse response:

h=[h₀, h₁, …, h_M]

The length (the number of filter coefficients): L_h=M+1

Digital Signal Processing

FIR Filtering and Convolution

11.1. Direct form

 The convolution in the direct form:

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

 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

 L_x=L input samples which is processed by the filter with order M

L_y L M=L_x M

yield the output signal y(n) of length

Digital Signal Processing

FIR Filtering and Convolution

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(M ,n)

y(n) 

h(m)x(n m)  hx

with

0  n ML1



mmax(0,nL1)

 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

FIR Filtering and Convolution

Example 1

 Consider the case of an order-3 filter and a length of 5-input signal.

Find the output ?

h=[h₀, h₁, h₂, h₃]

x=[x₀, x₁, x₂, x₃, x₄]

y=h*x=[y₀, y₁, y₂, y₃, y₄, y₅, y₆, y₇]

Digital Signal Processing

FIR Filtering and Convolution

1.2. Convolution table

 It can be observed that

y(n)  h(i)x( j)



i, j

i jn

 Convolution table

 The convolution

table is convenient

for quick calculation

by hand because it

displays all required

operations

compactly.

Digital Signal Processing

FIR Filtering and Convolution

Example 2

 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:

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 L_y=L+M=8+3=11 output samples.

Digital Signal Processing

FIR Filtering and Convolution

1.3. LTI Form

 LTI form of convolution:

y(n)  x(m)h(n m)



 Consider the filter h=[h₀, h₁, h₂, h₃] and the input signal x=[x₀, x₁, x₂,

x₃, x₄]. Then, the output is given by

y(n)  x₀h(n) x₁h(n1) x₂h(n2) x₃h(n3) x₄h(n4)

 We can represent the input and output signals as blocks:

Digital Signal Processing

FIR Filtering and Convolution

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.

Digital Signal Processing

FIR Filtering and Convolution

Example 3

 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

FIR Filtering and Convolution

1.4. Matrix Form

 Based on the convolution equations

y  Hx

we can write

 x is the column vector of the L_xinput samples.

 y is the column vector of the L_y=L_x+M put samples.

 H is a rectangular matrix with dimensions (L_x+M)xL_x.

Digital Signal Processing

FIR Filtering and Convolution

1.4. Matrix Form

 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

FIR Filtering and Convolution

Example 4

 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  L_y=L_x+M=11, the filter matrix is

11x8 dimensional

Digital Signal Processing

FIR Filtering and Convolution

1.5. Flip-and-slide form

 The output at time n is given by

y_n h₀x_nh x ...h_Mx_nM

1 n1

 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

FIR Filtering and Convolution

1.6. Transient and steady-state behavior

 From LTI convolution:

y(n)  h(m)x(n m)  h x  h x ... h x



0 n

1 n1

M nM

m0

 The output is divided into 3 subranges:

 Transient and steady-state filter outputs:

Digital Signal Processing

FIR Filtering and Convolution

1.7. 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.

 Overlap-add block convolution method:

Digital Signal Processing

FIR Filtering and Convolution

Example 5

 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

FIR Filtering and Convolution

Example 5

 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

FIR Filtering and Convolution

Tải về để xem bản đầy đủ

32 trang myanh 23560 Free

Download

Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Digital signal processing - Chapter 4: FIR filtering and Convolution - Nguyễn Thanh Tuấn", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

bai_giang_digital_signal_processing_chapter_4_fir_filtering.pdf