The Discrete Fourier Transform (DFT) can be understood as a numerical approximation to the Fourier transform. However, the DFT has its own exact Fourier theory, which is the main focus of this book. The DFT is normally encountered in practice as a Fast Fourier Transform (FFT)--i.e., a high-speed algorithm for computing the DFT. FFTs are used extensively in a wide range of digital signal processing applications, including spectrum analysis, high-speed convolution (linear filtering), filter banks, signal detection and estimation, system identification, audio compression (e.g., MPEG-II AAC), spectral modeling sound synthesis, and many other applications; some of these will be discussed in Chapter 8.
This book started out as a series of readers for my introductory course in digital audio signal processing that I have given at the Center for Computer Research in Music and Acoustics (CCRMA) since 1984. The course was created primarily for entering Music Ph.D. students in the Computer Based Music Theory program at CCRMA. As a result, the only prerequisite is a good high-school math background, including some calculus exposure.
- ``Introduction to the DFT'' points out the mathematical
elements which will be discussed in this book, all motivated by the
- ``Introduction to Complex Numbers'' is about factoring
polynomials, the quadratic formula, the complex plane, and Euler's
- ``Proof of Euler's Identity'' derives Euler's identity
in detail. This is an important tool for working with complex
numbers, and one of the critical elements of the DFT definition we
need to understand.
- ``Sinusoids and Exponentials'' is devoted to two of the
most elementary signals in signal processing--sinusoids and
exponentials. Also covered are complex sinusoids, audio decay
time (), in-phase and quadrature sinusoidal components,
analytic signals, positive and negative frequencies, constructive and
destructive interference, invariance of sinusoidal frequency in linear
time-invariant systems, circular motion as the vector sum of in-phase
and quadrature sinusoidal motions, sampled sinusoids, and generating
sampled sinusoids from powers of a unit-modulus complex number.
- ``Geometric Signal Theory'' provides an introduction to
vector spaces, inner products, orthogonality, projection of one signal
onto another, norms, and elementary vector space operations. In this
setting, the DFT can be regarded as a change of coordinates from one
basis set (shifted impulses) to another (sinusoids at different
- ``The DFT Derived'' derives the DFT as a projection of a
length signal onto the set of sampled complex
sinusoids generated by the th roots of unity.
- ``Fourier Theorems for the DFT'' derives basic Fourier
symmetry relations, the shift theorem, convolution theorem,
correlation theorem, power theorem, and theorems pertaining to
interpolation and downsampling.
- ``Example Applications of the DFT'' illustrates
practical FFT analysis in Matlab
and Octave (an open-source
matlab) through a series of examples. The various Fourier theorems of
the preceding chapter provide a ``thinking vocabulary'' for
understanding these applications.
Elementary and supporting information is provided in a series of appendices. Topics include introductions to sampling theory, Taylor series expansions, logarithms, decibels, digital audio number systems, matrices, round-off noise, Fourier series, and continuous-time Fourier theorems, such as the similarity and differentiation theorems. As a segue to computer-based approaches, a well used Fast Fourier Transform (FFT) algorithm is derived. Finally, various software examples in the Matlab (or Octave) programming language are presented.
This book is first in a series of course readers for my signal processing courses at CCRMA:
- Mathematics of the Discrete Fourier Transform (DFT):
- Introduction to Digital Filters:
- Physical Audio Signal Processing
(the ``physical modeling book''):
- Spectral Audio Signal Processing
(the ``spectral modeling book''):
- Audio Digital Filter Design
(an update of Chapter 1 of my PhD/EE thesis ):
Thanks to my graduate students and research colleagues Sean Bratnober, Mark Cartwright, Humane Chan, Rob Hamilton, Miriam Kolar, Randal Leistikow, Sandy Lin, Gautham Mysore, Juhan Nam, Jeonghun Noh, Brook Reeder, Bill Schottstaedt, Sook Young Won, Vivian Woo, and Matt Wright for helpful errata reporting and other suggestions based on earlier precursors to this book. Special thanks are due to Miller Puckette for some especially useful contributions. Thanks also to netizens Greg Allen, Adi Biton, John Brenneise, David Holman, Alexander Kraus, Nima Maftoon, Niels Moseley, Hirak Parikh, and Eric Woudenberg for reporting errata in the draft versions on the Web. Additionally, email discussions with Steven Johnson (co-author of the well known FFTW software package) contributed greatly to the appendix on FFT algorithms.
Many thanks to my 1997 teaching assistant Craig Stuart Sapp for writing the Mathematica magic for Figures 4.9 (adapted for the cover), 4.17, 4.18, 4.19, 7.5, 7.9, 7.11, and 7.12.
Thanks also to Prof. C. Sidney Burrus of Rice University for teaching me and others the fundamentals of digital signal processing, including the DFT.
Finally, thanks to my wife Carol for her encouragement and support, and for putting up with all those ``working Saturdays'', and to my son Harrison, age 9, for his many inspirations, both musical and mathematical, among others.
While I have tried, with help from my students and interested colleagues, to compose a correct manuscript, it is inevitable that ``suboptimalities'' will be discovered over time. The Web page http://books.w3k.org/mdft2/ will list any known errata, clarifications, or other information pertaining to this book.
The author and publisher make no warranties, express or implied, regarding the contents of this book.
Introduction to the DFT