Conversion of digit-reversed to bit-reversed order in FFT algorithms

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₁ and r₂. It is shown that if r₁=r₂^k a radix-r₁ FFT can be easily put in a digit-reversed order based on radix r₂. 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