Page 364 - Schaum's Outline of Theory and Problems of Signals and Systems

CHAP. 61 FOURIER ANALYSIS OF DISCRETE-TIME SIGNALS AND SYSTEMS 35 1

(b) Show that the N-point DFT X[k] of x[n] can be expressed as

1
(N/2)- N
where F[k]= C f[n]W$2 k =0,1,...9 - - 1 (6.218~)
2
n=O

(c) Draw a flow graph to illustrate the evaluation of X[k] from Eqs. (6.217~) and
(6.2176) with N = 8.
(d) Assume that x[n] is complex and w,"~ have been precomputed. Determine the
numbers of complex multiplications required to evaluate X[k] from Eq. (6.214)
and from Eqs. (6.217a) and (6.217b) and compare the results for N = 2'' = 1024.
(a) From Eq. (6.213)

f [n] =x[2n] = 0, n < 0 and f[:] =x[N] =O

Thus

Similarly
KI
g[n]=x[2n+l]=O,n<O and g - =x[N+ 1]=O

Thus,

(b) We rewrite Eq. (6.214) as
X[k] = x x[n] Win + C x[n] W,kn
n even n odd

With this substitution Eq. (6.219) can be expressed as