Conversion of digit-reversed to bit-reversed order in FFT algorithms
Panos E. Papamichalis, C.S. Burrus · International Conference on Acoustics, Speech, and Signal Processing · 2003
Implementation of the FFT (fast Fourier transform) on currently available DSP (digital signal processing) devices is facilitated by hardware bit-reverse counters that are used for the unscrambling of the data. C.S. Burrus (1988) showed how these counters can also be used in the case of higher radix algorithms. The concept is generalized here to radices r/sub 1/ and r/sub 2/. It is shown that if r/sub 1/=r/sub 2//sup k/ a radix-r/sub 1/ FFT can be easily put in a digit-reversed order based on radix r/sub 2/. For instance, a radix-4 or radix-8 FFT can be put in a bit-reversed (i.e. radix-2) order without any extra computation or data movement.>