where nfft specifies the FFT length, Fs is the sampling frequency, window specifies
the selected window function, and noverlap is the number of samples by which the
segments overlap.
7.3.4 Fast Convolution
As discussed in Chapter 5, FIR filtering is a linear convolution of the finite impulse
response h(n) with the input sequence x(n). If the FIR filter has L coefficients, we need L
real multiplications and L À 1real additions to compute each output y(n). To obtain L
output samples, the number of operations (multiplication and addition) needed is
proportional to L
2
. To reduce the computational requirements, we consider the alter-
nate approach defined in (7.1.26) and (7.1.27), which uses the property that the con-
volution of the sequences x(n) and h(n) is equivalent to multiplying their DFTs X(k)
and H(k).
As described in Section 7.1.3, the linear convolution can be implemented using zero
padding if the data sequence x(n) also has finite duration. To take advantage of efficient
FFT and IFFT algorithms, we use these computational efficient algorithms as illus-
trated in Figure 7.13. The procedure of using FFT to implement linear convolution in a
computationally efficient manner is called the fast convolution. Compared to the direct
implementation of FIR filtering, fast convolution will provide a significant reduction in
computational requirements for higher order FIR filters, thus it is often used to imple-
ment FIR filtering in applications having long data samples.
It is important to note that the fast convolution shown in Figure 7.13 produces the
circular convolution discussed in Section 7.1.3. In order to produce a filter result equal
to a linear convolution, it is necessary to append zeros to the signals in order to
overcome the circular effect. If the data sequence x(n) has finite duration M, the first
step is to pad both sequences with zeros to a length corresponding to an allowable FFT
size N ! L M À 1, where L is the length of the sequence h(n). The FFT is computed
for both sequences, the complex products defined in (7.1.27) are calculated, and the
IFFT is used to obtain the results. The desired linear convolution is contained in the
first L M À 1terms of these results.
The FFT of the zero-padded data requires about N log
2
N complex computations.
Since the filter impulse response h(n) is known as a priori, the FFT of the impulse
response can be pre-calculated and stored. The computation of product
Yk HkXk takes N complex multiplications, and the inverse FFT of the pro-
ducts Y(k) requires another N log
2
N complex multiplications. Therefore the fast con-
volution shown in Figure 7.13 requires about (8N log
2
N 4N) real multiplications.
x(n)
h(n)
X(k)
H(k)
Y(k)
y(n)
FFT
FFT
IFFT
Figure 7.13 Fast convolution algorithm
330
FAST FOURIER TRANSFORM AND ITS APPLICATIONS