INTRODUCTION TO DIGITAL SIGNAL PROCESSING

Analog Digital

• Analysis, synthesis and modify

• Analog signal processing
• Digital signal processing

www.iammanuprasad.com
 BASIC BLOCKS OF DIGITAL SIGNAL PROCESSING

Digital
Analog AD DA Analog
Pre filter Signal Post filter
input Converter Converter output
Processor

www.iammanuprasad.com
 Discrete Fourier Transform (DFT)

• DFT is a powerful computation tool which allows us to evaluate the Fourier transform on a digital computer or
specifically designed hardware
• We notate like this

𝑋 𝑘 = 𝐷𝐹𝑇[𝑥 𝑛 ] 𝑥 𝑛 = 𝐼𝐷𝐹𝑇[𝑋 𝑘 ]

DFT IDFT 𝑁−1

𝑁−1 1 𝑗2𝜋𝑘𝑛
𝑗2𝜋𝑘𝑛 𝑥(𝑛) = ෍ 𝑋 𝑘 𝑒 𝑁 , 0 ≤ n ≤ N − 1
−
𝑋 𝑘 = ෍𝑥 𝑛 𝑒 𝑁 ,0 ≤ k ≤ N − 1 𝑁
𝑘=0
𝑛=0

𝑗2𝜋
Let us define a term 𝑊𝑁 = 𝑒 − 𝑁 which is known as twiddle factor and substitute in above equations

𝑁−1 𝑁−1
1
𝑋 𝑘 = ෍𝑥 𝑛 𝑊𝑁𝑛𝑘 ,0 ≤ k ≤ N−1 𝑥(𝑛) = ෍ 𝑋 𝑘 𝑤𝑁−𝑛𝑘 , 0 ≤ n ≤ N − 1
𝑁
𝑛=0 𝑘=0

www.iammanuprasad.com
 𝑁−1
Let us take an example 𝑗2𝜋𝑘𝑛
−
𝑋 𝑘 = ෍𝑥 𝑛 𝑒 𝑁 ,0 ≤ k ≤ N − 1
Q) Find the DFT of the sequence 𝑥 𝑛 = {1,1,0,0}
𝑛=0

𝑁=4 𝑘=2 3
𝑗𝜋2𝑛
3 −
𝑗2𝜋𝑘𝑛 𝑋 2 = ෍𝑥 𝑛 𝑒 2
−
𝑋 𝑘 = ෍𝑥 𝑛 𝑒 4 ,0 ≤ k ≤ N − 1 𝑛=0
𝑛=0 = 𝑥 0 + 𝑥 1 𝑒 −𝑗𝜋 + 𝑥 2 𝑒 −𝑗2𝜋 + 𝑥 3 𝑒 −𝑗3𝜋

𝑘=0 = 1 + 1 cos 𝜋 − 𝑗 sin 𝜋 + 0 + 0 = 1−1=0

3
𝑗2𝜋0𝑛 𝑘=3 3
−
𝑋 0 = ෍𝑥 𝑛 𝑒 4 −
𝑗𝜋3𝑛
𝑋 3 = ෍𝑥 𝑛 𝑒 2
𝑛=0
𝑛=0
𝑗3𝜋 𝑗9𝜋
=𝑥 0 +𝑥 1 +𝑥 2 +𝑥 3 = 𝑥 0 + 𝑥 1 𝑒− 2 + 𝑥 2 𝑒 −𝑗3𝜋 + 𝑥 3 𝑒 − 2

=1+1+0+0 =2 3𝜋 3𝜋
= 1 + 1 cos − 𝑗 sin +0+0 =1+𝑗
2 2
𝑘=1 3
𝑗𝜋𝑛
𝑋 1 = ෍ 𝑥 𝑛 𝑒− 2
𝑛=0
𝑗𝜋 𝑗3𝜋
𝑋 𝑘 = 2, 1 − 𝑗, 0,1 + 𝑗
− −
=𝑥 0 +𝑥 1 𝑒 + 𝑥 2 𝑒 −𝑗𝜋 + 𝑥 3 𝑒
2 2

𝜋 𝜋
= 1 + 1 cos − 𝑗 sin + 0 + 0 = 1 − 𝑗 www.iammanuprasad.com
2 2
 DFT as linear transformation (Matrix method)
DFT We can also represent the equation in matrix format

