The DFT - Synthesis Lectures on Signal Processing - page 137

SR = 1000; ts = chirp( [0:1/(SR-1):1],0,1,SR/2);
s = [1,1,1,1]; lincon = conv(s, ts);
linconbyfft = real(ifft( fft(ts, 1024).*fft(s,1024)));
figure(14); subplot(2,1,1); plot(lincon);
subplot(2,1,2); plot(linconbyfft(1:1003))

Note that the linear convolution has a length equal to 1000+4-1=1003, and thus we take the
leftmost 1003 samples of the convolution-via-fft as the linear convolution.
If one of the sequences is of indefinite length (such as a sample stream from a real-time process),
an approach is to size the DFTs according to the length N of the impulse response (the shorter sequence)
and to break the longer sequence into shorter subsequences of length P , each of which is convolved
with the impulse response, and the partial responses overlapped with the proper offset and added. The
subsequence length P might also equal N , but it could be longer as well. Either way, the impulse response
and the subsequence are padded with zeros to a length at least equal to the sum of their lengths less one,
and then up to the next power of two.
As an example, we'll use an impulse response of length N as one period of an N -periodic sequence,
and divide the signal sequence into subsequences, each of length N .
The following procedure is known as the Overlap and Add Method :

• 1) Pad the impulse response with another N zeros to make a sequence of 2 N .If2 N is not a power
of 2, pad with additional zeros until a power of 2 length is reached (call the final padded length
M ).

• 2) Take the first N samples of the signal and pad them to length M .

• 3) Compute the inverse DFT of the product of the DFTs of the two sequences of length M .

• 4) The result from 3) above is a sequence of length M —take the leftmost 2 N 1 samples, which is

the proper length of the linear convolution of the original two sequences of length N . These samples
form the first 2 N

−

1 output samples (however, only the first N samples will remain unchanged,
as the next iteration will be superposed on this first output sequence starting at sample N +

−

1).

• 5) Take the second N samples of the signal sequence, pad to length M , and use with the padded
impulse response to obtain the next 2 N

− 1 samples of the output sequence using the DFT method.

• 6) Superpose these 2 N − 1 samples onto the current output sequence starting at sample N +1.

• 7) Keep repeating the procedure for each N signal samples, and superposing the result of the
Pth computation starting at output sequence sample index (P

− 1 )(N) + 1. For example, our first

computation ( P 1) was added into the output sequence starting at sample 1, and our second

computation (a sequence of length 2 N

=

− 1) was added in starting at sample ( 2 − 1 )(N) +1 = N + 1,

and so forth until all signal samples have been processed.

Example 3.30. Perform linear convolution using the DFT and the Overlap-Add Method.

Figure 3.27 shows a time just after the beginning of the DFT convolution of an eight-sample
impulse response with a much longer test signal. The test signal is divided into nonoverlapping eight
sample subsequences. The impulse response, and each subsequence in its turn, is padded to length-16.
Then the inverse DFT of the product of the DFTs of the impulse response and subsequence is added into