An efficient bit reversal permutation algorithm
Rami A. Al Na'mneh, Khalid Ahmad Darabkh · 2013
Bit-reversal routine is considered as an essential part in Fast Fourier transforms (FFT) and Fast Hartley Transform (FHT). Image transposition and generalized sorting of multidimensional arrays are other interesting applications of bit-reversal algorithms. In this paper, we propose an efficient bit-reversal permutation algorithm, namely the swapping algorithm, that has a time complexity of O(√n). Moreover, it performs n-n3/4swaps (or exchanges) which are lower than the well-known transpose algorithm that performs equation exchanges. We use a lookup table of size √n to perform the bit-reversal experimentally. The results show that our proposed algorithm outperforms the transpose algorithm. Furthermore, our proposed algorithm can be used efficiently in parallel systems since it consists of parallelizable steps.