Bit-reversal permutation

In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2k 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 representations 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, so repeating the same permutation twice returns to the original ordering on the items. In applied mathematics, a bit-reversal permutation is a permutation of a sequence of n items, where n = 2k 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 representations 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, so repeating the same permutation twice returns to the original ordering on the items. Consider the sequence of eight letters abcdefgh. Their indexes are the binary numbers 000, 001, 010, 011, 100, 101, 110, and 111, which when reversed become 000, 100, 010, 110, 001, 101, 011, and 111.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 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 of size 2k, for k = 0, 1, 2, 3, ... are (sequence A030109 in the OEIS)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 0 2 1 3 gives 0 4 2 6, adding one gives 1 5 3 7, and concatenating these two sequences gives the length-8 permutation 0 4 2 6 1 5 3 7. The generalization to n = bm for an arbitrary integer b > 1 is a base-b digit-reversal permutation, in which the base-b (radix-b) digits of the index of each element are reversed to obtain the permuted index.A further generalization to arbitrary 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. 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 algorithm. The first of these extensions, called Efficient Ordering, operates on composite numbers, and it is based on decomposing the number into its prime components. The second extension, called EBR (Extended Bit-Reversal), 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 0 … n − 1 {displaystyle 0ldots n-1} in linear time. Successive numbers are separated in the permutation by at least ⌊ n / 4 ⌋ {displaystyle lfloor n/4 floor } positions. Bit reversal is most important for radix-2 Cooley–Tukey FFT algorithms, where the recursive stages of the algorithm, operating in-place, imply a bit reversal of the inputs or outputs. Similarly, mixed-radix digit reversals arise in mixed-radix Cooley–Tukey FFTs.