Signals and Systems

11.13 BIT REVERSAL

Let us consider the signal flow graph of eight-point DIT FFT algorithm shown in Fig. 11.12 where the sequence of input data is shuffled as x(0), x(4), x(2), x(6), x(1), x(5), x(3), x(7). The DFT sequence X(k) at the output is in proper order i.e., x(0), x(1)…, x(7). Table 11.4 shows the shuffling of the input sequence has a well defined format.

 

Table 11.4 Computational complexity of DIT FFT algorithm compared to direction method

 

Table 11.5 Shuffling of the input sequence

 

From Table 11.4, x(1) ∫ x(001) is to be placed ...