M Muthumari, Asst Prof, ECE Dept 02/03/2023

DISCRETE TIME
SIGNAL
PROCESSING -
1151EC112
Ms M Muthu mari
Asst Prof, Dept of ECE

1
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

FILTERING USING DFT:

1. In practical application we often come across linear filtering of long

data sequences.
2. DFT involves operation on block of data.
3. The block size of data should minimum because digital processors
have limited memory.
4. Two methods of filtering:
 OVERLAP SAVE METHOD
 OVERLAP ADD METHOD

2
M Muthumari, Asst Prof, ECE Dept 02/03/2023

3
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE METHOD

STEP-1:
Determine length ‘M’, which is the length of the impulse
response data sequences i.e. h[n] & determine ‘M-1’.

STEP-2:
Given input sequence x[n] size of DFT is
‘N’. let assume, N=5
STEP-3:
Determine the length of the new data, ‘L’
=> N=(L+M-1)

STEP-4:
Pad ‘L-1’ zeros to h[n]
h[n] ‘L-1’ zeros (padded)
4
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE METHOD

STEP-3:
Determine the length of the blocks, ‘L’

L L L L

Input Data Sequence x[n]

M-1 zeros x1[n]

M-1 data x2[n]

M-1 data x3[n]

M-1 data x4[n]

 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE METHOD

STEP-5:
Perform Circular Convolution of h[n] & blocks of x[n]
i.e. y1[n]= x1[n] N h[n]
y2[n]= x2[n] N h[n]
y3[n]= x3[n] N h[n]
y4[n]= x4[n] N h[n]

6
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE METHOD

X=> discard
M-1 data y1[n]
X

M-1 data y2[n]

X

M-1 data y3[n]

X

M-1 data
y4[n]
X

Final Output Data Sequence y[n]

7
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE EXAMPLE

Ques. Given x[n]={3,-1,0,1,3,2,0,1,2,1}& h[n]={1,1,1}
 Let, N=5  N=(L+M-1)
Length of h[n], M= 3  5=L+3-1
Therefore, M-1= 2 We know,  L=3 (length of x(n))
∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,1,1,0,0}
Pad M-1 =2 no. of previous data with x(n)

n -2 -1 0 1 2 3 4 5 6 7 8 9 10 11
X(n) 3 -1 0 1 3 2 0 1 2 1

X1(n) 0 0 3 -1 0

X2(n) -1 0 1 3 2

X3(n) 3 2 0 1 2

X4(n) 1 2 1 0 0
8
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE EXAMPLE

Performing yk[n]= xk[n] N h[n], where k=1,2,3,4
y1[n]= {-1,0,3,2,2} y3[n]={6,7,5,3,3}
y2[n]= {4,1,0,4,6} y4[n]={1,3,4,3,1}
n -2 -1 0 1 2 3 4 5 6 7 8 9 10 11

y1(n) -1 0 3 2 2
X=> discard
y2(n) 4 1 0 4 6
X=> discard

y3(n) 6 7 5 3 3
X=> discard

y4(n) 1 3 4 3 1
X=> discard

y(n) 3 2 2 0 4 6 5 3 3 4 3 1

Output Y(n)={ 3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1 }
9
M Muthumari, Asst Prof, ECE Dept 02/03/2023

10
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD METHOD

STEP-1:
Determine length ‘M’, which is the length of the impulse
response data sequences i.e. h[n] & determine ‘M-1’.
STEP-2:
Given input sequence x[n] size of DFT is
‘N’. let assume, N=5
STEP-3:
Determine the length of the new data, ‘L’
STEP-4:
Pad ‘M-1’ zeros to xk[n]
Pad ‘L-1’ zeros to
h[n] xk[n] ‘M-1’ zeros (padded)

h[n] ‘L-1’ zeros (padded) 11

 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD METHOD

L L L L

Input Data Sequence x[n]

x1[n] M-1 zeros

x2[n] M-1 zeros

x3[n] M-1 zeros

x4[n] M-1 zeros

12
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD METHOD

STEP-5:
Perform Circular Convolution of h[n] & blocks of x[n]
i.e. y1[n]= x1[n] N h[n]
y2[n]= x2[n] N h[n]
y3[n]= x3[n] N h[n]
y4[n]= x4[n] N h[n]

13
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD METHOD

y1[n] M-1 data

add

y2[n] M-1 data

add

y3[n] M-1 data

add

y4[n] M-1 data

Final Output Data Sequence y[n]

14
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD EXAMPLE

Ques. Given x[n]={3,-1,0,1,3,2,0,1,2,1} & h[n]={1,1,1}
 Let, N=5  N=(L+M-1)
Length of h[n], M= 3  5=L+3-1
Therefore, M-1= 2  L=3 (length of x(n))
∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,1,1,0,0}

∴Pad M-1=2 zeros with all x[n]

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13
X(n) 3 -1 0 1 3 2 0 1 2 1

X1(n) 3 -1 0 0 0

