離散傅里葉變換矩陣

離散傅立葉變換矩陣是將離散傅立葉變換以矩陣乘法來表達的一種表示式。

定義[編輯]

N點的離散傅立葉變換可以用一個 $n\times m$ 的矩陣乘法來表示，即 $X=Wx$ ，其中 $x$ 是原始的輸入信號， $X$ 是經過離散傅立葉變換得到的輸出信號。一個 $n\times n$ 的變換矩陣 $W$ 可以定義成 $W=(\omega ^{ij})_{i,j=0,\ldots ,N-1}/{\sqrt {N}}$ ，或等效如下：

W={\frac {1}{\sqrt {N}}}{\begin{bmatrix}1&1&1&1&\cdots &1\\1&\omega &\omega ^{2}&\omega ^{3}&\cdots &\omega ^{N-1}\\1&\omega ^{2}&\omega ^{4}&\omega ^{6}&\cdots &\omega ^{2(N-1)}\\1&\omega ^{3}&\omega ^{6}&\omega ^{9}&\cdots &\omega ^{3(N-1)}\\\vdots &\vdots &\vdots &\vdots &&\vdots \\1&\omega ^{N-1}&\omega ^{2(N-1)}&\omega ^{3(N-1)}&\cdots &\omega ^{(N-1)(N-1)}\\\end{bmatrix}},

其中 $\omega$ 是 $1$ 的 $n$ 次方根的主值（primitive nth root of unity）,大小為 $e^{\frac {-2\pi i}{N}}$ 。需要注意的是在總和前面的正規化因數 ${\frac {1}{\sqrt {N}}}$ ，還有 $\omega$ 中指數的正負號是依據慣例，並且會因為處理的方法有所不同。以下所有的討論考慮到大多數的細節變動且不論是否為一般慣例均適用之。唯一重要的是，正變換和逆變換有相反的指數正負號標誌，而其正規化因數乘積為 ${\frac {1}{N}}$ 。然而，這裡為了使得最後的離散傅立葉變換矩陣結果正規化所選擇的因數，在許多情況下都是通用的。

快速傅立葉變換演算法利用矩陣的對稱性與W的周期性，以減少乘法所需要的時間（把計算複雜度從 $O(N^{2})$ 降為 $O(N\log N)$ ）。類似的方法也可適用於其他矩陣乘法如阿達馬矩陣和沃爾什矩陣。

特殊情況[編輯]

3點的離散傅立葉變換具有特殊的意義。例如：Charles LeGeyt Fortescue（英語：Charles LeGeyt Fortescue）於1918年所發表的對稱分量變換（Symmetrical Components Transform, SCT），它定義了三相平衡（three phase balance），即3點離散傅立葉變換可分解成一個直流成份，以及兩個交流成份（一個是順時針相位，另一個為逆時針相位）。

例子[編輯]

兩點離散傅立葉變換矩陣[編輯]

兩點的離散傅立葉變換是一個很簡單的例子，其第一列代表是直流成份（總和）和第二列是交流成份（差異）。

{\begin{bmatrix}1&1\\1&-1\end{bmatrix}}/{\sqrt {2}}

第一列處理總和的部份，第二列處理相差的部份。因數 $1/{\sqrt {2}}$ 致使整個矩陣規一化（見下文）。

四點離散傅立葉變換矩陣[編輯]

四點的離散傅立葉變換矩陣如下：

{\frac {1}{2}}{\begin{bmatrix}1&1&1&1\\1&-i&(-i)^{2}&(-i)^{3}\\1&(-i)^{2}&(-i)^{4}&(-i)^{6}\\1&(-i)^{3}&(-i)^{6}&(-i)^{9}\end{bmatrix}}.

八點離散傅立葉變換矩陣[編輯]

八點的離散傅立葉變換矩陣如下：

W={\frac {1}{\sqrt {8}}}{\begin{bmatrix}\omega ^{0}&\omega ^{0}&\omega ^{0}&\ldots &\omega ^{0}\\\omega ^{0}&\omega ^{1}&\omega ^{2}&\ldots &\omega ^{7}\\\omega ^{0}&\omega ^{2}&\omega ^{4}&\ldots &\omega ^{14}\\\omega ^{0}&\omega ^{3}&\omega ^{6}&\ldots &\omega ^{21}\\\omega ^{0}&\omega ^{4}&\omega ^{8}&\ldots &\omega ^{28}\\\omega ^{0}&\omega ^{5}&\omega ^{10}&\ldots &\omega ^{35}\\\vdots &&\vdots &\ddots &\vdots \\\omega ^{0}&\omega ^{7}&\omega ^{14}&\ldots &\omega ^{49}\\\end{bmatrix}}

其中

\omega =e^{-{\frac {2\pi i}{8}}}={\frac {1}{\sqrt {2}}}-{\frac {i}{\sqrt {2}}}

以下用圖片來解說離散傅立葉變換的矩陣乘法概念：

圖中實部（餘弦波）是由實線代表，虛部（正弦波）由虛線代表。最上面一行全為1，（透過乘上 $1/{\sqrt {8}}$ 來規一化），因此這個部份代表輸入信號的直流分量。下一行是8個負一次循環的複指數取樣（samples of negative one cycle of complex exponential），即分頻（fractional frequency）為−1/8倍頻率的信號。因此，這一行代表在分頻+1/8的信號強度。再下一行是8個負二次循環的複指數取樣，所以它代表-1/4倍的分頻。因此，這一行代表在分頻+1/4的信號強度。以下總結了八點離散傅立葉變換代表的意義，依行排序，以分頻表示：

0代表直流信號成份
-1/8代表分頻為+1/8 的信號強度
-1/4代表分頻為+1/4 的信號強度
-3/8代表分頻為+3/8 的信號強度
-1/2代表分頻為+1/2 的信號強度
-5/8代表分頻為+5/8 的信號強度
-3/4代表分頻為+3/4 的信號強度
-7/8代表分頻為+7/8 的信號強度

等效上最後一行，可以當作是分頻為+1/8即代表分頻-1/8的信號強度。如此一來，則可以說這個矩陣的上面列是信號的正頻率部份的強度而下面列是信號負頻率部份的強度。

規一化變換（unitary transform）[編輯]

離散傅立葉變換（或可能是透過適當的尺度選擇）是一個規一化的變換，即符合能量保留（preserves energy）。可以達到規一化的合適尺度是 $1/{\sqrt {N}}$ ，這使得能量物理意義上跟在傅立葉定義上是一樣的，即滿足傅立葉變換（帕塞瓦爾定理）。（其他未規一化的尺度，也普遍被使用以方便計算；例如，摺積（摺積定理）需較簡單的形式與尺度選擇，詳述於離散傅立葉變換條目中）。