Graphics Programs Reference
In-Depth Information
13.11. The Discrete Fourier Transform
The Discrete Fourier Transform (DFT) is a mathematical operation that
transforms a discrete sequence, usually from the time domain into the fre-
quency domain, in order to explicitly determine the spectral information for the
sequence. The time domain sequence can be real or complex. The DFT has
finite length
N
, and is periodic with period equal to
N
.
The discrete Fourier transform for the finite sequence
x ()
is defined by
N
–
1
j nk
N
---------------
–
ô
()
=
x () e
;
k
=
0 … N
,
,
–
1
(13.120)
n
=
0
The inverse DFT is given by
N
–
1
j nk
N
---------------
1
----
ô
ô ()
=
() e
;
n
=
0 … N
,
,
–
1
(13.121)
k
=
0
The Fast Fourier Transform (FFT) is not a new kind of transform different
from the DFT. Instead, it is an algorithm used to compute the DFT more effi-
ciently. There are numerous FFT algorithms that can be found in the literature.
In this topic we will interchangeably use the DFT and the FFT to mean the
same thing. Furthermore, we will assume radix-2 FFT algorithm, where the
FFT size is equal to
2 m
N
=
for some integer
m
.
13.12. Discrete Power Spectrum
Practical discrete systems utilize DFTs of finite length as a means of numer-
ical approximation for the Fourier transform. It follows that input signals must
be truncated to a finite duration (denoted by ) before they are sampled. This
is necessary so that a finite length sequence is generated prior to signal pro-
cessing. Unfortunately, this truncation process may cause some serious prob-
lems.
T
To demonstrate this difficulty, consider the time domain signal
. The spectrum of consists of two spectral lines at .
Now, when is truncated to length seconds and sampled at a rate
, where is the number of desired samples, we produce the
sequence . The spectrum of would still be
composed of the same spectral lines if is an integer multiple of and if the
DFT frequency resolution is an integer multiple of . Unfortunately, those
two conditions are rarely met and, as a consequence, the spectrum of
x ()
=
sin
f 0 t
x ()
±
f 0
x ()
T
T s
=
TN
N
{
x () n
;
=
01… N
,, ,
–
1
}
x ()
T
T s
f
f 0
x ()
Search WWH ::




Custom Search