𝑁−1 1 1 1 1 … 1
𝑊𝑁𝑛𝑘 𝑋(0) 𝑁−1 𝑥(0)
𝑋 𝑘 = ෍𝑥 𝑛 𝑒 ,0 ≤ k ≤ N − 1 1 𝑊𝑁1 𝑊𝑁2 𝑊𝑁3 … 𝑊𝑁
𝑗2𝜋
𝑋(1) 𝑥(1)
𝑛=0 1 𝑊𝑁2 𝑊𝑁4 𝑊𝑁6 … 2(𝑁−1)
𝑊𝑁 = 𝑒 − 𝑁 𝑋(2)
= 1
𝑊𝑁 𝑥(2)
…
𝑋(3) 𝑊𝑁3 𝑊𝑁6 𝑊𝑁9 3(𝑁−1)
𝑊𝑁 𝑥(3)
⋮ …
⋮ ⋮ ⋮ ⋮ ⋮ ⋮
Lets put n = 0,1,2, … N-1 𝑋(𝑁 − 1) 2(𝑁−1) 3(𝑁−1) 𝑥(𝑁 − 1)
𝑁−1 𝑁−1 𝑁−1
1 𝑊𝑁 𝑊𝑁 𝑊𝑁 … 𝑊𝑁
(𝑁−1)𝑘
𝑋 𝑘 = 𝑥 0 . 1 + 𝑥 1 . 𝑊𝑁1𝑘 + 𝑥 2 . 𝑊𝑁2𝑘 + ⋯ + 𝑥 𝑁 − 1 𝑊𝑁 1 1 … 1
𝑋𝑁 = 𝑊𝑁 𝑥𝑁 1 𝑊𝑁−1 −(𝑁−1)
𝑘=0 𝑊𝑁−1 = ⋮ ⋱ 𝑊𝑁
⋮
𝑋 0 = 𝑥 0 + 𝑥 1 + 𝑥 2 + ⋯+ 𝑥 𝑁 − 1 𝑥𝑁 = 𝑊𝑁−1 𝑋𝑁 1 𝑊𝑁
− 𝑁−1
… 𝑊𝑁
−(𝑁−1)(𝑁−1)

𝑘=1
(𝑁−1)
𝑋 1 = 𝑥 0 + 𝑥 1 . 𝑊𝑁1 + 𝑥 2 . 𝑊𝑁2 + ⋯ + 𝑥 𝑁 − 1 𝑊𝑁 IDFT
𝑁−1
1
⋮ 𝑥(𝑛) = ෍ 𝑋 𝑘 𝑤𝑁−𝑛𝑘 , 0 ≤ n ≤ N − 1
𝑁
𝑘=0
𝑘 =𝑁−1
𝑁−1
1 ∗ Comparing we get
𝑋 𝑁 − 1 = 𝑥 0 + 𝑥 1 . 𝑊𝑁
(𝑁−1) 2(𝑁−1)
+ 𝑥 2 . 𝑊𝑁
(𝑁−1)(𝑁−1)
+ ⋯ + 𝑥 𝑁 − 1 𝑊𝑁 𝑥(𝑛) = ෍ 𝑋 𝑘 𝑤𝑁𝑛𝑘
𝑁
𝑘=0
1 ∗
𝑊𝑁−1 = 𝑊
Symbolically we can 1 𝑁 𝑁
𝑥(𝑛) = 𝑋 𝑊∗
write as
www.iammanuprasad.com 𝑁 𝑁 𝑁
 Twiddle factor matrix

𝑗2𝜋 Lies on the unit circle in the complex plane from 0 to 2π angle and it gets
𝑊𝑁 = 𝑒− 𝑁 repeated for every cycle
𝑒 𝑗𝜃 = cos 𝜃 + 𝑗𝑠𝑖𝑛 𝜃

Imaginary
𝑊20 𝑊20 1 1 axis
𝑊2 = =
𝑊20 𝑊21 1 −1 𝑊 3, 𝑊 7 , 𝑊 11
𝑗 Phase change ( 00 - 3600) -
anticlockwise

𝑊40 𝑊40 𝑊40 𝑊40 1 1 1 1 𝑊 2 , 𝑊 6 , 𝑊 10 𝑊0 , 𝑊4, 𝑊8

𝑊40 𝑊41 𝑊42 𝑊43 1 −𝑗 −1 𝑗 𝑊1 −1 1 Real axis
𝑊4 = =
𝑊40 𝑊42 𝑊44 𝑊46 1 −1 1 −1
1 𝑗 −1 −𝑗 Since e-jθ – clockwise
𝑊40 𝑊43 𝑊46 𝑊49
−𝑗
𝑊1 , 𝑊 5, 𝑊 9

www.iammanuprasad.com
 Relationship of the DFT to Fourier Transform

Fourier-Transform DFT

𝑁−1 𝑁−1
𝑗2𝜋𝑘𝑛
𝑗𝜔 −𝑗𝜔𝑛 −
𝑋 𝑒 = ෍𝑥 𝑛 𝑒 𝑋 𝑘 = ෍𝑥 𝑛 𝑒 𝑁
𝑛=0 𝑛=0

Comparing the above equations we get to find that DFT of x(n)

is a sampled version of the FT of the sequence

𝑋 𝑘 = 𝑋(𝑒 𝑗𝜔 )ቚ 2𝜋𝑘 , 𝑘 = 0,1,2, … 𝑁 − 1

𝜔= 𝑁

Relationship between DFT & Fourie Transform

www.iammanuprasad.com
 Relationship of the DFT to Z-Transform
