Page 515 - Advanced engineering mathematics

14.5 The Discrete Fourier Transform 495

We claim that
N−1
1 2πijk/N
u j = U k e (14.18)
N
k=0
for j = 0,1,··· , N − 1. This is the inversion formula for the N-point DFT, and it is analogous
to inversion formulas for the Fourier transform and for the Fourier cosine and sine transforms,
with a summation replacing an integral.
To verify equation (14.18) it is convenient to put W = e −2πi/N . Then
N
W = 1 and W −1 = e 2πi/N .
Write
N−1 N−1
1 2πijk/N 1 − jk
U k e = U k W
N N
k=0 k=0
N−1 N−1
1
= u r e −2πirk/N W − jk
N
k=0 r=0
N−1 N−1
1 rk − jk
= u r W W
N
k=0 r=0
N−1 N−1
1
rk
= u r W W − jk
N
r=0 k=0
N−1 N−1
1
) .
= u r (W r− j k
N
r=0 k=0
Now, if r = j then (again using the finite geometric series),
N−1 r− j N
r− j k 1 − (W )
(W ) = = 0
1 − W r− j
k=0
because
) = e
(W r− j N −2π(r− j) = 1 and W r− j = e 2πi(r− j)/N = 1.
) = 1, so
But if r = j, then (W r− j k
N−1
r− j k
(W ) = N.
k=0
Therefore, in the last double summation we need only retain the term when r = j in the
summation with respect to r, yielding
N−1
N−1
N−1
1 1
U k e 2πijk/N = u r (W r− j k
)
N N
k=0 r=0 k=0
1
= u j N = u j .
N
14.5.3 DFT Approximation of Fourier Coefficients
We will now complete the idea suggested at the beginning of this section, approximating Fourier
coefficients by a discrete Fourier transform.

Copyright 2010 Cengage Learning. All Rights Reserved. May not be copied, scanned, or duplicated, in whole or in part. Due to electronic rights, some third party content may be suppressed from the eBook and/or eChapter(s).
Editorial review has deemed that any suppressed content does not materially affect the overall learning experience. Cengage Learning reserves the right to remove additional content at any time if subsequent rights restrictions require it.

October 14, 2010 16:43 THM/NEIL Page-495 27410_14_ch14_p465-504