Bit-Reversal Permutation in FFT Algorithms

A bit-reversal permutation is a data reordering technique where the position of each element in an array of size \(N = 2^k\) is swapped with the index obtained by reversing the binary digits of its original position. This permutation is a fundamental requirement in radix-2 Fast Fourier Transform (FFT) implementations, particularly the Cooley-Tukey algorithm, because it enables in-place computation, eliminates the need for auxiliary memory, and aligns recursively divided sub-problems with the hardware’s sequential memory access.

What is a Bit-Reversal Permutation?

In an array of length \(N = 2^k\), each index can be represented as a \(k\)-bit binary number. A bit-reversal permutation maps the element at index \(i\) to a new index \(j\), where the binary representation of \(j\) is the exact mirror image of the binary representation of \(i\).

For an array of size \(N = 8\) (\(k = 3\) bits), the mapping works as follows:

• Index 0 (000₂) \(\rightarrow\) 000₂ = Index 0
• Index 1 (001₂) \(\rightarrow\) 100₂ = Index 4
• Index 2 (010₂) \(\rightarrow\) 010₂ = Index 2
• Index 3 (011₂) \(\rightarrow\) 110₂ = Index 6
• Index 4 (100₂) \(\rightarrow\) 001₂ = Index 1
• Index 5 (101₂) \(\rightarrow\) 101₂ = Index 5
• Index 6 (110₂) \(\rightarrow\) 011₂ = Index 3
• Index 7 (111₂) \(\rightarrow\) 111₂ = Index 7

Indices that are binary palindromes (such as 0, 2, 5, and 7 in a 3-bit space) remain in their original positions, while the remaining pairs (1 and 4, 3 and 6) swap places.

Why It Is Essential for the Fast Fourier Transform

The standard Discrete Fourier Transform (DFT) requires \(O(N^2)\) operations. The Cooley-Tukey FFT reduces this complexity to \(O(N \log N)\) by applying a divide-and-conquer strategy, recursively splitting an \(N\)-point transform into two \(N/2\)-point transforms: one containing the even-indexed elements and the other containing the odd-indexed elements.

1. Binary Nature of Decimation

In Decimation-in-Time (DIT) FFT, the first level of division separates elements based on whether their index is even or odd—determined strictly by the least significant bit (LSB) being 0 or 1. The second level divides those subsets based on the second-least significant bit, and this process continues until base-case sub-transforms of size 2 are reached.

Because the algorithm divides the data from the least significant bit to the most significant bit, the final order of inputs required at the base level corresponds to reading the original index bits in reverse order (from LSB to MSB).

2. Enabling In-Place Computation

Without bit-reversal permutation, performing an FFT would require allocating temporary arrays at each recursive stage to hold the split even and odd sequences, consuming \(O(N)\) auxiliary space.

By applying a bit-reversal permutation to the input array upfront, the data is pre-arranged into the exact order needed for the base-level computations. The algorithm can then execute its “butterfly” operations iteratively from the bottom up, overwriting the input array in place with \(O(1)\) auxiliary memory overhead.

3. Dual Role in Decimation-in-Frequency (DIF)

While Decimation-in-Time (DIT) algorithms take bit-reversed inputs and produce naturally ordered outputs, Decimation-in-Frequency (DIF) algorithms take naturally ordered inputs and produce bit-reversed outputs. In DIF implementations, the bit-reversal permutation is applied at the end of the transform to restore the frequency-domain coefficients to standard sequential order.