𝑗2𝜋𝑘 𝑁
Z-Transform IDFT 𝑁−1 −1
1 1− 𝑒 𝑁 𝑧
𝑋(𝑧) = ෍ 𝑋(𝑘) 𝑗2𝜋𝑘
𝑁
𝑁−1 𝑁−1 𝑘=0 1 − 𝑒 𝑁 𝑧 −1
−𝑛 1 𝑗2𝜋𝑘𝑛
𝑋 𝑍 = ෍𝑥 𝑛 𝑧 𝑥(𝑛) = ෍ 𝑋 𝑘 𝑒 𝑁
𝑁 𝑁−1
𝑛=0 𝑘=0 1 1 − 𝑒 𝑗2𝜋𝑘 𝑧 −𝑁
= ෍ 𝑋(𝑘) 𝑗2𝜋𝑘
𝑁
𝑘=0 1 − 𝑒 𝑁 𝑧 −1
Substitute the value of x(n)

In the above condition 𝑒 𝑗2𝜋𝑘 = 1 for all the values of k

𝑁−1 𝑁−1
1 𝑗2𝜋𝑘𝑛
𝑋 𝑍 =෍ ෍ 𝑋 𝑘 𝑒 𝑁 𝑧 −𝑛 𝑁−1
𝑁 1 1 − 𝑧 −𝑁
𝑛=0 𝑘=0 = ෍ 𝑋(𝑘) 𝑗2𝜋𝑘
𝑁
𝑘=0 1− 𝑒 𝑁 𝑧 −1

𝑁−1 𝑁−1
1 𝑗2𝜋𝑘𝑛
= ෍ 𝑋(𝑘) ෍ 𝑒 𝑁 𝑧 −𝑛 𝑁−1
𝑁 1 − 𝑧 −𝑁 𝑋(𝑘)
𝑘=0 𝑛=0 𝑋 𝑧 = ෍ 𝑗2𝜋𝑘
𝑁−1 𝑁
N 𝑘=0 1−𝑒 𝑁 𝑧 −1
1−a
෍ 𝑎𝑛 =
𝑁−1 𝑁−1 𝑛 1−a
1 𝑗2𝜋𝑘 𝑘=0
= ෍ 𝑋(𝑘) ෍ 𝑒 𝑁 𝑧 −1 Relationship between DFT & Z- Transform
𝑁
𝑘=0 𝑛=0

www.iammanuprasad.com
 Properties of Discrete Fourier Transform

Periodicity
Circular time shift
If X(k) is N-point DFT of a finite duration sequences x(n) then If X(k) is N-point DFT of a finite duration sequences x(n) then

𝑗2𝜋𝑘𝑚
𝑥 𝑛 + 𝑁 = 𝑥 𝑛 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑛 𝐷𝐹𝑇 𝑥 𝑛 − 𝑚 𝑁
= 𝑋 𝑘 𝑒− 𝑁

X 𝑘 + 𝑁 = 𝑋 𝑘 𝑓𝑜𝑟 𝑎𝑙𝑙 𝑘
Proof
IDFT
𝑁−1
Linearity 1 𝑗2𝜋𝑘𝑛
𝑥(𝑛) = ෍ 𝑋 𝑘 𝑒 𝑁 , 0 ≤ n ≤ N − 1
𝑁
𝑘=0
If two finite sequences x1(n) and x2(n) are linearly combined as Put n=n-m
𝑁−1
𝑥3 𝑛 = 𝑎𝑥1 𝑛 + 𝑏𝑥2 (𝑛) 1 𝑗2𝜋𝑘(𝑛−𝑚)
𝑥(𝑛 − 𝑚) = ෍ 𝑋 𝑘 𝑒 𝑁
𝑁 Take DFT on both sides
𝑘=0
Then DFT of the sequence 𝑁−1
1 𝑗2𝜋𝑘𝑛 −𝑗2𝜋𝑘𝑚
= ෍𝑋 𝑘 𝑒 𝑁 𝑒 𝑁
𝑋3 𝑘 = 𝑎𝑋1 𝑘 + 𝑏𝑋2 (𝑘) 𝑁 −𝑗2𝜋𝑘𝑚
𝑘=0 𝐷𝐹𝑇{𝑥(𝑛 − 𝑚)} = 𝑋(𝑘)𝑒 𝑁

−𝑗2𝜋𝑘𝑚
𝐷𝐹𝑇 𝑥(𝑛 − 𝑚) = 𝑥(𝑛)𝑒 𝑁
𝑎𝑥1 𝑛 + 𝑏𝑥2 (𝑛) 𝑎𝑋1 𝑘 + 𝑏𝑋2 (𝑘)

www.iammanuprasad.com
 Q) Consider a finite length sequences x(n) shown in figure. The five point DF of x(n) is denoted by
X(k). Plot the sequences whose DFT is
𝑗2𝜋𝑘𝑚
−4𝜋𝑘 𝑥(𝑛) 𝐷𝐹𝑇 𝑥 𝑛 − 𝑚 = 𝑋 𝑘 𝑒− 𝑁
𝑌 𝑘 = 𝑒 5 𝑋(𝑘) 2 2 𝑁

1 1

-1 0 1 2 3
Solution

𝑗2𝜋𝑘2
𝐷𝐹𝑇 𝑥 𝑛 − 2 5
= 𝑋 𝑘 𝑒− 5 ,𝑛 = 0,1, … , 4

For n=0 ➔ 𝑦 0 = 𝑥 0−2 5

=𝑥 5+0−2 =𝑥 3 =1

For n=1 ➔ 𝑦 1 = 𝑥 1−2 5

