ECE 3203

Digital Signal Processing

FIR Filtering & Convolution

Shah Muhammad Azmat Ullah

Lecturer,
Dept. of ECE, KUET.
Khulna University of Engineering & Technology
 Introduction
 The term convolution describes, how the input to a system interacts with the system to
produce the output.

 Generally the system output will be a delayed and attenuated or amplified version of
the input.

 It is particularly useful to consider the output from the system owing to an impulse
input. This is because any input may be represented as a sequence of impulses of
different strengths. The output of the system owing to the impulse input will not be a
corresponding impulse, but will vary with time, passing through a maximum, as shown
in Figure 4.18. This figure shows that at sampling instant m the output owing to the
unit impulse applied at sampling instant 0 is h(m).

 The characteristic is known as the impulse response h(m) of the system.

Department of Electronics and Communication Engineering (ECE) 2

 Introduction

Department of Electronics and Communication Engineering (ECE) 3

 Methods
 Practical DSP methods (Convolution also) fall in two basic classes:

1. Block processing methods.

2. Sample processing methods.

 In Block processing methods, the data are collected and processed in blocks.
1. Direct form
2. Convolution table
3. LTI form
4. Matrix form
5. Overlap-add method
6. Overlap-save method

 In Sample processing methods, the data are processed one at a time—with each input
sample being subjected to a DSP algorithm which transforms it into an output sample.

Department of Electronics and Communication Engineering (ECE) 4

 Block Processing Methods

Department of Electronics and Communication Engineering (ECE) 5

 1. Direct Form
h = [h0, h1, . . . , hM]  Length, Lh = M + 1
x = [x0, x1, . . . , xL-1]  Length, Lx = L

The convolution of the length-L input x with the order-M filter h will result in an output
sequence y(n).

We must determine:
1. the range of values of the output index n, and
2. the precise range of summation in m.

The index of h(m):0 ≤ m ≤ M

Similarly, the index of x(n − m):0 ≤ n −m ≤ L − 1

Department of Electronics and Communication Engineering (ECE) 6

 1. Direct Form

The index of h(m):0 ≤ m ≤ M

Similarly, the index of x(n − m):0 ≤ n −m ≤ L − 1

To determine the range of values of the output index n

m ≤ n ≤ L − 1 +m
0 ≤ m ≤ n ≤ L − 1 +m ≤ L − 1 + M,
0 ≤ n ≤ L − 1 +M

y = [y0, y1, . . . , yL−1+M]  Length, Ly = L +M

Setting Lx = L, and Lh = M+1,

L=L+L −1
y x h

Department of Electronics and Communication Engineering (ECE) 7

 1. Direct Form

Therefore, in the case of an order-M FIR filter and a length-L input, the direct form of
convolution is given as follows:

Department of Electronics and Communication Engineering (ECE) 8

 1. Direct Form

As an example, consider the case of an order-3 filter and a length-5 input signal. The filter,
input, and output blocks are
h = [h0, h1, h2, h3]
x = [x0, x1, x2, x3, x4]
y = h ∗ x = [y0, y1, y2, y3, y4, y5, y6, y7]

The output block has length Ly = L +M = 5 + 3 = 8 and is indexed as 0 ≤ n ≤ 7.The

convolutional equation becomes:

Department of Electronics and Communication Engineering (ECE) 9

 1. Direct Form

Department of Electronics and Communication Engineering (ECE) 10

 1. Direct Form

Department of Electronics and Communication Engineering (ECE) 11

 2. Convolution Table

For example, y(5) is obtained as

Department of Electronics and Communication Engineering (ECE) 12

 2. Convolution Table Example

Department of Electronics and Communication Engineering (ECE) 13

 3. LTI Form
h = [h0, h1, h2, h3]
x = [x0, x1, x2, x3, x4]

Department of Electronics and Communication Engineering (ECE) 14

 3. LTI Form

Department of Electronics and Communication Engineering (ECE) 15

 3. LTI Form

Department of Electronics and Communication Engineering (ECE) 16

 3. LTI Form Example

Department of Electronics and Communication Engineering (ECE) 17

 4. Matrix Form

