DTFT, DFT, ZT, and FFT
497
Observe that if each segment fi (m), for i = 1, 2, 3, …, is of length M, then each convolution [h(n) ⊗ fi (m)] returns a sequence of length N + M − 1. Therefore, the fi rst convolution [f 1 (n) ⊗ h(n)] returns the fi rst N points of g(n) and the remaining M − 1 points
are added to the next convolution [h(n) ⊗ f 2 (m)]. This procedure is repeated until all
the short convolutions are added to obtain the fi nal convolution resulting in g(n).
The building up of the sequence g(n) for the fi rst two segments of f(n)[f 1 (m) +
f 2 (m)] are analyzed as follows:
g n
f m
h n
n N
f m
h n
f m
h n
N
n
N M
( )
( )
( )
( )
( )
( )
( )
ϭ
ϩ
ϩ
Ϫ
1
1
2
1
1
2
⊗
⊗
⊗
for
for
Յ Յ
Յ Յ
ϩ
1 1
Note that the convolution points 2N + 1 ≤ n ≤ 2N + M − 1 are added to the
convolution of [ f 3 (m) ⊗ h(n)] and so on.
R.5.114 Note that the overlap-add method is based on the summations of linear convolutions. The overlap-save method is based on circular convolutions and consists of
segmenting f(n) into overlapping blocks of f(n) and performing the circular convolution of the segments and keeping only the terms that correspond to the linear
portion of the convolution and discarding all the other terms.
R.5.115 The MATLAB function gn = fftfi lt(hn, fn) or gn = fftfi lt(hn, fn, seg) returns gn that
represents the output sequence g(n), as a result of performing the conv(hn, fn),
where hn is the system impulse response h(n) and fn is the system input sequence
f(n) segmented into successive sections of length of 512 samples, when not specifi ed, or by defi ning the segmentation length by seg.
Note that the term fi lt stands for a rectangular window or fi lter that is used to
limit the range of the convolutions involved.
R.5.116 A comparison between the linear and circular convolutions is useful to provide an
insight of the overlap-save method.
Consider the following example: Assume that f(n) is of length 5 and h(n) of
length 4. Then the evaluation of the coeffi cients of the linear and circular convolutions is illustrated as follows:
The linear convolution analysis for g L (n) = f(n) ⊗ h(n) and its corresponding
eight points are as follows:
g L (0) = f(0)h(0)
g L (1) = f(1)h(0) + h(1)f(0)
g L (2) = f(0)h(2) + f(1)h(1) + f(2)h(0)
g L (3) = f(0)h(3) + f(1)h(2) + f(2)h(1) + f(3)h(0)
g L (4) = f(1)h(3) + f(2)h(2) + f(3)h(1) + f(4)h(0)
g L (5) = f(2)h(3) + f(3)h(2) + f(4)h(1)
g L (6) = f(3)h(3) + f(2)h(4)
g L (7) = f(4)h(3)
CRC_47760_CH005.indd 497
CRC_47760_CH005.indd 497
7/23/2008 1:47:28 PM
7/23/2008 1:47:28 PM
497
Observe that if each segment fi (m), for i = 1, 2, 3, …, is of length M, then each convolution [h(n) ⊗ fi (m)] returns a sequence of length N + M − 1. Therefore, the fi rst convolution [f 1 (n) ⊗ h(n)] returns the fi rst N points of g(n) and the remaining M − 1 points
are added to the next convolution [h(n) ⊗ f 2 (m)]. This procedure is repeated until all
the short convolutions are added to obtain the fi nal convolution resulting in g(n).
The building up of the sequence g(n) for the fi rst two segments of f(n)[f 1 (m) +
f 2 (m)] are analyzed as follows:
g n
f m
h n
n N
f m
h n
f m
h n
N
n
N M
( )
( )
( )
( )
( )
( )
( )
ϭ
ϩ
ϩ
Ϫ
1
1
2
1
1
2
⊗
⊗
⊗
for
for
Յ Յ
Յ Յ
ϩ
1 1
Note that the convolution points 2N + 1 ≤ n ≤ 2N + M − 1 are added to the
convolution of [ f 3 (m) ⊗ h(n)] and so on.
R.5.114 Note that the overlap-add method is based on the summations of linear convolutions. The overlap-save method is based on circular convolutions and consists of
segmenting f(n) into overlapping blocks of f(n) and performing the circular convolution of the segments and keeping only the terms that correspond to the linear
portion of the convolution and discarding all the other terms.
R.5.115 The MATLAB function gn = fftfi lt(hn, fn) or gn = fftfi lt(hn, fn, seg) returns gn that
represents the output sequence g(n), as a result of performing the conv(hn, fn),
where hn is the system impulse response h(n) and fn is the system input sequence
f(n) segmented into successive sections of length of 512 samples, when not specifi ed, or by defi ning the segmentation length by seg.
Note that the term fi lt stands for a rectangular window or fi lter that is used to
limit the range of the convolutions involved.
R.5.116 A comparison between the linear and circular convolutions is useful to provide an
insight of the overlap-save method.
Consider the following example: Assume that f(n) is of length 5 and h(n) of
length 4. Then the evaluation of the coeffi cients of the linear and circular convolutions is illustrated as follows:
The linear convolution analysis for g L (n) = f(n) ⊗ h(n) and its corresponding
eight points are as follows:
g L (0) = f(0)h(0)
g L (1) = f(1)h(0) + h(1)f(0)
g L (2) = f(0)h(2) + f(1)h(1) + f(2)h(0)
g L (3) = f(0)h(3) + f(1)h(2) + f(2)h(1) + f(3)h(0)
g L (4) = f(1)h(3) + f(2)h(2) + f(3)h(1) + f(4)h(0)
g L (5) = f(2)h(3) + f(3)h(2) + f(4)h(1)
g L (6) = f(3)h(3) + f(2)h(4)
g L (7) = f(4)h(3)
CRC_47760_CH005.indd 497
CRC_47760_CH005.indd 497
7/23/2008 1:47:28 PM
7/23/2008 1:47:28 PM