= 𝑥 5+1−2 = 𝑥 4 = 0

For n=2 ➔ 𝑦 2 = 𝑥 2−2 5 =𝑥 5+2−2 =𝑥 5 =𝑥 5−5 =𝑥 0 =1 Exceeding the limit 0 ≤ 𝑛 ≤ 4

For n=3 ➔ 𝑦 3 = 𝑥 3−2 5

=𝑥 5+3−2 =𝑥 6 =𝑥 6−5 =𝑥 1 =2 𝑦(𝑛)
2 2
For n=4 ➔ 𝑦 4 = 𝑥 4−2 5
=𝑥 5+4−2 =𝑥 7 =𝑥 7−5 =𝑥 2 =2
1 1

𝑦 𝑛 = 1,0,1,2,2
-1 0 1 2 3 4
www.iammanuprasad.com
 Properties of Discrete Fourier Transform

Circular frequency shift

If X(k) is N-point DFT of a finite duration sequences x(n) then

Time reversal of the sequence

𝑗2𝜋𝑙𝑛
𝐷𝐹𝑇 𝑥 𝑛 𝑒 𝑁 =𝑋 𝑘−𝑙 𝑁
The time reversal of N-point sequence x(n) is attained by
wrapping the sequence x(n) around the circle in clockwise direction.
Proof
DFT 𝑁−1
𝑗2𝜋𝑘𝑛
𝑋 𝑘 = ෍ 𝑥 𝑛 𝑒− 𝑁 ,0 ≤ k ≤ N − 1
𝑛=0
𝑥 −𝑛 𝑁
= 𝐷𝐹𝑇 𝑥 𝑁 − 𝑛 =𝑋 𝑁−𝑘
Put k=k-l
𝑁−1
𝑗2𝜋(𝑘−𝑙)𝑛
−
𝑋 𝑘−𝑙 = ෍𝑥 𝑛 𝑒 𝑁
Take DFT on both sides
𝑛=0
𝑁−1
𝑗2𝜋𝑘𝑛 𝑗2𝜋𝑙𝑛
= ෍ 𝑥 𝑛 𝑛𝑒 − 𝑁 𝑒 𝑁
𝑗2𝜋𝑙𝑛
𝑛=0 𝑋 𝑘−𝑙 𝑁
= 𝐷𝐹𝑇 𝑥(𝑛)𝑒 𝑁

𝑗2𝜋𝑙𝑛
𝑥(𝑘 − 𝑙) = 𝑋 𝑘 𝑒 𝑁

www.iammanuprasad.com
 Properties of Discrete Fourier Transform

Complex conjugate property

∗ 𝑗2𝜋𝑛𝑁
𝑁−1
If X(k) is N-point DFT of a finite duration sequences x(n) then
𝑗2𝜋𝑘𝑛 𝑒− 𝑁 = 𝑒 −𝑗2𝜋𝑛 = 1
𝐷𝐹𝑇 𝑥 𝑛 = ෍𝑥 𝑛 𝑒 𝑁
𝑛=0

∗
∗ ∗ ∗ 𝑁−1
𝐷𝐹𝑇 𝑥 𝑛 =𝑋 𝑁−𝑘 =𝑋 −𝑘 𝑁
𝑗2𝜋𝑘𝑛
−
𝑗2𝜋𝑛𝑁
= ෍𝑥 𝑛 𝑒 𝑁 𝑒 𝑁
𝑛=0

∗
𝑁−1
Proof 𝑗2𝜋𝑛 𝑁−𝑘
= ෍ 𝑥 𝑛 𝑒− 𝑁

𝑁−1 𝑛=0
𝑗2𝜋𝑘𝑛
𝐷𝐹𝑇 𝑥 𝑛 = ෍𝑥 𝑛 𝑒− 𝑁
𝑛=0
∗
𝐷𝐹𝑇 𝑥 𝑛 = 𝑋 𝑁−𝑘
𝑁−1
𝑗2𝜋𝑘𝑛
∗ ∗ −
𝐷𝐹𝑇 𝑥 𝑛 = ෍𝑥 𝑛 𝑒 𝑁
𝑛=0

www.iammanuprasad.com
 Q) Let X(k) be a 14 point DFT of a length 14 real sequence x(n). The first 8 samples of X(k) are given by,
X(0) = 12,
X(1) = -1+3j ,
X(2) = 3+4j,
X(3) = 1-5j,
X(4) = -2+2j,
∗
𝐷𝐹𝑇 𝑥 𝑛 = 𝑋 𝑁−𝑘
X(5) = 6+3j,
X(6) = -2-3j,
X(7) = 10. Determine the remining samples

Solution
Given N=14
For n=8 ➔ 𝑋 8 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 8 = 𝑋 ∗ 6 = −2 + 3𝑗

For n=9 ➔ 𝑋 9 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 9 = 𝑋 ∗ 5 = 6 − 3𝑗

For n=10 ➔ 𝑋 10 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 10 = 𝑋 ∗ 4 = −2 − 2𝑗

For n=11 ➔ 𝑋 11 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 11 = 𝑋 ∗ 3 = 1 + 5𝑗