X2(n) 1 3 2 0 0

X3(n) 0 1 2 0 0

X4(n) 1 0 0 0 0
15
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD EXAMPLE

Performing yk[n]= xk[n] N h[n], where k=1,2,3,4
y1[n]= {3,2,2,-1,0} y3[n]={0,1,3,3,2}
- Add the over lapping
y2[n]= {1,4,6,5,2} y4[n]={1,1,1,0,0} values

n 0 1 2 3 4 5 6 7 8 9 10 11 12 13

y1(n) 3 2 2 -1 0

y2(n) 1 4 6 5 2

y3(n) 0 1 3 3 2

y4(n) 1 1 1 0 0

y(n) 3 2 2 0 4 6 5 3 3 4 3 1 0 0

Output Y(n)={ 3, 2, 2, 0, 4, 6, 5, 3, 3, 4, 3, 1 }
16
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE VS ADD METHOD

Overlap Save Overlap Add

 Overlapped values has to be  Overlapped values has to be
discarded. added.
 It does not require any addition.  It will involve adding a number
of values in the output.
 Linear convolution is not
 It can be computed using linear
applicable here.
convolution

 Overlap Add and Save methods are almost similar.

 From the differences one can choose any of the
methods, which is suitable at that time.
17
 M Muthumari, Asst Prof, ECE Dept 02/03/2023
Find the output y(n) of the filter whose impulse
response h(n) = {1, 2} and input signal x(n) = {1, 2, -1, 2,
3, -2, -3, -1, 1, 1, 2, -1} using (i) overlap add method
and (ii) overlap save method
Soln:
Given : x(n) = {1, 2, -1, 2, 3, -2, -3, -1, 1, 1, 2, -1}
h(n) ={ 1, 2}
Let, N=4  N=(L+M-1)
Length of h[n], M= 2  4=L+2-1
Therefore, M-1= 1  L=3 (Length of x(n))

∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,2,0,0}

18
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP SAVE METHOD

Pad M-1 =1 no. of previous data with x(n)

X1(n) ={ 0, 1, 2, -1} pad M-1 zeros before x(n)

X2(n) ={ -1, 2, 3, -2}
X3(n)={ -2, -3, -1, 1} pad M-1 data from previous x(n)
X4(n) ={1, 1, 2, -1}
X5(n) ={ -1,0,0,0}

n -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
X(n) 1 2 -1 2 3 -2 -3 -1 1 1 2 -1
X1(n) 0 1 2 -1
X2(n) -1 2 3 -2
X3(n) -2 -3 -1 1
X4(n) 1 1 2 -1
X5(n) -1 0 0 0

19
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

X=> discard
Performing yk[n]= xk[n] N h[n], where k=1,2,3,4,5
y1[n]= {-2,1,4,3} y3[n]={0,-7,-7,-1}
y2[n]= {-5,0,7,4} y4[n]={-1,3,4,3} y5[n]= { -1,-2,0,0 }
n -1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
y1(n) -2 1 4 3
x
y2(n) -5 0 7 4
X
y3(n) 0 -7 -7 -1
X
y4(n) -1 3 4 3
X
y5(n) -1 -2 0 0
X
y(n) 1 4 3 0 7 4 -7 -7 -1 3 4 3 -2 0 0

Output Y(n)={ 1,4,3,0,7,4,-7,-7,-1,3,4,3,-2}

20
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

OVERLAP ADD METHOD

Pad M-1 =1 zeros with x(n)
x(n) = {1, 2, -1, 2, 3, -2, -3, -1, 1, 1, 2, -1} L=3

X1(n) ={ 1, 2, -1, 0} pad M-1 zeros before x(n)

X2(n) ={2, 3, -2, 0}
X3(n)={-3, -1, 1, 0}
X4(n) ={1, 2, -1, 0}
∴Pad L-1=2 zeros with h[n] i.e. h[n]={1,2,0,0}

n 0 1 2 3 4 5 6 7 8 9 10 11 12
X(n) 1 2 -1 2 3 -2 -3 -1 1 1 2 -1

X1(n) 1 2 -1 0
X2(n) 2 3 -2 0
X3(n) -3 -1 1 0
X4(n) 1 2 -1 0

21
 M Muthumari, Asst Prof, ECE Dept 02/03/2023

Performing yk[n]= xk[n] N h[n], where k=1,2,3,4,5

y1[n]= {1,4,3,-2} y3[n]={-3,-7,-1,2}
y2[n]= {2,7,4,-4} y4[n]={1,4,3,-2} - Add the over lapping
values
n 0 1 2 3 4 5 6 7 8 9 10 11 12
y1(n) 1 4 3 -2
y2(n) 2 7 4 -4
y3(n) -3 -7 -1 2
y4(n) 1 4 3 -2

y(n) 1 4 3 0 7 4 -7 -7 -1 3 4 3 -2

Output Y(n)={ 1,4,3,0,7,4,-7,-7,-1,3,4,3,-2}

22