Digital Signal Processing Reference
In-Depth Information
9.4 APPLICATION OF FFT TO FILTERING
There are many applications for the FFT. Frequency analysis, spectral densities,
and filtering are among the more popular. Since this is a text about filtering, we
discuss how the FFT can be used in filtering applications. To begin this
discussion, we review the process of FIR filtering first. Once FIR filter
coefficients have been determined, the output signal of the filter can be
determined from the input signal by convolving the filter coefficients and the input
signal, as shown in (9.13). We learned in Chapter 5 that convolution in the time
domain was equivalent to simple multiplication in the frequency domain, as
shown in (9.14).
M
∑
−
=
1
y
(
n
)
=
h
(
n
)
∗
x
(
n
)
=
h
(
k
)
⋅
x
(
n
−
k
)
n
=
0
1
…
,
N
−
1
(9.13)
k
0
Y
(
z
)
=
H
(
z
)
⋅
X
(
z
)
(9.14)
Since we now have a fast algorithm for determining the transform of a time-
domain signal, it may be useful to consider the alternative presented by (9.14).
Let's consider the steps involved in using transforms to implement the filtering
process:
1. Transform the filter coeffients:
H
(
z
)
= FFT
[
h
(
n
)
]
.
2. Transform the input signal:
X
(
z
)
=
FFT
[
x
(
n
) ]
.
3. Multiply the two complex sequences:
Y
(
z
)
= H
(
z
)
·X
(
z
)
.
4. Inverse transform to find the output:
y
(
n
)
= FFT
-1
[
Y
(
z
) ].
The process outlined above may or may not prove to be faster than the
convolution of (9.13). It all depends on the number of filter coefficients and the
number of points in the FFT. The text by Proakis and Manolakis mentioned in
Appendix A offers a detailed comparison that will be discussed further at the end
of this section. Listing 9.3 shows
Dig_FFT_Filt
that performs steps 2 through
4 above. Note that it is assumed that the filter coefficients have already been
transformed and stored in
H
. The function first transforms the input signal
X
, then
multiplies the coefficients times the transform of
X
, and finally computes the
inverse FFT. Note that the results of each of these steps are stored in
X
.
There are many cases when the length of the input signal exceeds the size of
the FFT that can be applied. In that case, the signal must be broken into smaller,
more manageable, sections and the FFT filtering algorithm applied to each section.
Unfortunately, it is not as simple as taking each
N
-point group of input samples
and generating an output group. The resulting patched-together sequence would
undoubtedly have discontinuities at the combination points. This problem can be