For n=12 ➔ 𝑋 12 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 12 = 𝑋 ∗ 2 = 3 − 4𝑗

For n=13 ➔ 𝑋 13 = 𝑋 ∗ 𝑁 − 𝑘 = 𝑋 ∗ 14 − 13 = 𝑋 ∗ 1 = −1 − 3𝑗
www.iammanuprasad.com
 Linear Convolution
Consider a discrete sequence x(n) of length L and impulse sequence h(n) of length M,
the equation for linear convolution is
3
x(k) 2
∞

𝑦 𝑛 = ෍ 𝑥 𝑘 ℎ 𝑛−𝑘 1 1
𝑘=−∞

-3 -2 -1 0 1 2 3
Where length of y(n) is L+M-1
h(k) 1 1 1
Let’s discuss it with an example

Q) Find the convolution of x(n) = {1,2,3,1}, h(n)={1,1,1,} -3 -2 -1 0 1 2 3

h(-k) 1 1 1
Solution
L = 4, M = 3 -3 -2 -1 0 1 2 3
∞

𝑦 𝑛 = ෍ 𝑥 𝑘 ℎ 𝑛−𝑘 Of length → 4+3-1 = 6

𝑘=−∞

For n=0 ➔ 𝑦 0 = ෍ 𝑥 𝑘 ℎ −𝑘 = 1.0 + 1.0 + 1.1 + 0.2 + 0.3 + 0.1 =1

𝑘=−∞

www.iammanuprasad.com
 ∞ ∞ 3
For n=1 ➔ 𝑦 1 = ෍ 𝑥 𝑘 ℎ 1 − 𝑘 = ෍ 𝑥 𝑘 ℎ −𝑘 + 1 x(k) 2
𝑘=−∞ 𝑘=−∞ 1
1

= 1.0 + 1.1 + 1.2 + 0.3 + 0.1 = 3

∞ ∞ 3 2 -1 0 1 2 3
h(k) 1 1 1
For n=2 ➔ 𝑦 2 = ෍ 𝑥 𝑘 ℎ 2 − 𝑘 = ෍ 𝑥 𝑘 ℎ −𝑘 + 2
𝑘=−∞ 𝑘=−∞
3 2 -1 0 1 2 3
= 1.1 + 1.2 + 1.3 + 0.1 = 6 h(-k) 1 1 1
∞ ∞

For n=3 ➔ 𝑦 3 = ෍ 𝑥 𝑘 ℎ 3 − 𝑘 = ෍ 𝑥 𝑘 ℎ −𝑘 + 3 3 2 -1 0 1 2 3
𝑘=−∞ 𝑘=−∞ h(-k+1) 1 1 1

= 0.1 + 1.2 + 1.3 + 1.1 = 6

∞ ∞
3 2 -1 0 1 2 3
h(-k+2) 1 1 1
For n=4 ➔ 𝑦 4 = ෍ 𝑥 𝑘 ℎ 4 − 𝑘 = ෍ 𝑥 𝑘 ℎ −𝑘 + 4
𝑘=−∞ 𝑘=−∞
3 2 -1 0 1 2 3
= 0.1 + 0.2 + 1.3 + 1.1 = 4 h(-k+3) 1 1 1

∞ ∞

For n=5 ➔ 𝑦 5 = ෍ 𝑥 𝑘 ℎ 5 − 𝑘 = ෍ 𝑥 𝑘 ℎ −𝑘 + 5 3 2 -1 0 1 2 3
𝑘=−∞ 𝑘=−∞ h(-k+4) 1 1 1

= 0.1 + 0.2 + 0.3 + 1.1 = 1

3 2 -1 0 1 21 3 1 1
h(-k+5)
𝑦 𝑛 = 1,3,6,6,4,1 www.iammanuprasad.com
3 2 -1 0 1 2 3
Q) Find the convolution of x(n) = {1,2,3,1}, h(n)={1,1,1,}

Solution

1 1 1
1 1 1 1
+ +
2 2 2 2
+ + 𝑦 𝑛 = 1,3,6,6,4,1
3 3 3 3
+
+
1 1 1 1

www.iammanuprasad.com
 Circular Convolution
Consider two discrete sequence x1(n) & x2(n) of length N with DFTs X1(k), X2(k)

Also
𝑁−1

𝑥3 𝑛 = ෍ 𝑥1 𝑚 𝑥2 𝑛 − 𝑚 𝑁 𝑥3 𝑛 = 𝑥1 𝑛 ⊙ 𝑥2 𝑛 𝐷𝐹𝑇 𝑥1 𝑛 ⊙ 𝑥2 𝑛 = 𝑋1 𝑘 . 𝑋2 𝑘
𝑚=0

Matrix method

Let’s discuss it with an example

Q) Find the circular convolution of x(n) = {1,2,3,4}, h(n)={1,-1,1,}

Solution
1 3 2 1 (1.1)+(4.-1)+(3.1)+(2.0) = 0
L = 4, M = 3
2 4 3 -1 (2.1)+(1.-1)+(4.1)+(3.0) = 5
Since lengths are not same we do zero-padding =
3 1 4 1 (3.1)+(2.-1)+(1.1)+(4.0) = 2
ℎ 𝑛 = 1, −1,1,0
4 2 1 0 (4.1)+(3.-1)+(2.1)+(2.0) = 3

