PRACTICAL MATLAB® FOR ENGINEERS PRACTICAL MATLAB

DTFT, DFT, ZT, and FFT 497

Observe that if each segment fi (m), for i = 1, 2, 3, ..., is of length M, then each convo-

lution [h(n) ⊗ fi (m)] returns a sequence of length N + M − 1. Therefore, the fi rst con-

volution [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:

gn

fm hn n N

f m hn f m hn N n N M

()

() ()

() () () ()



1

12

1

12

⊗

⊗⊗

for

for

 11









Note that the convolution points 2N + 1 ≤ n ≤ 2 N + 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 convolu-

tions. 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 convo-

lution 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 speci-

fi 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 convo-

lutions is illustrated as follows:

The linear convolution analysis for gL(n) = f(n) ⊗ h(n) and its corresponding

eight points are as follows:

gL(0) = f(0)h(0)

gL(1) = f(1)h(0) + h(1)f(0)

gL(2) = f(0)h(2) + f(1)h(1) + f(2)h(0)

gL(3) = f(0)h(3) + f(1)h(2) + f(2)h(1) + f(3)h(0)

gL(4) = f(1)h(3) + f(2)h(2) + f(3)h(1) + f(4)h(0)

gL(5) = f(2)h(3) + f(3)h(2) + f(4)h(1)

gL(6) = f(3)h(3) + f(2)h(4)

gL(7) = f(4)h(3)