Bit-reversal permutation: Difference between revisions

Revision as of 06:39, 14 February 2021

Revision as of 06:43, 14 February 2021

Line 1:

In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of ''n'' items, where ''n''&nbsp;=&nbsp;2^''k'' is a [[power of two]]. It is defined by indexing the elements of the sequence by the numbers from 0 to ''n''&nbsp;&minus;&nbsp;1 and then reversing the [[binary representation]]s of each of these numbers (padded so that each of these binary numbers has length exactly&nbsp;''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<ref name=":0" />.

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.