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

FIGURE 6.7. Output magnitude for 16-point FFT.

Verify the scrambled output sequence X 's as shown in Figure 6.6. Reorder this
output sequence and take its magnitude. Verify the plot in Figure 6.7, which repre-
sents a sinc function. The output X (8) represents the magnitude at the Nyquist fre-
quency. These results can be verified with MATLAB, as described in Appendix D.

6.4 DECIMATION-IN-TIME FFT ALGORITHM WITH RADIX-2

Whereas the DIF process decomposes an output sequence into smaller subse-
quences, decimation-in-time (DIT) is a process that decomposes the input sequence
into smaller subsequences. Let the input sequence be decomposed into an even
sequence and an odd sequence, or

() () () ( ) xxx 024 , , ,..., xn 2

and

() () () ( ) xxx 135 , , ,..., xn 21 +

We can apply (6.1) to these two sequences to obtain

( ) - ( ) -

N 21 N 21

 Â

() ( )

( )

2 nk 21 nk +

Xk () = x nW 2 + x n 2 + 1 W (6.22)

n = 0 n = 0

Using W N = W N /2 in (6.22) yields

( ) - ( ) - N 21 N 21

 Â

() ( )

Xk () = xnW 2

nk

+ W

N k

xn 2 + 1 W

nk

(6.23)

N 2 N 2

n = 0 n = 0