Bit-reversal permutation: Difference between revisions

Revision as of 06:40, 17 March 2023

Latest revision as of 21:21, 22 July 2025

(6 intermediate revisions by 5 users not shown)

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, the digit-reversal permutation should simultaneously reversesreverse 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

Line 36:

| pages = 1099–1102

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

| year = 1989}}</ref>| s2cid = 15028026

}}</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

Line 50 ⟶ 51:

| title = In-place permuting and perfect shuffling using involutions

| volume = 113

| year = 2013}}.</ref>| s2cid = 14672841

| arxiv = 1204.1958

}}.</ref>

There are two extensions of the bit-reversal permutation to sequences of arbitrary length. These extensions coincide with bit-reversal for sequences whose length is a power of 2, and their purpose is to separate adjacent items in a sequence for the efficient operation of the [[Kaczmarz method|Kaczmarz algorithm]]. The first of these extensions, called ''efficient ordering'',<ref>{{citation|last1=Herman|first1=Gabor T.|author1-link=Gabor Herman|title=Fundamentals of Computerized Tomography|url=https://archive.org/details/fundamentalscomp00herm|url-access=limited|date=2009|publisher=Springer|___location=London|isbn=978-1-85233-617-2|page=[https://archive.org/details/fundamentalscomp00herm/page/n216 209]|edition=2nd}}</ref> operates on composite numbers, and it is based on decomposing the number into its prime components.

The second extension, called EBR (extended bit-reversal), is similar in spirit to bit-reversal. Given an array of size <math>n</math>, EBR fills the array with a permutation of the numbers in the range <math>0\ldots n-1</math> in linear time. Successive numbers are separated in the permutation by at least <math>\lfloor n/4\rfloor</math> positions.<ref>{{citation|last1=Gordon|first1=Dan|title=A derandomization approach to recovering bandlimited signals across a wide range of random sampling rates|journal=Numerical Algorithms|volume=77|issue=4|pages=1141–1157|date=June 2017|doi=10.1007/s11075-017-0356-3|s2cid=254889989 }}</ref>

==Applications==

Line 78 ⟶ 81:

| contribution = Lower Bounds for Accessing Binary Search Trees With Rotations

| doi = 10.1109/SFCS.1986.28

| pages = 61-7061–70

| title = 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)

| contribution-url = https://ieeexplore.ieee.org/abstract/document/4568196

| year = 1989| title-link = Symposium on Foundations of Computer Science

| isbn = 0-8186-0740-8

Line 106 ⟶ 109:

| title = International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90)

| volume = 3

| year = 1990| s2cid = 122373780

| year = 1990}}.</ref> Because bit-reversal permutations may be repeated multiple times as part of a calculation, it may be helpful to separate out the steps of the algorithm that calculate index data used to represent the permutation (for instance, by using the doubling and concatenation method) from the steps that use the results of this calculation to permute the data (for instance, by scanning the data indexes in order and performing a swap whenever the swapped ___location is greater than the current index, or by using more sophisticated [[Vectored I/O|vector scatter–gather operations]]).<ref name="karp"/>

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.<ref name="karp"/><ref name="cg98">{{citation|last1=Carter|first1=Larry|first2=Kang Su|last2=Gatlin|contribution=Towards an optimal bit-reversal permutation program|title=Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS)|pages=544–553|year=1998|doi=10.1109/SFCS.1998.743505|title-link=Symposium on Foundations of Computer Science|isbn=978-0-8186-9172-0|citeseerx=10.1.1.46.9319|s2cid=14307262 }}.</ref> An alternative to these techniques is special computer hardware that allows memory to be accessed both in normal and in bit-reversed order.<ref>{{citation

| last1 = Harley | first1 = T. R.

| last2 = Maheshwaramurthy | first2 = G. P.

Line 117 ⟶ 121:

| title = Address generators for mapping arrays in bit-reversed order

| volume = 52

| year = 2004}}| bibcode = 2004ITSP.</ref>..52.1693H

| s2cid = 10043478

}}.</ref>

TheSignificant performanceattention improvementhas ofbeen bit-reversalsgiven into bothimproving uniprocessorthe andperformance multiprocessorsof hasbit-reversal beenoperations paidwithin athe seriousfield attention inof high-performance computing fields. BecauseDeveloping architecture-aware algorithmalgorithms developmentis cancrucial bestfor utilizeenabling optimal use of hardware and system software resources, includingsuch as caches, TLBTLBs, and multicores, significantly accelerating themulticore computationprocessors.<ref>{{citation

| last1 = Zhang | first1 = Zhao

| last2 = Zhang | first2 = Xiaodong