Fast bit-reversal algorithms based on index representations in GF(2 b)

The author develops bit-reversal unscrambling algorithms that are based on representing array indices as elements in GF(2^b). The elements of GF(2^b) are sequenced through by counters that use integer shifts and bitwise exclusive-OR, operations available in C and in all assembly languages. First, a very simple algorithm that applies GF(2^b) counters in a structure similar to that of the popular Gold-Rader bit-reversal unscrambler is proposed. The resulting algorithm is shown to be less complex and significantly faster than the Gold-Rader algorithm. Then a recent bit-reversal algorithm due to D.M.W. Evans (IEEE Trans. Acoust. Speech, Signal Proc., vol.ASSP-35, p. 1120-5, 1987) is adapted to use GF(2^b) counters. The adapted algorithm eliminates the lookup tables required by the Evans algorithm and is shown to be faster than that algorithm on many computer architectures