= Bit-reversal permutation
{title2=$\operatorname{rev}_m(j)$}
The <bit-reversal permutation> of $\{0,\ldots,2^m-1\}$ writes each index using exactly $m$ <binary digits>, reverses those digits, and interprets the result as another index. Leading zeros matter. Reversing twice restores the original index, so this <permutation> is an <involution>.
For $m=3$, the index order becomes $0,4,2,6,1,5,3,7$: for example, $3=011_2$ maps to $110_2=6$. It occurs naturally in radix-two <Fast Fourier transform> implementations. Repeatedly separating even from odd indices consumes the low-order bits first; traversing the resulting recursion tree reverses the order in which the index bits are read. Some implementations permute inputs, others permute outputs, and other layouts avoid an explicit reversal. The <discrete Fourier transform> itself is independent of this storage choice.<Notes on the FFT by C. Sidney Burrus>[radix-two decimation and digit-reversed ordering]{ref}
Back to article page
