An in-order, in-place radix-2 FFT

Most Cooley-Tukey, in-place Fast Fourier Transform (FFT) algorithms result in the output being permuted or scrambled in order. For a radix-2 FFT, this order can be easily found by reversing the order of the bits of the address, and the unscrambler is called a bit-reversed counter. In some machines, this unscrambling takes from 10% to 50% of the total execution time. This paper presents an in-place, radix-2 FFT that does the unscrambling while the FFT is being calculated rather than as a separate process. The theoretical framework is based on index maps [1] and ideas used on the in-place, in-order prime factor FFT (PFA) [2]. The non-scrambled algorithm is implemented in FORTRAN. The size of the program is essentially the same as the regular radix-2 FFT with its bit-reversed counter.