𝑦 𝑛 = 0,5,2,3
www.iammanuprasad.com
 Circular Convolution

Concentric Circle method / Stockholm's Method

Let’s discuss it with an example

Q) Find the circular convolution of x(n) = {1,2,3,4}, h(n)={1,-1,1,} 1

Solution
L = 4, M = 3 1

Since lengths are not same we do zero-padding

ℎ 𝑛 = 1, −1,1,0
2 −1 4
0
For n=0 ➔ 𝑦 0 = 1.1 + 2.0 + 3.1 + (4. −1) =0

For n=1 ➔ 𝑦 1 = 1. −1 + 2.1 + 3.0 + (4.1) =5

For n=2 ➔ 𝑦 2 = 1.1 + 2. −1 + 3.1 + (4.0) =2 1

For n=3 ➔ 𝑦 3 = 1.0 + 2.1 + 3. −1 + (4.1) =3

3

𝑦 𝑛 = 0,5,2,3
www.iammanuprasad.com
 Linear convolution using circular convolution
Let there are two sequence x(n) with L and h(n) with length M. in linear convolution the length of output in L+M-1. In circular
convolution the length of the both input is L=M

Let’s discuss with an example

Q) Find the convolution of the sequences x(n) = {1,2,3,1}, h(n)={1,1,1,}

First we have to make the length of the x(n) and h(n) by adding zeros

𝑥 𝑛 = 1,2,3,1,0,0 (M-1 zeros)

ℎ 𝑛 = 1,1,1,0,0,0 (L-1 zeros)

1 0 1 3 2 1 (1.1)+(0.1)+(0.1)+(1.0) +(3.0) +(2.0) = 1

2 0 0 1 3 1 (2.1)+(1.1)+(0.1)+(0.0) +(1.0) +(3.0) = 3
3 1 0 0 1 1 (3.1)+(2.1)+(1.1)+(0.0) +(0.0) +(1.0) = 6
=
1 2 1 0 0 0 (1.1)+(3.1)+(2.1)+(1.0) +(0.0) +(0.0) = 6
0 3 2 1 0 0 (0.1)+(1.1)+(3.1)+(2.0) +(1.0) +(0.0) = 4
0 1 3 2 1 0 (0.1)+(0.1)+(1.1)+(3.0) +(2.0) +(1.0) = 1

𝑦 𝑛 = 1,3,6,6,4,1
www.iammanuprasad.com
 Filtering of long duration sequences
1) Overlap – save method

Let’s consider an input sequence x(n) of length Ls and response h(n)of length M, the steps to
follow overlap – save method is

Step 1 : input x(n) is divided into length L (L≥M)

Step 2 : Calculate the length N=L+M-1
Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from
previous segment, making each of length N
Step 4 : Make impulse response to length N by adding zeros
Step 5 ; Find the circular convolution of each new segments with new h(n)
Step 6 : Linearly combine each results and take sequence of length Ls+M-1 from that by discarding/removing first
M-1 points

www.iammanuprasad.com
 1) Overlap – save method
Q) Find the convolution of the sequences x(n) = {3,-1,0,1,3,2,0,1,2,1} and h(n) ={1,1,1}

Solution

Given , Ls = 10 & M=3 Lets guess the value of L =3 (𝐿 ≥ 𝑀)

Step 1 : input x(n) is divided into length L

𝑥1 𝑛 = 3, −1,0

𝑥2 𝑛 = 1,3,2
𝑥3 𝑛 = 0,1,2
𝑥4 𝑛 = 1,0,0

Step 2 : Calculate the length N=L+M-1

𝑁 =𝐿+𝑀−1 =3+3−1=5

www.iammanuprasad.com
1) Overlap – save method

Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from
previous segment, making each of length N

𝑥1 𝑛 = 0,0,3, −1,0
M-1 = 3-1 = 2
𝑥1 𝑛 = 3, −1,0
𝑥2 𝑛 = −1,0, 1,3,2 𝑥2 𝑛 = 1,3,2
𝑥3 𝑛 = 0,1,2
𝑥4 𝑛 = 1,0,0
𝑥3 𝑛 = 3,2,0,1,2

𝑥4 𝑛 = 1,2,1,0,0

Step 4 : Make impulse response to length N by adding zeros

ℎ 𝑛 = 1,1,1,0,0

www.iammanuprasad.com
 1) Overlap – save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

𝑦1 𝑛 = 𝑥1 𝑛 ⊙ ℎ(𝑛) = 0,0,3, −1,0 ⊙ 1,1,1,0,0 = −1,0,3,2,2 0 0 −1 3 0 1

0 0 0 −1 3 1
𝑦2 (𝑛) = 𝑥2 𝑛 ⊙ ℎ(𝑛) = −1,0, 1,3,2 ⊙ 1,1,1,0,0 = 4, 1, 0, 4, 6 3 0 0 0 −1 1
−1 3 0 0 0 0
𝑦3 (𝑛) = 𝑥3 𝑛 ⊙ ℎ(𝑛) = 3,2,0,1,2 ⊙ 1,1,1,0,0 = 6, 7, 5, 3, 3 0 −1 3 0 0 0
𝑦4 (𝑛) = 𝑥4 𝑛 ⊙ ℎ(𝑛) = 1,2,1,0,0 ⊙ 1,1,1,0,0 = 1, 3, 4, 3, 1

