Fast Computational Algorithms for Bit Reversal

Radix—2 fast Fourier transform programs of the Gentleman-Sande type leave the transformed array in a scrambled order of frequencies. Unscrambling is accomplished by moving each element from its present location into a new location obtained by bit reversal. Bit reversal can be interpreted as an exchange of groups of bits symmetric with respect to a pivot. Two formulas are developed for simultaneous and sequential exchanging in place, with negligible auxiliary storage. Programs for one-step and sequential unscrambling were implemented. Binary unscrambling is useful to unscramble large arrays in peripheral storage. The one-step unscrambling program presented is more efficient than other programs available in the literature.