Bit-reversal (order)

The fixed input reordering, a byproduct of splitting by successive bits, that the FFT's recursion needs.

Bit-reversal is the fixed reordering of an FFT's input in which the sample originally at index $i$ moves to the position whose binary representation is $i$ 's bits read backward. It is applied once, up front, before any butterfly runs, and is a direct byproduct of repeatedly splitting the input by even and odd index.

Examples

For $N=8$ , index $1$ (binary $001$ ) moves to index $4$ (binary $100$ ) under bit-reversal.