Bit-reversal permutation

In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2k is a power of two. It is defined by indexing the elements of the sequence by the numbers from 0 to n − 1 and then reversing the binary representations of each of these numbers (padded so that each of these binary numbers has length exactly k). Each item is then mapped to the new position given by this reversed value. The bit reversal permutation is an involution, so repeating the same permutation twice returns to the original ordering on the items.

Example

Consider the sequence of eight letters abcdefgh. Their indexes are the binary numbers 000, 001, 010, 011, 100, 101, 110, and 111, which when reversed become 000, 100, 010, 110, 001, 101, 011, and 111. Thus, the letter a in position 000 is mapped to the same position (000), the letter b in position 001 is mapped to the fifth position (the one numbered 100), etc., giving the new sequence aecgbfdh. Repeating the same permutation on this new sequence returns to the starting sequence.

Writing the index numbers in decimal (but, as above, starting with position 0 rather than the more conventional start of 1 for a permutation), the bit-reversal permutations of size 2n, for n = 0, 1, 2, 3, ... are

0
0 1
0 2 1 3
0 4 2 6 1 5 3 7
0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15

(sequence A030109 in the OEIS)
Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, doubled, and the same sequence with each value increased by one. Thus, for example doubling the length-4 permutation 0 2 1 3 gives 0 4 2 6, adding one gives 1 5 3 7, and concatenating these two sequences gives the length-8 permutation 0 4 2 6 1 5 3 7.

Generalizations

The generalization to n = bm for an arbitrary integer b > 1 is a base-b digit-reversal permutation, in which the base-b (radix-b) digits of the index of each element are reversed to obtain the permuted index. A further generalization to arbitrary composite sizes is a mixed-radix digit reversal (in which the elements of the sequence are indexed by a number expressed in a mixed radix, whose digits are reversed by the permutation).

Permutations that generalize the bit-reversal permutation by reversing contiguous blocks of bits within the binary representations of their indices can be used to interleave two equal-length sequences of data in-place.[1]

Applications

Bit reversal is most important for radix-2 Cooley–Tukey FFT algorithms, where the recursive stages of the algorithm, operating in-place, imply a bit reversal of the inputs or outputs. Similarly, mixed-radix digit reversals arise in mixed-radix Cooley–Tukey FFTs.[2]

The bit reversal permutation has also been used to devise lower bounds in distributed computation.[3]

The Van der Corput sequence, a low-discrepancy sequence of numbers in the unit interval, is formed by reinterpreting the indexes of the bit-reversal permutation as the fixed-point binary representations of dyadic rational numbers.

Algorithms

Mainly because of the importance of fast Fourier transform algorithms, numerous efficient algorithms for applying a bit-reversal permutation to a sequence have been devised.[4]

Because the bit-reversal permutation is an involution, it may be performed easily in place (without copying the data into another array) by swapping pairs of elements. In the random-access machine commonly used in algorithm analysis, a simple algorithm that scans the indexes in input order and swaps whenever the scan encounters an index whose reversal is a larger number would take perform a linear number of data moves.[5] However, computing the reversal of each index may take a non-constant number of steps. Alternative algorithms can perform a bit reversal permutation in linear time while using only simple index calculations.[6]

Another consideration that is even more important for the performance of these algorithms is the effect of the memory hierarchy on running time. Because of this effect, more sophisticated algorithms that consider the block structure of memory can be faster than this naive scan.[4][5] An alternative to these techniques is special computer hardware that allows memory to be accessed both in normal and in bit-reversed order.[7]

References

  1. ↑ Yang, Qingxuan; Ellis, John; Mamakani, Khalegh; Ruskey, Frank (2013), "In-place permuting and perfect shuffling using involutions", Information Processing Letters, 113 (10-11): 386–391, doi:10.1016/j.ipl.2013.02.017, MR 3037467.
  2. ↑ B. Gold and C. M. Rader, Digital Processing of Signals (New York: McGraw–Hill, 1969).
  3. ↑ Frederickson, Greg N.; Lynch, Nancy A. (1984), "The impact of synchronous communication on the problem of electing a leader in a ring" (PDF), Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing (STOC '84), pp. 493–503, doi:10.1145/800057.808719.
  4. 1 2 Karp, Alan H. (1996), "Bit reversal on uniprocessors", SIAM Review, 38 (1): 1–26, doi:10.1137/1038001, MR 1379039. Karp surveys and compares 30 different algorithms for bit reversal, developed between 1965 and the 1996 publication of his survey.
  5. 1 2 Carter, Larry; Gatlin, Kang Su (1998), "Towards an optimal bit-reversal permutation program", Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 544–553, doi:10.1109/SFCS.1998.743505.
  6. ↑ Jeong, Jechang; Williams, W.J. (1990), "A fast recursive bit-reversal algorithm", International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90), 3, pp. 1511–1514, doi:10.1109/ICASSP.1990.115695.
  7. ↑ Harley, T. R.; Maheshwaramurthy, G. P. (2004), "Address generators for mapping arrays in bit-reversed order", IEEE Transactions on Signal Processing, 52 (6): 1693–1703, doi:10.1109/TSP.2004.827148.
This article is issued from Wikipedia - version of the 12/11/2014. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.