Mathematics of the DFT

In the signal processing literature, it is common to write the DFT and its inverse in the more pure form below, obtained by setting in the previous definition:

where denotes the input signal at time (sample) , and denotes the th spectral sample. This form is the simplest mathematically, while the previous form is easier to interpret physically.

There are two remaining symbols in the DFT we have not yet defined:

The first,
, is the basis for *complex
numbers*.^{1.1} As a result, complex numbers will be the
first topic we cover in this book (but only to the extent needed
to understand the DFT).

The second, , is a (transcendental) real number defined by the above limit. We will derive and talk about why it comes up in Chapter 3.

Note that not only do we have complex numbers to contend with, but we have them appearing in exponents, as in

We will systematically develop what we mean by imaginary exponents in order that such mathematical expressions are well defined.

With
,
, and imaginary exponents understood, we can go on to prove
*Euler's Identity*:

Euler's Identity is the key to understanding the meaning of expressions like

We'll see that such an expression defines a

Finally, we need to understand what the summation over
is doing in
the definition of the DFT. We'll learn that it should be seen as the
computation of the *inner product* of the signals
and
defined above, so that we may write the DFT, using inner-product
notation, as

where is the sampled complex sinusoid at (normalized) radian frequency , and the inner product operation is defined by

We will show that the inner product of with the th ``basis sinusoid'' is a measure of ``how much'' of is present in and at ``what phase'' (since it is a complex number).

After the foregoing, the inverse DFT can be understood as the
*sum of projections* of
onto
; *i.e.*,
we'll show

where

is the

Note that both the

Having completely understood the DFT and its inverse mathematically, we go
on to proving various *Fourier Theorems*, such as the ``shift
theorem,'' the ``convolution theorem,'' and ``Parseval's theorem.'' The
Fourier theorems provide a basic thinking vocabulary for working with
signals in the time and frequency domains. They can be used to answer
questions such as

``What happens in the frequency domain if I do [operation x] in the time domain?''Usually a frequency-domain understanding comes closest to a

Finally, we will study a variety of practical spectrum analysis
examples, using primarily the `matlab`
programming language
[70] to analyze and display signals and their spectra.

[How to cite this work] [Order a printed hardcopy] [Comment on this page via email]

Copyright ©

Center for Computer Research in Music and Acoustics (CCRMA), Stanford University