Bit-reversal permutation: Difference between revisions

Revision as of 16:26, 9 October 2021

Revision as of 21:01, 7 May 2022

Line 1:

[[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 ''<math>n''</math> items, where ''<math>n''&nbsp;=&nbsp;2<sup>''^k''</supmath> is a [[power of two]]. It is defined by indexing the elements of the sequence by the numbers from <math>0</math> to ''<math>n''&nbsp;&minus;&nbsp;-1</math>, andrepresenting theneach reversingof thethese numbers by its [[binary representation]]s of each of these numbers (padded soto that each of these binary numbers hashave length exactly&nbsp;'' <math>k''</math>)., Eachand itemmapping iseach then mappeditem to the newitem positionwhose givenrepresentation by this reversed value. The bit reversal permutation is an [[Involution (mathematics)|involution]], so repeatinghas the same permutationbits twice returns toin the originalreversed ordering on the itemsorder.

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 8 ⟶ 10:

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 ofon size 2<supmath>''n=2^k''</supmath> items, for ''<math>k''&nbsp;=&nbsp;0, 1, 2, 3, ...\dots</math>, are

* k = 0: 0

* k = 1: 0 1

Line 19 ⟶ 21:

==Generalizations==

The generalization to ''n''&nbsp;=&nbsp;''b''[[radix]] <supmath>''m''b</supmath> representations, for an<math>b arbitrary> integer2</math>, ''and to <math>n=b''&nbsp;^k</math>&nbsp;1, is a [[radix|base]]-''b'' '''digit-reversal permutation''', in which the base-''<math>b'' (radix-''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, with a permutation that simultaneously reverses the digits of each item and the bases of the number system.

A further generalization to arbitrary [[composite number|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.<ref>{{citation

Line 38 ⟶ 39:

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>{{cite book|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),<ref>{{cite journal|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}}</ref> 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.

==Applications==