Transcript DFT-app1 - Graz University of Technology

Lecture 3
Linear filtering based on the DFT
Advanced Digital Signal Processing
Dr Dennis Deng
Department of Electronic Engineering, La Trobe University
1998,1999
1
Contents
•
•
•
•
Linear filter and circular convolution
Overlap and save method
Overlap and add method
Self test exercises
2
Linear Filtering
3
• A sequence x(n) of length L filtered by an FIR
filter h(n) of length M
y( n ) 
M 1

h( n ) x( n  k )
k 0
• The length of y(n) is L+M-1
• Example x(n) =[1 1 1] , h(n) =[-1 1]
y (0 )= -1
x (n )
h (n )1
1
-1
1
1
y (1 )= 0
1
1
1
-1
1
y (2 )= 0
1
1
1
1
-1
y (3 )= 1
1
1
1
1
-1
Linear Filtering
• In the frequency domain
Y( )  H ( ) X ( )
• Sampling both side by an interval
• The kth sample is given by
Y(
2
,N  L  M 1
N
2
2
2
k )  H( k ) X ( k )
N
N
N
• Using the DFT notation Y( k )  H ( k ) X ( k )
X(k) and H(k) are the DFT (with zero padding) of
x(n) and h(n), respectively.
4
Linear Filtering
• Performing the inverse DFT y( n)  IDFT (Y( k ))
• Is y( n) the same as y(n) ? YES. Because Y( ) is
the Fourier transform of y(n), to recover y(n), an
N-point sampling of Y( ) and an N-point IDFT is
necessary.
• An equivalent question is under what condition
circular convolution becomes linear convolution ?
• A 4-point circular convolution of the previous
example in the following slide
5
Linear Filtering
x (n )
h (n ) -1
1
1
1
1
0
1
0
0
-1
0
0
1
-1
0
0
0
1
-1
0
0
0
6
1
-1
• This example shows that by zero padding such
that the length of the circular convolution is
greater than or equal to L+M-1, circular
convolution is the same as linear convolution.
Linear Filtering
• The multiplication in DFT domain corresponds to
circular convolution in the time domain.
• By zero padding the two sequences, circular
convolution becomes linear convolution
• To perform linear convolution using the DFT
(1) zero padding x(n) and h(n) such that the
length of them is N=L+M-1
(2) Calculate an N-point DFT for both sequences
and multiply them point-by-point
(3) perform an N-point inverse DFT
7
Linear Filtering
• The following example shows a 3-point circular
convolution
x (n )
h (n )
1
-1
-1
1
1
0
y (1 )= 0
0
0
1
1
-1
0
1
-1
y (2 )-0
1
y (0 )= 0
8
Linear Filtering
9
• The following example shows a 5-point circular
convolution
x (n )
h (n ) -1
1
1
1
1
0
0
1
0
0
0
-1
0
0
0
1
-1
0
0
0
0
1
-1
0
0
y (1 )= 0
y (2 )= 0
y (0 )= -1
0
0
1
-1
0
y (3 )= 1
• These examples show that when N  L  M  1
circular convolution is the same as linear
convolution
Overlap-save method
• When the DFT is used to implement linear
filtering, a signal is processed in blocks. Due to
the real-time requirement (low delay) and the
limitation of physical memory, the size of the
block can not be arbitrarily large.
• The length of the FIR filter is M and the length of
on block of data is L (L>M)
• Each time a block of data of length L+M-1 is
filtered by using the DFT method.
10
Overlap-save method
• The method is shown in the following diagram
s ig n a l
L
L
L
M -1 z e o r
s a v e l a s t M -1 s a m p l e
o u tp u t
d is ca rd
M -1 s a m p l e s
11
Overlap-save method
• Each step consists:
(1) calculating N-point DFT of x(n) and multiply
it with the N-point DFT of h(n).
(2) calculating N-point IDFT and discarding the
first M-1 output sample. The last L samples
are the desired filter output
(3) append the last M-1 samples to the beginning
of the new block of signal
(4) goto (1) until reach the end of the signal.
12
Overlap-save method
• The reason for discarding the first M-1 output
samples is that they are the result of circular
convolution. Linear convolution starts at the Mth
sample.
• For the same reason, the last M-1 samples of the
processed block should be appended to the
beginning of the new block
13
Overlap-save method
14
• This is can be easily seen from a simple example:
x(n)=[1 2 2 1]; h(n)=[1 -1]. (L=4, M=2). A 6-point
circular convolution (x(n) represents a block of
data)
x (n )
h (n ) -1
1
0
1
2
2
1
1
0
0
0
-1
0
0
0
1
-1
0
0
0
0
1
-1
0
0
y (1 )= -1
(l i n e a r c o n v . )
y (2 )= -1
(l i n e a r c o n v . )
y (0 )= -1 (c i r c u l a r c o n v . )
0
0
1
-1
0
y (3 )= 0
(l i n e a r c o n v . )
Overlap-add method
15
• This method is shown in the following diagram
s ig n a l
L
L
L
M -1 z e r o
M -1 z e r o
M -1 z e r o
s te p 1
o u tp u t
s te p 2
s te p 3
add
M -1 s a m p l e s
Overlap-add method
• In each step:
(1) perform the L+M-1 point DFT, multiplication
and IDFT
(2) the last M-1 samples of the previous output is
added to the first M-1 samples of the current
output
16
Summary
• The DFT can be used to implement linear filtering
• A key point is to choose the N-point DFT such
that circular convolution is the same as linear
convolution
• The overlap-save and overlap-add methods can be
used in real time signal processing.
17
Self test exercises
• For a signal x(n)=[1 2 3 2 1] and a filter h(n)=[1 -2 1],
(1) Calculate its circular convolution.
(2) Verify your result by using Matlab
(hint: real(ifft(fft(x).*fft(h,6))))
(3) Calculate its N-point (N=8,9,10,128) circular
convolution. Which one is the same as linear
convolution
• For a signal x(n)=[1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4]
and a filter h(n)=[1 2 1], calculate the filter output using
(1) Overlap-save
(2) Overlap-add
18