4
Fourier Analysis and the Discrete Fourier
Transform
Summary. Having discussed sampling and time-limiting and how they affect a
signal’s spectrum, we move on to the estimation of the spectrum of a signal from
the signal’s samples. In this chapter, we introduce the discrete Fourier transform, we
discuss its significance, and we derive its properties. Then we discuss the family of
algorithms know as fast Fourier transforms. We explain their significance, describe
how one uses them, and discuss zero-padding and the fast convolution algorithm.
Keywords. Fourier transform, discrete Fourier transform, fast Fourier transform,
zero-padding, fast convolution.
4.1 An Introduction to the Discrete Fourier Transform
Often, we need to determine the spectral content of a signal—how much of
a signal’s power is located at a given frequency. In general, this means that
we would like to determine the Fourier transform of the signal. Because we
are actually measuring the signal, we cannot possibly know its values from
t = −∞ to t =+∞. We can only know the signal’s value in some finite
interval. As we generally use a microprocessor to make measurements, even
in that interval we only know the signal’s value at discrete times—generally
at the times t = nT
s
where T
s
is the sampling period. From this set of time-
limited samples, we would like to estimate the Fourier transform of the signal.
If all that one knows of a signal is its value in an interval it is clearly
impossible to determine the signal’s Fourier transform. Something must be
assumed about the signal at the times for which no measurements exist. A
fairly standard assumption, and the most reasonable in many ways, is that the
function is zero outside the region in which it is measured and is reasonably
smooth inside this region. We will, once again, consider the consequences
of time-limiting the function—of “lopping off the tails” of the function—in
Chapter 5.
Recalling that the Fourier transform of a function, y(t), is
