Fast bit-reversal algorithms based on index representations in GF(2/sup b/)
M.T. Orchard · 2003
The author develops bit-reversal unscrambling algorithms that are based on representing array indices as elements in GF(2/sup b/). The elements of GF(2/sup 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/sup 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/sup 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.>