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

() =+ ( )( ) + ( ) () +- ( )( ) X 15 1 j 1 1 307 . - j 0 541 . j j 1 414 . 1

( ) () =+ +- 1 307 . - j 0 541 . j 1 j 5 028 .

The output sequence X (0), X (1),..., X (15) is identical to the output sequence
obtained with the 16-point FFT with the radix-2 in Figure 6.6. These results also can
be verified with MATLAB, as described in Appendix D.
The output sequence is scrambled and needs to be resequenced or reordered.
This can be done using a digit-reversal procedure, in a similar fashion as a bit rever-
sal in a radix-2 algorithm. The radix-4 (base 4) uses the digits 0, 1, 2, 3. For example,
the addresses of X (8) and X (2) need to be swapped because (8) 10 in base 10 or
decimal is equal to (20) 4 in base 4. Digits 0 and 1 are reversed to yield (02) 4 in base
4, which is also (02) 10 in decimal.
Although mixed or higher radices can provide a further reduction in computa-
tion, programming considerations become more complex. As a result, radix-2 is still
the most widely used, followed by radix-4. Two programming examples are included
in Section 6.8, and two projects are described in Chapter 10.

6.7 INVERSE FAST FOURIER TRANSFORM

The inverse discrete Fourier transform (IDFT) converts a frequency-domain
sequence X ( k ) into an equivalent sequence x ( n ) in the time domain. It is defined as

N -

Â

1

1

() = ()

- nk

xn XkW n = 01 , ,..., N - 1 (6.37)

N

k = 0

Comparing (6.37) with the DFT equation definition in (6.1), we see that the FFT
algorithm (forward) described previously can be used to find the inverse FFT
(IFFT) with the two following changes:

1. Adding a scaling factor of 1/ N
2. Replacing W nk by its complex conjugate W - nk

With the changes, the same FFT flow graphs can be used for the IFFT. We also
develop programming examples to illustrate the inverse FFT.
A variant of the FFT, such as the FHT, can be obtained readily from the FFT.
Conversely, the FFT can be obtained from the FHT [10,11]. A development of
the FHT with flow graphs and exercises for 8- and 16-point FHTs can be found in
Appendix F.

Exercise 6.5: Eight-Point IFFT

Let the output sequence X (0) j 2.41 obtained

in Exercise 6.1 become the input to an eight-point IFFT flow graph. Make the two

= 4, X (1) = 1 - j 2.41,..., X (7) = 1 +