7.1.1 Definitions
Given the DTFT X!, we take N samples over the full Nyquist interval, 0 ! < 2p, at
discrete frequencies !
k
2pk=N, k 0, 1, . . . , N À 1. This is equivalent to evaluating
X! at N equally spaced frequencies !
k
, with a spacing of 2p=N radians (or f
s
=N Hz)
between successive samples. That is,
X!
k
I
nÀI
xne
Àj2p=Nkn
NÀ1
n0
I
lÀI
xn À lN
4
5
e
Àj2p=Nkn
NÀ1
n0
x
p
ne
Àj2p=Nkn
, k 0, 1, . . . , N À 1,
7:1:1a
where
x
p
n
I
lÀI
xn À lN
7:1:1b
is a periodic signal with period N.
In general, the equally spaced frequency samples do not represent the original
spectrum X! uniquely when x(n) has infinite duration. Instead, these frequency
samples correspond to a periodic sequence x
p
n as shown in (7.1.1). When the sequence
x(n) has a finite length N, x
p
n is simply a periodic repetition of x(n). Therefore
the frequency samples X!
k
, k 0, 1, . . . , N À 1uniquely represent the
finite-duration sequence x(n). Since xn x
p
n over a single period, a finite-duration
sequence x(n) of length N has the DFT defined as
Xk X!
k
X
2pk
N
NÀ1
n0
xne
Àj2p=Nkn
, k 0, 1, . . . , N À 1,
7:1:2
where X(k) is the kth DFT coefficient and the upper and lower indices in the summation
reflect the fact that xn 0 outside the range 0 n N À 1. Strictly speaking, the DFT
is a mapping between an N-point sequence in the time domain and an N-point sequence in
the frequency domain that is applicable in the computation of the DTFT of periodic and
finite-length sequences.
Example 7.1: If the signals fxng are real valued and N is an even number, we can
show that X0 and XN=2 are real values and can be computed as
X0
NÀ1
n0
xn
304
FAST FOURIER TRANSFORM AND ITS APPLICATIONS