Bit-reversal permutation: Difference between revisions

Revision as of 18:21, 27 November 2019

Revision as of 23:23, 27 November 2019

Line 1:

In applied mathematics, a '''bit-reversal permutation''' is a [[permutation]] of a [[sequence]] of ''n'' items, where ''n'' = 2^''k'' 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.

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.

==Example==