This chapter introduces the Discrete
Fourier Transform (
DFT) and
points out the mathematical elements that will be explicated in this
book. To find motivation for a detailed study of the DFT, the reader
might first peruse Chapter
8 to get a feeling for some of the many
practical applications of the DFT. (See also the preface on page
![[*]](../icons/crossref.png)
.)

Before we get started on the DFT, let's look for a moment at the
Fourier transform (FT) and explain why we are not talking about
it instead. The Fourier transform of a continuous-time
signal 
may be defined as
Thus, right off the bat, we need
calculus. The DFT, on the
other hand, replaces the infinite integral with a finite sum:
where the various quantities in this formula are defined on the next
page. Calculus is not needed to define the DFT (or its inverse, as we
will see), and with finite summation limits, we cannot encounter
difficulties with infinities (provided

is finite, which is
always true in practice). Moreover, in the field of
digital signal
processing, signals and
spectra are processed only in
sampled
form, so that the DFT is what we really need anyway (implemented using
an
FFT when possible). In summary, the DFT is
simpler
mathematically, and
more relevant computationally than the
Fourier transform. At the same time, the basic concepts are the same.
Therefore, we begin with the DFT, and address FT-specific results in
the appendices.
DFT Definition
The
Discrete Fourier Transform (DFT) of a
signal 
may be defined by
where `

' means ``is defined as'' or ``equals by definition'', and
The
sampling interval 
is also called the
sampling period.
For a tutorial on sampling continuous-time signals to obtain
non-
aliased discrete-time signals, see Appendix
D.
When all

signal samples

are real, we say

.
If they may be complex, we write

. Finally,

means

is any integer.
Inverse DFT
The
inverse DFT (the IDFT) is given by
The inverse DFT is written using `

' instead of `

' because
the result follows from the definition of the DFT, as we will show
in Chapter
6.
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
sampled complex
sinusoid, and we'll talk about
sinusoids in some detail, particularly
from an audio perspective.
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
coefficient of projection of

onto

.
Using the notation

to mean the whole signal

for all
![$ n\in [0,N-1]$](http://www.dsprelated.com/josimages_new/mdft/img39.png)
, the IDFT can be written more simply as
Note that both the
basis sinusoids 
and their coefficients of
projection

are
complex valued in general.
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
perceptual
understanding of audio processing.
Finally, we will study a variety of practical
spectrum analysis
examples, using primarily the
matlab
programming language
[
67] to analyze and display signals and their
spectra.
DFT Math Outline
In summary, understanding the DFT takes us through the following topics:
We will additionally discuss various practical aspects of working with
signals and
spectra.
Next Section: Complex NumbersPrevious Section: Preface