Discrete Fourier transform - Continuous and Discrete Time Signals and Systems - page 554

Proof
Expressing Eq. (12.30) in terms of even- and odd-numbered samples of x [ k ],
we obtain

K − 1 K − 1

− j(2 π kr / K ) − j(2 π kr / K )

X [ r ] = x [ k ]e + x [ k ]e , (12.31)

k = 0 , 2 , 4 ,... k = 1 , 3 , 5 ,...

Term I Term II

for 0 ≤ r ≤ ( M − 1). Substituting k = 2 m in Term I and k = 2 m + 1 in Term II,
Eq. (12.31) can be expressed as follows:

K / 2 − 1 K / 2 − 1

x [2 m ]e − j(2 π (2 m ) r / K ) + x [2 m + 1]e − j(2 π (2 m + 1) r / K ) X [ r ] =

m = 0 , 1 , 2 ,... m = 0 , 1 , 2 ,...

or

K / 2 − 1

x [2 m ]e − j2 π mr / ( K / 2) X [ r ] =

m = 0 , 1 , 2 ,...

+ e − j(2 π r / K ) K / 2 − 1 x [2 m + 1]e − j2 π mr / ( K / 2) , (12.32)

m = 0 , 1 , 2 ,...

where exp[ − j2 π (2 m ) r / K ] = exp[ − j2 π mr / ( K / 2)] . By expressing g [ m ] =
x [2 m ] and h [ m ] = x [2 m + 1], we can rewrite Eq. (12.32) in terms of the DFTs
of g [ m ] and h [ m ]:

K / 2 − 1 K / 2 − 1

g [ m ]e − j2 π mr / ( K / 2) + e − j2 π r / K h [ m ]e − j2 π mr / ( K / 2)

X [ r ] =

m = 0 , 1 , 2 ,... m = 0 , 1 , 2 ,...

= G [ r ] = H [ r ]

(12.33)

or

X [ r ] = G [ r ] + W K H [ r ] , (12.34)

where W K is defined as exp( − j2 π/ K ). In FFT literature, W K is generally
referred to as the twiddle factor. Note that in Eqs. (12.33) and (12.34), G [ r ]
represents the (K/2)-point DFT of g [ k ], the even-numbered samples of x [ k ].
Similarly, H [ r ] represents the ( K / 2)-point DFT of h [ k ], the odd-numbered
samples of x [ k ]. Equation (12.34) thus proves Proposition 12.1.

Based on Eqs. (12.34), the procedure for determining the K -point DFT can be
summarized by the following steps.

(1) Determine the ( K / 2)-point DFT G [ r ] for 0 ≤ r ≤ ( K / 2 − 1) of the even-
numbered samples of x [ k ].