作者：July、dznlong | 日期：2011年2月20日 | 參考：《The Scientist and Engineer's Guide to Digital Signal Processing》Steven W. Smith著
關於傅里葉變換，網上資料多枯燥抽象，公式堆砌讓人望而生畏。本文旨在通俗易懂地講透傅里葉變換，從由來到DFT、FFT全程實現，力求閱讀順暢、感性理解。
傅里葉變換是一種線性積分變換，核心思想：將信號從時域轉換到頻域，或兩者相互轉換。法國學者Joseph Fourier（1768-1830）於1807年系統提出，故以其命名。
| 變體 | 時域 | 頻域 | 說明 |
|---|---|---|---|
| 連續傅里葉變換 (CFT) | 連續 | 連續 | 非周期信號，積分形式 |
| 傅里葉級數 (FS) | 連續 | 離散 | 周期信號，級數形式 |
| 離散時域傅里葉變換 (DTFT) | 離散 | 連續(周期) | 時域離散化，頻域周期化 |
| 離散傅里葉變換 (DFT) | 離散 | 離散 | 時頻雙離散，計算機實現基礎 |
關鍵規律：時域離散 ⇔ 頻域周期；時域連續 ⇔ 頻域非周期。DFT是DTFT在頻域採樣的特例，工程上通過FFT高效計算。
Fourier 1807年主張：任何連續周期信號皆可由正弦曲線組合而成。拉格朗日強烈反對，認為無法表示方波等帶棱角信號。50年後證實：雖無法精確表示，但可任意逼近，能量差趨近於零。
分解信號方法無窮多，但正弦波具備保真度：正弦信號經線性系統輸出仍為正弦波，僅幅度相位改變，頻率波形不變。此特性唯正弦波擁有，故成為分解基礎。
DFT將有限長離散信號 x[n] 表示為正弦波求和：
X[k] = Σ x[n] * cos(2πkn/N) - j Σ x[n] * sin(2πkn/N)
直接計算複雜度 O(N²)，FFT 可優化至 O(N log N)，使DFT在信號處理領域極具實用價值。
拋物線高度公式 h = vt - ½gt² 求時間 t 需開平方，若高度過大會出現負數開方。Cardano 首次使用，Gauss 形式化定義複數：實部 + 虛部，虛數單位用 j 表示（電工學中 i 表電流）。
向量可用複數表示：A = 2+6j, B = -4-1.5j, C = 3-7j
模 M = √(a²+b²)，相位 θ = arctan(b/a)
歐拉公式：ejθ = cosθ + j sinθ
由此得復數指數形式：a + jb = M ejθ
指數形式極大簡化乘除運算：
M1ejθ1 × M2ejθ2 = M1M2 ej(θ1+θ2) M1ejθ1 ÷ M2ejθ2 = (M1/M2) ej(θ1-θ2)
將問題轉為複數形式運算，最後轉回實數結果。兩種用法：簡單替換（向量表示）與複數形式DFT（FFT基礎）。
利用歐拉公式，DFT 統一為：
X[k] = Σ x[n] * e-j2πkn/N (k = 0,1,...,N-1)
逆變換：
x[n] = (1/N) Σ X[k] * ej2πkn/N
此形式緊湊優雅，是 FFT 算法的基礎。下篇將深入講解 FFT 原理與實現。
