Bit-reversal permutation: Difference between revisions

Revision as of 06:23, 12 October 2022

Revision as of 06:27, 12 October 2022

Line 30:

==Generalizations==

The generalization to [[radix]] <math>b</math> representations, for <math>b > 2</math>, and to <math>n=b^k</math>, is a '''digit-reversal permutation''', in which the base-<math>b</math> digits of the index of each element are reversed to obtain the permuted index. The same idea can also been generalized to [[mixed radix]] number systems. In such cases, withthe adigit-reversal permutation thatshould simultaneously reverses the digits of each item and the bases of the number system, so that each reversed digit remains within the range defined by its base.<ref>{{citation

| last = Elster | first = Anne C.

| contribution = Fast bit-reversal algorithms

| doi = 10.1109/ICASSP.1989.266624

| pages = 1099–1102

| publisher = {IEEE}

| title = IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '89, Glasgow, Scotland, May 23-26, 1989

| year = 1989}}</ref>

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.<ref>{{citation