This book presents an introduction to the principles of the fast Fourier transform
(FFT). It covers FFTs, frequency domain filtering, and applications to video and
audio signal processing.
As fields like communications, speech and image processing, and related areas
are rapidly developing, the FFT as one of the essential parts in digital signal
processing has been widely used. Thus there is a pressing need from instructors
and students for a book dealing with the latest FFT topics.
This book provides a thorough and detailed explanation of important or up-todate
FFTs. It also has adopted modern approaches like MATLAB examples and
projects for better understanding of diverse FFTs.
Fast Fourier transform (FFT) is an efficient implementation of the discrete Fourier
transform (DFT). Of all the discrete transforms, DFT is most widely used in digital
signal processing. The DFT maps a sequence either in the time domain or in the
spatial domain into the frequency domain. The development of the DFT originally by
Cooley and Tukey [A1] followed by various enhancements/modifications by other
researchers has provided the incentive and the impetus for its rapid and widespread
utilization in a number of diverse disciplines. Independent of the Cooley-Tukey
approach, several algorithms such as prime factor, split radix, vector radix, split
vector radix, Winograd Fourier transform, and integer FFT have been developed. The
emphasis of this book is on various FFTs such as the decimation-in-time FFT,
decimation-in-frequency FFT algorithms, integer FFT, prime factor DFT, etc.
In some applications such as dual-tone multi-frequency detection and certain
pattern recognition, their spectra are skewed to some regions that are not uniformly
distributed. With this basic concept we briefly introduce the nonuniform DFT
(NDFT), dealing with arbitrarily spaced samples in the Z-plane, while the DFT
deals with equally spaced samples on the unit circle with the center at the origin in
A number of companies provide software for implementing FFT and related
basic applications such as convolution/correlation, filtering, spectral analysis, etc.
on various platforms. Also general-purpose DSP chips can be programmed to
implement the FFT and other discrete transforms.