Bit-reversal permutation

Bit-reversal permutation
Product of Gray code permutation and bit-reversal permutation (4-bit)

(The result permutes a natural ordered into a sequence ordered Hadamard matrix.)

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.[1][2][3][4][5][6]

References

  1. ^ B. Gold and C. M. Rader, Digital Processing of Signals (New York: McGraw–Hill, 1969).
  2. ^ Jeffrey J. Rodríguez, "An improved FFT digit-reversal algorithm," IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 37 (no. 8), pp. 1298–1300 (1989)
  3. ^ David M. W. Evans, "A second improved digit-reversal permutation algorithm for fast transforms," IEEE Trans. Acoustics, Speech, and Signal Processing, vol. 37 (no. 8), pp. 1288–1291 (1989)
  4. ^ Karp, Alan H., "Bit reversal on uniprocessors," SIAM Review 38 (1), 1–26 (1996)
  5. ^ Carter, Larry and Kang Su Gatlin, "Towards an optimal bit-reversal permutation program," Proc. 39th Ann. Symp. on Found. of Comp. Sci. (FOCS), 544–553 (1998).
  6. ^ Rubio, M., P. Gómez, and K. Drouiche, "A new superfast bit reversal algorithm," Intl. J. Adaptive Control and Signal Processing 16, 703–707 (2002)

Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Permutation — For other uses, see Permutation (disambiguation). The 6 permutations of 3 balls In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting (rearranging) objects or values.… …   Wikipedia

  • Cooley–Tukey FFT algorithm — The Cooley–Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N1N2 in terms of smaller DFTs… …   Wikipedia

  • Cooley-Tukey FFT algorithm — The Cooley Tukey algorithm, named after J.W. Cooley and John Tukey, is the most common fast Fourier transform (FFT) algorithm. It re expresses the discrete Fourier transform (DFT) of an arbitrary composite size N = N 1 N 2 in terms of smaller… …   Wikipedia

  • Cycles and fixed points — 16 bit Gray code permutation G multiplied with the bit reversal permutation B G has 2 fixed points, 1 2 cycle and 3 4 cycles B has 4 fixed points and 6 2 cycles GB has 2 fixed points and 2 7 cycles …   Wikipedia

  • Walsh matrix — In mathematics, a Walsh matrix is a specific square matrix, with dimensions a power of 2, the entries of which are +1 or 1, and the property that the dot product of any two distinct rows (or columns) is zero. The Walsh matrix was proposed by… …   Wikipedia

  • Evenness of zero — The number 0 is even. There are several ways to determine whether an integer is even or odd, all of which indicate that 0 is an even number: it is a multiple of 2, it is evenly divisible by 2, it is surrounded on both sides by odd integers, and… …   Wikipedia

  • Parity of zero — Zero objects, divided into two equal groups Zero is an even number. In other words, its parity the quality of an integer being even or odd is even. Zero fits the definition of even number : it is an integer multiple of 2, namely 0 × 2. As a… …   Wikipedia

  • Feistel cipher — In cryptography, a Feistel cipher is a symmetric structure used in the construction of block ciphers, named after the German IBM cryptographer Horst Feistel; it is also commonly known as a Feistel network. A large proportion of block ciphers use… …   Wikipedia

  • literature — /lit euhr euh cheuhr, choor , li treuh /, n. 1. writings in which expression and form, in connection with ideas of permanent and universal interest, are characteristic or essential features, as poetry, novels, history, biography, and essays. 2.… …   Universalium

  • Modified discrete cosine transform — The modified discrete cosine transform (MDCT) is a Fourier related transform based on the type IV discrete cosine transform (DCT IV), with the additional property of being lapped: it is designed to be performed on consecutive blocks of a larger… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”