Since W
0
2
1and W
1
2
e
Àp
À1 , we have
X0 x0 x1
and
X1 x0 À x1:
The signal flow graph is shown in Figure 7.7. Note that the results are agreed with
the results obtained in Example 7.1.
As shown in Figure 7.6, the output sequence is in natural order, while the input
sequence has the unusual order. Actually the order of the input sequence is arranged as
if each index was written in binary form and then the order of binary digits was reversed.
The bit-reversal process is illustrated in Table 7.1for the case N 8. Each of the time
sample indices in decimal is converted to its binary representation. The binary bit streams
are then reversed. Converting the reversed binary numbers to decimal values gives the
reordered time indices. If the input is in natural order the output will be in bit-reversed
order. We can either shuffle the input sequence with a bit-reversal algorithm to get the
output sequence in natural order, or let the input sequence be in natural order and shuffle
the bit-reversed results to obtain the output in natural order. Note that most modern
DSP chips such as the TMS320C55x provide the bit-reversal addressing mode to support
this bit-reversal process. Therefore the input sequence can be stored in memory with the
bit-reversed addresses computed by the hardware.
For the FFT algorithm shown in Figure 7.6, once all the values for a particular stage
are computed, the old values that were used to obtain them are never required again.
Thus the FFT needs to store only the N complex values. The memory locations used for
the FFT outputs are the same as the memory locations used for storing the input data.
This observation is used to produce in-place FFT algorithms that use the same memory
locations for input samples, all intermediate calculations, and final output numbers.
Table 7.1 Example of bit-reversal process, N 8 (3-bit)
Input sample index
&
Bit-reversed sample index
Decimal
Binary
Binary
Decimal
0
000
000
0
10011
00
4
2
01 0
01 0
2
3
011
110
6
4
100
001
1
5
101
101
5
6
110
011
3
7
111
111
7
318
FAST FOURIER TRANSFORM AND ITS APPLICATIONS