Digital Signal Processing Reference
In-Depth Information
CHAPTER
3
The DFT
3.1
OVERVIEW
In previous chapters, we have studied the DTFT and the
z
-transform, both of which have important
places in discrete signal processing theory, but neither is a numerically computable transform. Signal
processing as applied in industry and commerce, however, for such applications as audio and video com-
pression algorithms, etc., relies on computable transforms. Unlike the DTFT and
z
-transform, however,
the Discrete Fourier Transform is a numerically computable transform. It is a reversible frequency trans-
form that evaluates the spectrum of a finite sequence at a finite number of frequencies. It is perhaps the
best known and most widely used transform in digital signal processing. Many papers and books have
been written about it. There are other numerically computable frequency transforms, such as the Dis-
crete Cosine Transform (DCT), the Modified Discrete Cosine Transform (MDCT), the Discrete Sine
Transform (DST), and the Discrete Hartley Transform (DHT), but the DFT is the most often discussed
and used frequency transform. Its fast implementation, the FFT (actually an entire family of algorithms)
serves as the computational basis not only for the DFT per se, but for other transforms that are related
to the DFT but do not have their own fast implementations. While the end goal of much DFT use may
be spectral analysis, there is a growing body of applications that use the DFT-IDFT (and relatives of it,
such as the Discrete Cosine Transform) for data compression.
In this chapter we cover the DFS and its basis, the reconstruction of a sequence from samples of its
z
-transform, followed by the definition(s), basic properties, and computation of the DFT. We then delve
into a mix of practical and theoretical matters, including the DFTs of common signals, determination of
Frequency Resolution/Binwidth, the FFT or Fast Fourier Transform, the Goertzel Algorithm (a simple
recursive method to compute a single DFT bin which finds utility in such things as DTMF detection and
the like), implementation of linear convolution using the DFT (a method permitting efficient convolution
of large blocks of data), DFT Leakage (an issue in spectral analysis and signal detection), computation of
the DTFT via the DFT, and the Inverse DFT (IDFT), which we compute directly, by matrix methods,
or through ingenious use of the DFT.
3.2
SOF TWARE FOR USE WITH THIS Topic
The software files needed for use with this topic (consisting of m-code (.m) files, VI files (.vi), and related
support files) are available for download from the following website:
http://www.morganclaypool.com/page/isen
The entire software package should be stored in a single folder on the user's computer, and the full
file name of the folder must be placed on the MATLAB or LabVIEW search path in accordance with the
instructions provided by the respective software vendor (in case you have encountered this notice before,
which is repeated for convenience in each chapter of the topic, the software download only needs to be
done once, as files for the entire series of four volumes are all contained in the one downloadable folder).
See Appendix A for more information.