y = Hx Ly × Lx = (L + M)×L

Department of Electronics and Communication Engineering (ECE) 18

 4. Matrix Form Example

Department of Electronics and Communication Engineering (ECE) 19

 4. Matrix Form

Alternative way:

Department of Electronics and Communication Engineering (ECE) 20

 4. Matrix Form Example

Department of Electronics and Communication Engineering (ECE) 21

 5. Overlap-Add Method

Department of Electronics and Communication Engineering (ECE) 22

 5. Overlap-Add Method Example

Department of Electronics and Communication Engineering (ECE) 23

 5. Overlap-Add Method Example

Department of Electronics and Communication Engineering (ECE) 24

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 25

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 26

 Sample Processing Methods
Pure Delays:

Department of Electronics and Communication Engineering (ECE) 27

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 28

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 29

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 30

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 31

 Sample Processing Methods

Department of Electronics and Communication Engineering (ECE) 32

 Sample Processing Methods
FIR Filtering in Direct Form

Department of Electronics and Communication Engineering (ECE) 33

 Sample Processing Methods
FIR Filtering in Direct Form

Department of Electronics and Communication Engineering (ECE) 34

 Sample Processing Methods
FIR Filtering in Direct Form

Department of Electronics and Communication Engineering (ECE) 35

 Sample Processing Methods
FIR Filtering in Direct Form

Department of Electronics and Communication Engineering (ECE) 36

 Sample Processing Methods
FIR Filtering in Direct Form

Department of Electronics and Communication Engineering (ECE) 37

 Sample Processing Methods Example

Department of Electronics and Communication Engineering (ECE) 38

 Sample Processing Methods Example

Department of Electronics and Communication Engineering (ECE) 39

 Circular Convolution

Department of Electronics and Communication Engineering (ECE) 40

 Circular Convolution (Periodic Convolution)
𝑁−1

𝑥3 𝑚 = 𝑥1 𝑛 𝑥2 𝑚 − 𝑛, 𝑚𝑜𝑑 𝑁 , 𝑚 = 0,1, … , 𝑁 − 1
𝑛=0

where 𝑥2 𝑚 − 𝑛, 𝑚𝑜𝑑 𝑁 is the reflected and circularly shifted version of 𝑥2 𝑚 and n

represents the number of indices that the sequence 𝑥 𝑛 is shifted to the right.

Convolution using DFT & IDFT

𝑦 𝑛 =𝑥 𝑛 ∗ℎ 𝑛

𝑌 𝑘 =𝑋 𝑘 𝐻 𝑘

𝑦 𝑛 = 𝐼𝐷𝐹𝑇{𝑋 𝑘 𝐻 𝑘 }

Department of Electronics and Communication Engineering (ECE) 41

 Circular Convolution (Periodic Convolution)
Compute (a) linear and (b) circular periodic
convolutions of two sequences 𝑥1 𝑛 = 1,1,2,2
and 𝑥2 𝑛 = {1,2,3,4} (c) Also find circular
convolution using DFT and IDFT.

Department of Electronics and Communication Engineering (ECE) 42

 Circular Convolution (Periodic Convolution)

Department of Electronics and Communication Engineering (ECE) 43

 Circular Convolution (Periodic Convolution)

Department of Electronics and Communication Engineering (ECE) 44

 Circular Convolution (Periodic Convolution)
Find the response of an FIR filter with impulse response h 𝑛 = 1,2,4 to the input sequence
and x 𝑛 = {1,2}.

Department of Electronics and Communication Engineering (ECE) 45

 References
 Digital Signal Processing: A Practical Approach
- Emmanuel C. Ifeachor & Barrie W. Jervis.

 Digital Signal Processing

- S. Salivahanan, A. Vallavaraj, C Gnanapriya.

 Digital Signal Processing Principles Algorithms and Applications

- John G. Proakis, Dimitris G. Manolakis

 Signals and Systems Using MATLAB

- Luis F. Chaparro

 Digital Signal Processing Using MATLAB

- Vinay K. Ingle, John G. Proakis

Department of Electronics and Communication Engineering (ECE) 46

Department of Electronics and Communication Engineering (ECE) 47