Bit-reversal permutation
Encyclopedia
In applied mathematics, a bit-reversal permutation is a permutation
of a sequence
with n = 2m (a power of two
) elements, defined by reversing the binary digits of the index (0 to n − 1) of each element. 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).
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. Mainly because of the importance of fast Fourier transform
(FFT) algorithms, numerous efficient O(n) in-place algorithms for bit-reversal and digit-reversal permutations have been devised.
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
of a sequence
Sequence
In mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
with n = 2m (a power of two
Power of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
) elements, defined by reversing the binary digits of the index (0 to n − 1) of each element. The generalization to n = bm for an arbitrary integer b > 1 is a base
Radix
In mathematical numeral systems, the base or radix for the simplest case is the number of unique digits, including zero, that a positional numeral system uses to represent numbers. For example, for the decimal system the radix is ten, because it uses the ten digits from 0 through 9.In any numeral...
-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
Composite number
A composite number is a positive integer which has a positive divisor other than one or itself. In other words a composite number is any positive integer greater than one that is not a prime number....
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).
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. Mainly because of the importance of fast Fourier transform
Fast Fourier transform
A fast Fourier transform is an efficient algorithm to compute the discrete Fourier transform and its inverse. "The FFT has been called the most important numerical algorithm of our lifetime ." There are many distinct FFT algorithms involving a wide range of mathematics, from simple...
(FFT) algorithms, numerous efficient O(n) in-place algorithms for bit-reversal and digit-reversal permutations have been devised.