Content deleted Content added
→Applications: Added reference Tag: Reverted |
|||
| (33 intermediate revisions by 12 users not shown) | |||
Line 1:
{{Short description|Permutation that reverses binary numbers}}
In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of ''n'' items, where ''n'' = 2<sup>''k''</sup> 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 representation]]s 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 (mathematics)|involution]], so repeating the same permutation twice returns to the original ordering on the items.▼
[[File:Hammersley set 2D.svg|thumb|A [[Hammersley set]] whose coordinates are the integers from 0 to 255 and their bit-reversals]]
▲In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of
Repeating the same permutation twice returns to the original ordering on the items, so the bit reversal permutation is an [[Involution (mathematics)|involution]].
This permutation can be applied to any sequence in [[linear time]] while performing only simple index calculations. It has applications in the generation of [[low-discrepancy sequence]]s and in the evaluation of [[fast Fourier transform]]s.
Line 7 ⟶ 11:
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 ''{{not a typo|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
{| class="wikitable" style="text-align: center;"
|-
* k = 1: 0 1▼
! <math>k</math> !! <math>n=2^k</math> !! permutation
* k = 2: 0 2 1 3▼
|-
* k = 3: 0 4 2 6 1 5 3 7▼
| 0 || 1 || 0
* k = 4: 0 8 4 12 2 10 6 14 1 9 5 13 3 11 7 15▼
|-
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 {{nowrap|0 2 1 3}} gives {{nowrap|0 4 2 6}}, adding one gives {{nowrap|1 5 3 7}}, and concatenating these two sequences gives the length-8 permutation {{nowrap|0 4 2 6 1 5 3 7}}.▼
|-
|-
|}
▲Each permutation in this sequence can be generated by concatenating two sequences of numbers: the previous permutation, with its values doubled, and the same sequence with each value increased by one.
▲Thus, for example doubling the length-4 permutation {{nowrap|0 2 1 3}} gives {{nowrap|0 4 2 6}}, adding one gives {{nowrap|1 5 3 7}}, and concatenating these two sequences gives the length-8 permutation {{nowrap|0 4 2 6 1 5 3 7}}.<ref name="karp"/>
==Generalizations==
The generalization to
| last = Elster | first = Anne C.
| contribution = Fast bit-reversal algorithms
| doi = 10.1109/ICASSP.1989.266624
| title = IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '89, Glasgow, Scotland, May 23-26, 1989
| year = 1989| 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 25 ⟶ 43:
| last2 = Ellis | first2 = John
| last3 = Mamakani | first3 = Khalegh
| last4 = Ruskey | first4 = Frank | author4-link = Frank Ruskey
| doi = 10.1016/j.ipl.2013.02.017
| issue = 10–11
Line 33 ⟶ 51:
| title = In-place permuting and perfect shuffling using involutions
| volume = 113
| year = 2013
| 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 ''
The second extension, called EBR (
==Applications==
Line 52 ⟶ 72:
| year = 1984| title-link = Symposium on Theory of Computing
| isbn = 978-0897911337
| doi-access = free
}}.</ref>
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 arithmetic|fixed-point binary representations]] of [[dyadic rational number]]s.
Bit-reversal permutations are often used in finding lower bounds on dynamic [[data structures]]. For example, subject to certain assumptions, the cost of looking up the integers between <math>0</math> and <math>n-1</math>, inclusive, in any [[binary search tree]] holding those values, is <math>\Omega(n \log n)</math> when those numbers are queried in bit-reversed order. This bound applies even to trees like [[splay trees]] that are allowed to rearrange their nodes between accesses.<ref>{{citation
| last1 =
| contribution =
| doi = 10.1109/SFCS.1986.28
| volume = 4▼
|
| title = 27th Annual Symposium on Foundations of Computer Science (sfcs 1986)
▲ | pages = 1-11
| contribution-url = https://
| year = 1989| title-link = Symposium on Foundations of Computer Science
▲ | contribution-url = https://musmat.org/wp-content/uploads/2020/06/05-Scott.pdf
| isbn = 0-8186-0740-8
}}.</ref>
Line 88 ⟶ 109:
| title = International Conference on Acoustics, Speech, and Signal Processing (ICASSP-90)
| volume = 3
| 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 99 ⟶ 121:
| title = Address generators for mapping arrays in bit-reversed order
| volume = 52
| year = 2004
| s2cid = 10043478
}}.</ref>
Significant attention has been given to improving the performance of bit-reversal operations within the field of high-performance computing. Developing architecture-aware algorithms is crucial for enabling optimal use of hardware and system software resources such as caches, TLBs, and multicore processors.<ref>{{citation
| last1 = Zhang | first1 = Zhao
| last2 = Zhang | first2 = Xiaodong
| doi = 10.1137/S1064827599359709
| issue = 6
| journal = SIAM Journal on Scientific Computing
| mr = 1856305
| pages = 2113–2134
| title = Fast bit-reversals on uniprocessors and shared-memory multiprocessors
| year = 2000}}</ref>
==References==
| |||