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

摘要

The author proposes bit-reversal unscrambling algorithms based on representing array indices as elements in GF(2/sup b/). These elements are sequenced through by counters implemented with integer shifts and bitwise exclusive-OR. A very simple algorithm, developed by applying these counters in a structure similar to the Gold-Rader algorithm, is shown to be less complex and significantly faster than the Gold-Rader (1969) algorithm. A second algorithm, constructed by using counters in GF(2/sup b/) to adapt an algorithm proposed by Evans (1987), eliminates the lookup tables required by the Evans algorithm while maintaining its speed advantages.