A new efficient computational algorithm for bit reversal mapping
Karim Drouiche · IEEE Transactions on Signal Processing · 2001
In this correspondence, we present a new bit reversal algorithm that outperforms the existing ones. The bit reversal technique is involved in the fast fourier transform (FFT) technique, which is widely used in computer-based numerical techniques for solving numerous problems. The new approach for computing the bit reversal is based upon a pseudo semi-group homomorphism property. The surprising thing is that this property is almost trivial to prove, but at the same time, it also leads to a very efficient algorithm, which we believe to be the best with only O(N) operations and optimal constant, i.e. unity.