Lecture 3 1
Linear filtering based on the DFT
Advanced Digital Signal Processing
Dr Dennis Deng
Department of Electronic Engineering, La Trobe University
1998,1999
Contents 2
• Linear filter and circular convolution
• Overlap and save method
• Overlap and add method
• Self test exercises
Linear Filtering 3
• A sequence x(n) of length L filtered by an FIR
filter h(n) of length M
M 1
y( n ) 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 y(1)=0 y(2)=0 y(3)=1
x(n)
1 1 1 1 1 1 1 1 1 1 1 1
h(n) 1 -1 1 -1 1 -1 1 -1
Linear Filtering 4
• In the frequency domain
Y ( ) H ( ) X ( )
2
• Sampling both side by an interval N
,N L M 1
• The kth sample is given by
2 2 2
Y( 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.
Linear Filtering 5
• 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
Linear Filtering 6
x(n) 1 1 1 0
h(n) -1 1 0 0 -1 0 0 1
1 -1 0 0 0 1 -1 0 0 0 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 7
• 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
Linear Filtering 8
• The following example shows a 3-point circular
convolution
x(n) 1 1 1
h(n) -1 1 0 -1 0 1 y(0)=0
1 -1 0 0 1 -1
y(1)=0 y(2)-0
Linear Filtering 9
• The following example shows a 5-point circular
convolution
x(n) 1 1 1 0 0
h(n) -1 1 0 0 0 -1 0 0 0 1 y(0)=-1
1 -1 0 0 0 0 1 -1 0 0 0 0 1 -1 0
y(1)=0 y(2)=0 y(3)=1
• These examples show that when N L M 1
circular convolution is the same as linear
convolution
Overlap-save method 10
• 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.
Overlap-save method 11
• The method is shown in the following diagram
signal
L L L
M-1 zeor
save last M-1 sample
output
discard
M-1 samples
Overlap-save method 12
• 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.
Overlap-save method 13
• 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
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) 0 1 2 2 1
h(n) -1 1 0 0 0 -1 0 0 0 1 y(0)=-1 (circular conv.)
1 -1 0 0 0 0 1 -1 0 0 0 0 1 -1 0
y(1)=-1 y(2)=-1 y(3)=0
(linear conv.) (linear conv.) (linear conv.)
Overlap-add method 15
• This method is shown in the following diagram
signal
L L L
M-1 zero
M-1 zero
M-1 zero
step 1
output
step 2
step 3
add
M-1 samples
Overlap-add method 16
• 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
Summary 17
• 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.
Self test exercises 18
• 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