Step 6 : Linearly combine each results and take sequence of length Ls+M-1 from that by discarding/removing first M-1
points
M-1 = 3-1 = 2
Check whether length of y(n) is Ls+M-1 , if yes
discard the higher sequences
𝑦 𝑛 = {3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1}
Ls+M-1 = 10+3-1 = 12

www.iammanuprasad.com
 1) Overlap – save method
Q) Find the convolution of the sequences x(n) = {1,2,-1,2,3,-2,-3,-1,1,1,2,-1} and h(n) ={1,2} using overlap-save method

Solution

Given , Ls = 12 & M=2 Lets guess the value of L =3 (𝐿 ≥ 𝑀)

Step 1 : input x(n) is divided into length L

𝑥1 𝑛 = 1, 2, −1

𝑥2 𝑛 = 2,3, −2
𝑥3 𝑛 = −3, −1,1
𝑥4 𝑛 = 1,2, −1

Step 2 : Calculate the length N=L+M-1

𝑁 =𝐿+𝑀−1 =3+2−1=4

www.iammanuprasad.com
1) Overlap – save method

Step 3 : Add M-1 zeros to the start to first segment, each segment (length = L) has its first M-1 points coming from
previous segment, making each of length N

𝑥1 𝑛 = 0,1,2, −1
M-1 = 2-1 = 1
𝑥1 𝑛 = 1, 2, −1

𝑥2 𝑛 = −1,2,3, −2 𝑥2 𝑛 = 2,3, −2
𝑥3 𝑛 = −3, −1,1
𝑥4 𝑛 = 1,2, −1
𝑥3 𝑛 = −2, −3, −1,1

𝑥4 𝑛 = 1, 1, 2, −1

𝑥5 𝑛 = −1, 0,0,0

Step 4 : Make impulse response to length N by adding zeros

ℎ 𝑛 = 1, 2 , 0 , 0
www.iammanuprasad.com
 1) Overlap – save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

𝑦1 𝑛 = 𝑥1 𝑛 ⊙ ℎ(𝑛) = 0,1,2, −1 ⊙ 1,2, 0,0 = −2, 1, 4, 3 0 −1 2 1 1

1 0 −1 2 2
𝑦2 (𝑛) = 𝑥2 𝑛 ⊙ ℎ(𝑛) = −1,2,3, −2 ⊙ 1,2,0,0 = −5, 0, 7, 4 2 1 0 −1 0
−1 2 1 0 0
𝑦3 (𝑛) = 𝑥3 𝑛 ⊙ ℎ(𝑛) = −2, −3, −1,1 ⊙ 1,2, 0,0 = 0, −7, −7, −1
𝑦4 (𝑛) = 𝑥4 𝑛 ⊙ ℎ(𝑛) = 1, 1, 2, −1 ⊙ 1,2,0,0 = −1, 3, 4, 3
𝑦5 (𝑛) = 𝑥5 𝑛 ⊙ ℎ(𝑛) = −1, 0,0,0 ⊙ 1,2,0,0 = −1, −2, 0, 0

Step 6 : Linearly combine each results and take sequence of length Ls+M-1 from that by discarding/removing first M-1
points
Check whether length of y(n) is Ls+M-1 , if yes
𝑦 𝑛 = {1,4,3,0,7,4, −7, −7, −1,3,4,3, −2,0,0} discard the higher sequences

Ls+M-1 = 12+2-1 = 13
𝑦 𝑛 = {1,4,3,0,7,4, −7, −7, −1,3,4,3, −2}
www.iammanuprasad.com
 Filtering of long duration sequences
2) Overlap – add method

Let’s consider an input sequence x(n) of length L1 and response h(n) of length M, the steps to
follow overlap – save method is

Step 1 : input x(n) is divided into length L (L≥M)

Step 2 : Calculate the length N=L+M-1
Step 3 : Add M-1 zeros on each segment (length = L) of x(n)
Step 4 : Make impulse response to length N by adding zeros
Step 5 ; Find the circular convolution of each new segments with new h(n)
Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L1+M-1

www.iammanuprasad.com
 1) Overlap – add method
Q) Find the convolution of the sequences x(n) = {3,-1,0,1,3,2,0,1,2,1} and h(n) ={1,1,1}

Solution

Given , L1 = 10 & M=3 Lets guess the value of L =3 (𝐿 ≤ 𝑀)

Step 1: input x(n) is divided into length L (L≥M)

𝑥1 𝑛 = 3, −1,0

𝑥2 𝑛 = 1,3,2
𝑥3 𝑛 = 0,1,2
𝑥4 𝑛 = 1,0,0

Step 2 : Calculate the length N=L+M-1

𝑁 =𝐿+𝑀−1 =3+3−1=5

www.iammanuprasad.com
1) Overlap – add method

Step 3 : Add M-1 zeros on each segment (length = L) of x(n)

