Fast Fourier Transform - Digital Signal Processing and Applications with the C6713 and C6416 DSK - page 218

which represents two ( N /2)-point DFTs. Let

( ) -

Â

N 21

() = ()

Ck x nW N nk 2

(6.24)

2

n = 0

( ) -

Â

N 21

() = ( )

Dk X 21 2 n + W N nk (6.25)

n = 0

Then X ( k ) in (6.23) can be written as

() = () + ()

Xk Ck W Dk

N k

(6.26)

Equation (6.26) needs to be interpreted for k > ( N /2) - 1. Using the symmetry prop-

erty (6.5) of the twiddle constant, W k + N /2 W k ,

=-

( ) = () - () ( ) -

Xk N + 2 Ck W Dk

k

k = 0 1 , ,..., N 2 1 (6.27)

For example, for N = 8, (6.26) and (6.27) become

() = () + ()

Xk Ck W Dk

k

k = 0123 ,, , (6.28)

( ) = () - ()

Xk + 4 Ck W Dk

k

k = 0123 ,, , (6.29)

Figure 6.8 shows the decomposition of an eight-point DFT into two four-point DFTs
with the DIT procedure. This decomposition or decimation process is repeated so
that each four-point DFT is further decomposed into two two-point DFTs, as shown
in Figure 6.9. Since the last decomposition is ( N /2) two-point DFTs, this is as far as
this process goes.
Figure 6.10 shows the final flow graph for an eight-point FFT using a DIT process.
The input sequence is shown to be scrambled in Figure 6.10 in the same manner as
the output sequence X ( k ) was scrambled during the DIF process. With the input

FIGURE 6.8. Decomposition of eight-point DFT into four-point DFTs using DIT.