離散傅里葉變換

03-16

閱讀原文

預備知識　幺正矩陣，傅里葉變換（指數函數）

結論

　　對兩組有序數列 $f_0,f_1,dots,f_{N-1}$ 和 $g_0,g_2,dots, g_{N-1}$ ，正變換和逆變換分別為（註：工程上的定義常常是正變換沒有 $1/sqrt{N}$ 因子，逆變換的 $1/sqrt{N}$ 因子變為 $1/N$ ．這樣的好處是節省運算量．本書中使用的定義好處是變換為幺正變換，有保持歸一化的特點）．

$g_p = frac{1}{sqrt{N}}sum_{q=0}^{N-1} left(-frac{2pimathrm i}{N} p q ight) f_q$ 　　(1)

$f_q = frac{1}{sqrt{N}}sum_{p=0}^{N-1} left(frac{2pimathrm i}{N} p q ight) g_p$ 　　(2)

　　離散傅里葉變換（Discrete Fourier Transform）（DFT）是一個複數域的正交變換．快速傅里葉變換（FFT）的結果與離散傅里葉變換一樣，只是優化了演算法使程序運行更高效．

矩陣表示

　　把變換和逆變換用幺正矩陣 $mathbf F$ 和 $mathbf F^{-1}$ 來表示，令列矢量 $mathbf f = (f_0,f_1,dots,f_N)^T$ ， $mathbf g = (g_1,g_2,dots,g_N)^T$ ，變換和逆變換分別為

$mathbf g = mathbf F mathbf f qquad mathbf f = mathbf F^{-1} mathbf g$ 　　(3)

其中

（剩下部分見頂部的「閱讀原文」）