Bit-reversal permutation: Difference between revisions

Revision as of 16:52, 16 October 2020

Revision as of 18:47, 17 October 2020

Line 37:

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 ''n'', 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==