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

FIGURE 6.1. Periodicity and symmetry of twiddle constant W .

smallest transform is determined by the radix of the FFT. For a radix-2 FFT, N must
be a power or base of 2, and the smallest transform or the last decomposition is the
two-point DFT. For a radix-4, the last decomposition is a four-point DFT.

6.3 DECIMATION-IN-FREQUENCY FFT ALGORITHM WITH RADIX-2

Let a time-domain input sequence x ( n ) be separated into two halves:

x N

Ê
Ë

ˆ
¯

() ()

(a) xx 01 , ,..., - 1 (6.6)

2

and

N N

Ê
Ë

ˆ
¯

Ê
Ë

ˆ
¯

( )

(b) x , x + 1 ,..., xN - 1 (6.7)

2 2

Taking the DFT of each set of the sequence in (6.6) and (6.7) gives us

( ) - N 21 N - 1

 Â

() = () ()

nk nk

Xk xnW + xnW (6.8)

n = 0 nN = 2

Let n = n + N /2 in the second summation of (6.8); X ( k ) becomes

( ) - ( ) - N 21 N 21

N

Ê
Ë

ˆ
¯

 Â

() = ()

Xk xnW

nk

+ W

k N 2

x n + W

nk

(6.9)

2

n = 0 n = 0