雷德演算法（Bit-Reversal）原理與 C++ 實作：FFT 輸入重排關鍵步驟

背景：為什麼需要位元反轉？

快速傅立葉變換（FFT）輸出頻率係數順序為「倒位序」（bit-reversed order）。若在 FFT 前先將輸入資料重排為倒位序，FFT 輸出即為自然順序，省去後續重排步驟。雷德演算法即高效產生這種重排索引的方法。

核心原理：自然順序 vs 倒位序

設資料長度 N = 2^k。自然順序索引 0,1,2... 的二進位表示，下一個數 = 當前數 + 1（低位向高位進位）。倒位序索引則是將二進位位元反轉：

N=8 (3 bits)        自然順序 → 倒位序 (二進位反轉)
0 (000)    →    0 (000)
1 (001)    →    4 (100)
2 (010)    →    2 (010)
3 (011)    →    6 (110)
4 (100)    →    1 (001)
5 (101)    →    5 (101)
6 (110)    →    3 (011)
7 (111)    →    7 (111)

遞迴產生規則

已知當前倒位序數 J，求下一個：

1. 從最高位（K = N/2）開始檢查
2. 若 K > J：最高位為 0 → 加 K 置 1，得到下一個
3. 若 K ≤ J：最高位為 1 → 減 K 置 0，繼續檢查次高位（K/2），直到某位為 0 為止，將該位置 1

C++ 參考實作

#include <iostream>
#include <cstdio>
using namespace std;

int main() {
    int N = 8;
    int x[16] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    int y[16] = {0};

    // 產生倒位序索引並同步交換資料（就地重排）
    for (int j = 0, i = 0; i < N - 1; i++) {
        if (i < j) {  // 交換
            swap(x[i], x[j]);
        }
        int k = N / 2;
        while (j >= k) {  // 處理進位
            j -= k;
            k /= 2;
        }
        j += k;  // 更新 j 為下一個倒位序數
    }

    for (int i = 0; i < N; ++i)
        printf("%2d %2d\n", i, x[i]);  // 驗證重排結果
    return 0;
}

輸出驗證

 0  0
 1  4
 2  2
 3  6
 4  1
 5  5
 6  3
 7  7

索引 i 對應重排後位置 x[i]，符合位元反轉映射表。

工程應用提示

• 通常整合於 FFT 迴圈內，避免額外記憶體與迴圈
• 大型 FFT（N > 1024）可預計算倒位序索引表
• 嵌入式系統常用查表法換取速度

總結

雷德演算法以 O(N) 時間、O(1) 額外空間完成就地位元反轉重排，是 FFT 工程落地的標準組件。理解其「二進位減法模擬反向進位」的本質，有助於除錯與優化。