𝑥1 𝑛 = 3, −1, 0, 0, 0 M-1 = 3-1 = 2

𝑥1 𝑛 = 3, −1,0
𝑥2 𝑛 = 1, 3, 2, 0, 0
𝑥2 𝑛 = 1,3,2
𝑥3 𝑛 = 0, 1, 2, 0, 0 𝑥3 𝑛 = 0,1,2
𝑥4 𝑛 = 1,0,0
𝑥4 𝑛 = 1, 0, 0, 0, 0

Step 4 : Make impulse response to length N by adding zeros

ℎ 𝑛 = 1,1,1,0,0

www.iammanuprasad.com
 1) Overlap – add method

Step 5 ; Find the circular convolution of each new segments with new h(n)

𝑦1 𝑛 = 𝑥1 𝑛 ⊙ ℎ(𝑛) = 3, −1, 0, 0, 0, ⊙ 1,1,1,0,0 = 3,2,2, −1,0 3 0 0 0 −1 1

−1 3 0 0 0 1
𝑦2 (𝑛) = 𝑥2 𝑛 ⊙ ℎ(𝑛) = 1, 3, 2, 0, 0 ⊙ 1,1,1,0,0 = 1,4,6,5,2 0 −1 3 0 0 1
0 0 −1 3 0 0
𝑦3 (𝑛) = 𝑥3 𝑛 ⊙ ℎ(𝑛) = 0, 1, 2, 0, 0 ⊙ 1,1,1,0,0 = 0,1,3,3,2 0 0 0 −1 3 0
𝑦4 (𝑛) = 𝑥4 𝑛 ⊙ ℎ(𝑛) = 1, 0, 0, 0, 0 ⊙ 1,1,1,0,0 = 1,1,1,0,0

Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L1+M-1

3, 2, 2, −1, 0
Check whether length of y(n) is L1+M-1 , if yes
1, 4, 6, 5, 2 discard the higher sequences

0,1, 3, 3, 2 L1+M-1 = 10+3-1 = 12

1, 1, 1, 0, 0
𝑦 𝑛 = {3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1}
{3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1, 0,0}
www.iammanuprasad.com
 1) Overlap – add method
Q) Find the convolution of the sequences x(n) = {1,2,-1,2,3,-2,-3,-1,1,1,2,-1} and h(n) ={1,2} using overlap-add method

Solution

Given , Ls = 12 & M=2 Lets guess the value of L =3 (𝐿 ≥ 𝑀)

Step 1 : input x(n) is divided into length L

𝑥1 𝑛 = 1, 2, −1

𝑥2 𝑛 = 2,3, −2
𝑥3 𝑛 = −3, −1,1
𝑥4 𝑛 = 1,2, −1

Step 2 : Calculate the length N=L+M-1

𝑁 =𝐿+𝑀−1 =3+2−1=4

www.iammanuprasad.com
 1) Overlap – save method

Step 3 : Add M-1 zeros on each segment (length = L) of x(n)

𝑥1 𝑛 = 1, 2, −1, 0 M-1 = 2-1 = 1

𝑥2 𝑛 = 2,3, −2,0 𝑥1 𝑛 = 1, 2, −1

𝑥3 𝑛 = −3, −1,1,0 𝑥2 𝑛 = 2,3, −2

𝑥4 𝑛 = 1, 2, −1,0 𝑥3 𝑛 = −3, −1,1

𝑥4 𝑛 = 1,2, −1

Step 4 : Make impulse response to length N by adding zeros

ℎ 𝑛 = 1, 2 , 0 , 0

www.iammanuprasad.com
 1) Overlap – save method

Step 5 ; Find the circular convolution of each new segments with new h(n)

𝑦1 𝑛 = 𝑥1 𝑛 ⊙ ℎ(𝑛) = 1,2, −1,0 ⊙ 1,2, 0,0 = 1, 4, 3,2 1 0 −1 2 1

2 1 0 −1 2
𝑦2 (𝑛) = 𝑥2 𝑛 ⊙ ℎ(𝑛) = 2,3, −2,0 ⊙ 1,2,0,0 = 2,7, 4, −4 −1 2 1 0 0
0 −1 2 1 0
𝑦3 (𝑛) = 𝑥3 𝑛 ⊙ ℎ(𝑛) = −3, −1,1,0 ⊙ 1,2, 0,0 = −3, −7, −1,2
𝑦4 (𝑛) = 𝑥4 𝑛 ⊙ ℎ(𝑛) = 1, 2, −1,0 ⊙ 1,2,0,0 = 1, 4 , 3, −2

Step 6 : Add last and first M-1 points of each segments, discard/remove excess point than L1+M-1
1, 4, 3, 2
Check whether length of y(n) is Ls+M-1 , if yes
−2, 7, 4, −4 discard the higher sequences
−3, −7, −1, 2 Ls+M-1 = 12+2-1 = 13
1, 4, 3, −2
𝑦 𝑛 = {1,4,3,0,7,4, −7, −7, −1,3,4,3, −2}
{1, 4, 3, 0, 7, 4, −7, −7, −1, 3, 4, 3, −2, }

www.iammanuprasad.com