經典算法研究：從頭到尾徹底理解傅里葉變換算法（下）

作者：July、dznlong | 日期：2011年2月22日 | 接上篇繼續講解複數形式DFT與FFT實現

前期回顧

上篇覆蓋了傅里葉變換由來、實數形式DFT。本篇重點講解複數、複數形式DFT，並引入FFT快速算法。

第三章：複數深度解析（續）

複數極坐標表示

複平面上：橫軸實部，縱軸虛部。向量模 M = √(a²+b²)，相位 θ = arctan(b/a)。

直角轉極坐標：

a = M cosθ,  b = M sinθ
M = √(a²+b²),  θ = arctan(b/a)

歐拉公式與指數形式

歐拉公式：e^jx = cos x + j sin x

泰勒級數證明：

ejx = 1 + jx + (jx)²/2! + (jx)³/3! + ...
      = (1 - x²/2! + x⁴/4! - ...) + j(x - x³/3! + x⁵/5! - ...)
      = cos x + j sin x

復數指數形式：a + jb = M e^jθ

指數形式乘除極簡單：

A × B = MAMB ej(θA+θB)
A ÷ B = (MA/MB) ej(θA-θB)

第四章：複數形式離散傅里葉變換

從實數DFT到複數DFT

實數DFT需分別計算餘弦、正弦係數，複數形式統一為：

X[k] = Σn=0N-1 x[n] e-j2πkn/N

其中 x[n] 為實數時，X[k] 具共軛對稱性：X[N-k] = X*[k]

DFT 矩陣形式

令 W_N = e^-j2π/N，則 DFT 可寫為矩陣乘法：

[X] = [W] [x]

其中 [W] 為 N×N 霍爾德矩陣，對稱且正交。

第五章：快速傅里葉變換 (FFT)

FFT 核心思想：分治與蝶形運算

Cooley-Tukey 算法將 N 點 DFT 分解為兩個 N/2 點 DFT：

• 偶數索引點 DFT
• 奇數索引點 DFT

遞歸分解直到 2 點 DFT，最終合併。複雜度從 O(N²) 降至 O(N log N)。

基-2 FFT 流程圖解

以 N=8 為例：

1. 位倒序重排
2. 級聯蝶形運算（log₂N 級）
3. 每級 N/2 個蝶形單元

蝶形運算基本單元：

X = A + Wk B
Y = A - Wk B

FFT 代碼框架（偽代碼）

void FFT(complex x[], int N) {
    // 1. 位倒序排列
    bitReverse(x, N);
    
    // 2. 級聯蝶形運算
    for (int stage = 1; stage <= log2(N); stage++) {
        int step = 1 << stage;
        int half = step >> 1;
        complex w_step = exp(-j * 2*PI / step);
        
        for (int k = 0; k < N; k += step) {
            complex w = 1;
            for (int j = 0; j < half; j++) {
                complex u = x[k+j];
                complex v = w * x[k+j+half];
                x[k+j] = u + v;
                x[k+j+half] = u - v;
                w *= w_step;
            }
        }
    }
}

總結

本系列從傅里葉變換歷史由來講起，經實數DFT、複數理論、歐拉公式，推導至複數DFT與FFT算法。FFT 以分治策略將 O(N²) 優化為 O(N log N)，奠定現代數字信號處理基石。理解關鍵在於：正弦波保真特性 → 複數指數形式 → 分治蝶形運算 三大核心環節。