The discrete Fourier transform for transforming a time-domain signal
fx0, x1, x2, F F F , xN À 1g into frequency-domain samples fXkg of length N
is expressed as
Xk
NÀ1
n0
xne
Àj
2p
N
kn
, k 0,1, F F F , N À 1,
4:4:23
where n is the time index, k is the frequency index,and Xk is the kth DFT coefficient.
The inverse discrete Fourier transform (IDFT) is defined as
xn
1
N
NÀ1
k0
Xke
j
2p
N
kn
, n 0,1, F F F , N À 1:
4:4:24
Equation (4.4.23) is called the analysis equation for calculating the spectrum from the
signal,and (4.4.24) is called the synthesis equation used to reconstruct the signal from its
spectrum. This pair of DFT and IDFT equations holds for any discrete-time signal that
is periodic with period N.
When we define the twiddle factor as
W
N
e
Àj
2p
N
,
4:4:25
the DFT defined in (4.4.23) can be expressed as
Xk
NÀ1
n0
xnW
kn
N
, k 0,1, F F F , N À 1:
4:4:26
Similarly,the IDFT defined in (4.4.24) can be expressed as
xn
1
N
NÀ1
k0
XkW
Àkn
N
, n 0,1, F F F , N À 1:
4:4:27
Note that W
N
is the Nth root of unity since e
Àj2p
1. Because the W
kn
N
are N-periodic,the
DFT coefficients are N-periodic. The scalar 1/N that appears in the IDFT in (4.4.24) does
not appear in the DFT. However,if we had chosen to define the DFT with the scalar 1/N,
it would not have appeared in the IDFT. Both forms of these definitions are equivalent.
Example 4.16: In this example,we develop a user-written MATALB function to
implement DFT computations. MATLAB supports complex numbers indicated
by the special functions i and j.
Consider the following M-file (dft.m in the software package):
function [Xk] dft(xn, N)
% Discrete Fourier transform function
%
[Xk] dft(xn, N)
% where xn is the time-domain signal x(n)
158
FREQUENCY ANALYSIS