離散傅立葉轉換

離散傅立葉轉換（英語：Discrete Fourier Transform，縮寫為DFT），是傅立葉轉換在時域和頻域上都呈離散的形式，將信號的時域採樣轉換為其DTFT的頻域採樣。

在形式上，轉換兩端（時域和頻域上）的序列是有限長的，而實際上這兩組序列都應當被認為是離散週期信號的主值序列。即使對有限長的離散信號作DFT，也應當將其看作其週期延拓的轉換。在實際應用中通常採用快速傅立葉轉換計算DFT。

定義

對於$N$點序列$\left\{x[n]\right\}_{0\leq n<N}$，它的離散傅立葉轉換（DFT）為

${\hat {x}}[k]=\sum _{n=0}^{N-1}e^{-i{\frac {2\pi }{N}}nk}x[n]\qquad k=0,1,\ldots ,N-1.$

其中$e$是自然對數的底數，$i$是虛數單位。通常以符號${\mathcal {F}}$表示這一轉換，即

${\hat {x}}={\mathcal {F}}x$

離散傅立葉轉換的逆轉換（IDFT）為：

$x\left[n\right]={1 \over N}\sum _{k=0}^{N-1}e^{i{\frac {2\pi }{N}}nk}{\hat {x}}[k]\qquad n=0,1,\ldots ,N-1.$

可以記為：

$x={\mathcal {F}}^{-1}{\hat {x}}$

實際上，DFT和IDFT轉換式中和式前面的歸一化係數並不重要。在上面的定義中，DFT和IDFT前的係數分別為$1$和${\frac {1}{N}}$。有時會將這兩個係數都改成${\frac {1}{\sqrt {N}}}$。

從連續到離散

連續時間信號$x(t)$以及對應的連續傅立葉轉換${\hat {x}}(\omega )$都是連續函數。由於數位系統只能處理有限長的離散信號，因此必須將$x$和${\hat {x}}$都離散化，並且建立對應的傅立葉轉換。

假設$x(t)$時限於$[0,L]$，再通過時域採樣將$x(t)$離散化，就可以得到有限長離散信號，記為$x_{discrete}(t)$。設採樣週期為$T$，則時域採樣點數$N={\frac {L}{T}}$。

$x_{discrete}(t)=x(t)\sum _{n=0}^{N-1}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)\delta (t-nT)$

它的傅立葉轉換為

${\hat {x}}_{discrete}(\omega )=\sum _{n=0}^{N-1}x(nT){\mathcal {F}}\delta (t-nT)=\sum _{n=0}^{N-1}x(nT)e^{-in\omega T}$

這就是$x(t)$在時域採樣後的連續傅立葉轉換，也就是離散時間傅立葉轉換，它在頻域依然是連續的。

下面將頻域信號轉化為有限長離散信號。與對時域信號的處理類似，假設頻域信號是帶限的，再經過離散化，即可得到有限長離散信號。依據採樣定理，頻域採樣若要能完全重建原信號，頻域信號${\hat {x}}(\omega )$應當帶限於$(0,{\frac {1}{2T}})$。由於時域信號時限於$[0,L]$，由採樣定理以及時頻對偶的關係，頻域的採樣間隔應為$1/L$。故，頻域採樣點數為：

${\frac {1/T}{1/L}}=N$

即頻域採樣的點數和時域採樣同為$N$，頻域採樣點為$\{\omega _{k}={2\pi }k/NT\}_{0\leq k<N}$。 而DTFT在頻域上採樣：

${\hat {x}}[k]={\hat {x}}_{discrete}(\omega _{k})={\frac {1}{T}}\sum _{n=0}^{N-1}x[nT]e^{-i{\frac {2\pi }{N}}nk}$

令$T=1$，將其歸一化，就得到前面定義的離散傅立葉轉換。因此，DFT就是先將信號在時域離散化，求其連續傅立葉轉換後，再在頻域離散化的結果。

DFT與CFT

參見：連續傅立葉轉換

下面考察離散傅立葉轉換與連續傅立葉轉換（CFT，Continuous Fourier Transform）的關係。連續傅立葉轉換

${\mathcal {F}}x(t)={\hat {x}}(\omega )={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega t}dt$

的採樣為：

${\hat {x}}(\omega _{k})={\frac {1}{L}}\int _{0}^{L}x(t)e^{-i\omega _{k}t}dt$

將這個積分以黎曼和的形式近似，有：

${\hat {x}}(\omega _{k})\approx {\frac {1}{L}}\sum _{n=0}^{N-1}x[n]e^{-i\omega _{k}nT}T={\frac {1}{N}}{\hat {x}}[k]$

這一結論指出離散傅立葉轉換確實是連續傅立葉轉換在某種意義上的近似。不過必須注意以下兩點：

• 時域採樣必須滿足採樣定理
• 離散傅立葉轉換的處理物件是時限的

為此，通常對連續信號的時域採樣再做一次加窗處理（Windowing），這樣就得到帶限的有限長離散信號。

DFT與DTFT

參見：離散時間傅立葉轉換

離散時間傅立葉轉換（DTFT）是在時域上對連續傅立葉轉換的採樣。DFT則是在頻域上對DTFT的均勻採樣。離散信號$x[n]$（n=0,...,N-1）的DTFT為：

${\hat {x}}(e^{i\omega })=\sum _{n=0}^{N-1}x[n]e^{-in\omega }$

對${\hat {x}}(e^{i\omega })$在離散的頻點$\{\omega _{k}=k{\frac {2\pi }{N}}\}_{0\leq k<N}$上採樣

${\hat {x}}[k]={\hat {x}}(e^{i\omega _{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}\qquad k=0,\ldots ,N-1$

即為$x$的DFT。由於DTFT在頻域是週期的，所以在DTFT頻域上的均勻採樣也應是週期的。${\hat {x}}[k]$實際上是這個週期序列的主值序列。

柵欄效應

$N$點序列的DFT只能在有限的$N$個頻點上觀察頻譜，這相當於從柵欄的縫隙中觀察景色，對於了解信號在整個頻域上的特性是不夠的。為了觀察到其他頻率的資訊，需要對原信號$x[n]$做一些處理，以便在不同的頻點上採樣。

將原來在DTFT頻域上的採樣點數增加到$M$點，這樣採樣點位置變為$\{\omega '_{k}=e^{ik{\frac {2\pi }{M}}}\}_{0\leq k<M}$。則對應的DFT成為

${\hat {x}}'[k]={\hat {x}}(e^{ik\omega '_{k}})=\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{M}}kn}$

若在序列$x[n]$之後補上M-N個零，設為$x'[n]$，則上式變為

${\hat {x}}'[k]=\sum _{n=0}^{M-1}x'[n]e^{-i{\frac {2\pi }{M}}kn}={\mathcal {F}}x'$

因此將$x[n]$補零再做DFT就可以得到$x[n]$的DTFT在其他頻率上的值，相當於移動了柵欄，因而能夠從其他位置進行觀察。

頻譜解析度

$N$點DFT的頻譜解析度是$2\pi /N$。柵欄效應一節指出可以通過補零觀察到更多的頻點，但是這並不意味著補零能夠提高真正的頻譜解析度。這是因為$x[n]$實際上是$x(t)$採樣的主值序列，而將$x[n]$補零得到的$x'[n]$週期延拓之後與原來的序列並不相同，也不是$x(t)$的採樣。因此${\hat {x}}'$與${\hat {x}}$是不同離散信號的頻譜。對於補零至$M$點的$x'$的DFT，只能說它的解析度${\frac {2\pi }{M}}$僅具有計算上的意義，${\hat {x}}'$並不是真正的、物理意義上的頻譜。頻譜解析度的提高只能在滿足採樣定理的條件下增加時域採樣長度來實現。

從空間的角度分析

週期為N的離散信號構成一個N維歐幾里得空間$\mathbb {C} ^{N}$。在這一空間上兩個信號x和y的內積定義為

$\langle x,y\rangle =\sum _{n=0}^{N-1}x[n]y^{*}\left[n\right]$

下面給出$\mathbb {C} ^{N}$上的一組正交基：

$\{e_{k}[n]=e^{i{\frac {2\pi }{N}}kn}\}_{0\leq k<N}$

將信號x在這組正交基上分解，得

$x=\sum _{k=0}^{N-1}{\frac {\langle x,e_{k}\rangle }{\Vert e_{k}\Vert ^{2}}}e_{k}$

令

${\hat {x}}[k]=\langle x,e_{k}\rangle =\sum _{n=0}^{N-1}x[n]e^{-i{\frac {2\pi }{N}}kn}$

此即為離散傅立葉轉換。又

$\|e_{k}\|^{2}=N$

則有

$x[n]={\frac {1}{N}}\sum _{k=0}^{N-1}{\hat {x}}[k]e^{i{\frac {2\pi }{N}}kn}$

此即為離散傅立葉轉換的逆轉換。

由此可知，在正交分解的角度上說，離散週期信號$x$的離散傅立葉轉換${\hat {x}}$實質上是$x$在正交基$\{e_{k}\}$上的分量。而從線性轉換的角度上說，$\{e_{k}\}$是圓周摺積的特徵向量，${\hat {x}}$則是對應的特徵值。

DFT與圓周摺積

根據摺積定理，離散信號x與y的圓周摺積對偶於頻域上x與y離散傅立葉轉換的乘積。下面揭示DFT與圓周摺積的內在關係。

對長為N的離散信號${\tilde {x}}$與${\tilde {y}}$，如果要計算它們的摺積，就必須定義${\tilde {x}}[n]$與${\tilde {y}}[n]$在0≤n<N之外的值。如果將${\tilde {x}}$與${\tilde {y}}$作週期為N的延拓，則有

$x[n]={\tilde {x}}[n\mod N]\qquad y[n]={\tilde {y}}[n\mod N]$

如此，週期為N的圓周摺積：

$(x\otimes y)[n]=\sum _{m=0}^{N-1}x[m]y[n-m]=\sum _{m=0}^{N-1}x[n-m]y[m]$

摺積的結果仍然是以N為週期的離散信號。

前面指出，$e_{k}$是DFT的特徵向量，實際上它也是圓周摺積的特徵向量。定義x與y的圓周摺積算子：

${L}x[n]=(x\otimes y)[n]$

則$e_{k}$與y的圓周摺積為

${L}e_{k}[n]=e_{k}[n]\cdot \sum _{m=0}^{N-1}y[m]e_{k}[-m]$

顯然，y的DFT

${\hat {y}}[k]=\sum _{m=0}^{N-1}y[m]e_{k}[-m]$

就是圓周摺積的特徵值。

性質

完全性

離散傅立葉轉換是可逆的線性轉換

${\mathcal {F}}:\mathbf {C} ^{N}\to \mathbf {C} ^{N}$

其中C表示複數集。即，任意N-維複向量都存在DFT和IDFT，而且其DFT和IDFT也是N-維複向量。

正交性

向量組exp（2πi kn/N）是N-維複數空間上的一組正交基：

$\sum _{n=0}^{N-1}\left(e^{{\frac {2\pi i}{N}}kn}\right)\left(e^{-{\frac {2\pi i}{N}}k'n}\right)=N~\delta _{kk'}$

其中δ_kn是Kronecker delta。

移位定理

時域信號序列$x_{n}$的相位移動$\exp(2\pi inm/N)$（其中$m$為整數）在頻域反映為「循環移位」，即：頻域信號序列$X_{k}$變為$X_{((k-m))_{N}}$，其中下標是指將k-m對N 取余。類似的，由對偶性，時域信號序列的循環移位對應於頻域信號序列的相移：

若${\mathcal {F}}(\{x_{n}\})_{k}=X_{k}$

則${\mathcal {F}}(\{x_{n}e^{{\frac {2\pi i}{N}}nm}\})_{k}=X_{k-m}$

且有${\mathcal {F}}(\{x_{n-m}\})_{k}=X_{k}e^{-{\frac {2\pi i}{N}}km}$

週期性

上文中DFT與DTFT一節已經證明，離散序列的傅立葉轉換是週期的。有限長序列$x_{n}$的離散傅立葉轉換$X_{k}$可以被看作是它的週期延拓序列${\tilde {x}}_{n}=x_{n\ mod\ N}$的離散時間傅立葉轉換${\tilde {X}}_{k}$。由時頻對偶性可知$X_{k}$也可以被看作它的週期延拓的主值。

上一節的移位定理隱含著DFT的週期性，因為DFT的幅度$|X_{k}|$不受輸入信號的循環移位的影響，因為時移在頻域對偶於相移，循環移位僅僅使DFT的相位產生平移。週期性的邊界條件在DFT的許多應用中有重要作用。解差分方程式時，就假設邊界條件是滿足週期性的，這是一個很有用的性質（參見應用）。

普朗歇爾定理與帕塞瓦爾定理

如果X_k和Y_k分別是x_n和y_n的離散傅立葉轉換，那麼就有普朗歇爾定理：

$\sum _{n=0}^{N-1}x_{n}y_{n}^{*}={\frac {1}{N}}\sum _{k=0}^{N-1}X_{k}Y_{k}^{*}$

其中星號表示復共扼。帕塞瓦爾定理是普朗歇爾定理的一個特例：

$\sum _{n=0}^{N-1}|x_{n}|^{2}={\frac {1}{N}}\sum _{k=0}^{N-1}|X_{k}|^{2}.$

應用

DFT在諸多多領域中有著重要應用，下面僅是頡取的幾個例子。需要指出的是，所有DFT的實際應用都依賴於計算離散傅立葉轉換及其逆轉換的快速算法，即快速傅立葉轉換。

快速傅立葉轉換

主條目：快速傅立葉轉換

快速傅立葉轉換（即FFT）是計算離散傅立葉轉換及其逆轉換的快速算法。按照DFT的定義計算一個長為n的序列的DFT需要的計算複雜度達到了${\mathcal {O}}(n^{2})$，而同樣長度FFT的計算複雜度僅為${\mathcal {O}}(n\log n)$。由於DFT的逆轉換可以由DFT表示，所以DFT逆轉換的計算同樣可以由FFT完成。FFT算法的提出，使DFT得到了廣泛的實際應用。

頻譜分析

前面指出，DFT是連續傅立葉轉換的近似。因此可以對連續信號x（t）均勻採樣並截斷以得到有限長的離散序列$\{x_{n}\}\,$，對這一序列作離散傅立葉轉換，可以分析連續信號x（t）頻譜的性質。前面還提到DFT應用於頻譜分析需要注意的兩個問題：即採樣可能導致信號混疊和截斷信號引起的頻譜洩漏。可以通過選擇適當的採樣頻率（見奈奎斯特頻率）消減混疊。選擇適當的序列長度並加窗可以抑制頻譜洩漏。

數據壓縮

主條目：數據壓縮

由於人類感官的分辨能力存在極限，因此很多有損壓縮算法利用這一點將語音、音頻、圖像、視頻等信號的高頻部分除去。高頻信號對應於信號的細節，濾除高頻信號可以在人類感官可以接受的範圍內獲得很高的壓縮比。這一去除高頻分量的處理就是通過離散傅立葉轉換完成的。將時域或空域的信號轉換到頻域，僅儲存或傳輸較低頻率上的係數，在解壓縮端採用逆轉換即可重建信號。

解偏微分方程式

主條目：偏微分方程式

離散傅立葉轉換及其多維形式在偏微分方程式的求解中也有應用。此時DFT被看作傅立葉級數的近似。傅立葉級數將函數在複指數e^inx上展開，這正是微分算子的特徵方程式：d/dx e^inx = in e^inx。因此，通過傅立葉級數的形式，線性常微分方程式被轉換為代數方程式，而後者是很容易求解的。此時得到的結果是偏微分方程式解的級數表示，只要通過DFT逆轉換即可得到其一般表示。這種方法被稱作譜方法或級數解法。

長整數與多項式乘法

目前長整數或多項式乘法最快速的算法是基於離散傅立葉轉換的。由於整數（或多項式）乘法是逐位（或逐項）乘累加的形式，因此整數（或多項式）乘積的數字（或係數）可以用乘數數字（或乘式係數）的摺積表示。利用摺積定理，只要將數字（或係數）序列通過離散傅立葉轉換變到頻域，就可以將逐個乘累加的摺積變為對位的乘法，從而減少計算量，再以一次逆轉換便可以得到乘法結果。需要注意整數乘法還有進位的問題。下面以多項式乘法為例說明這一應用：

假設需要計算多項式乘法c(x) = a(x)·b（x），這一乘積結果的各項係數的表達式實際上是線性摺積的形式。由於離散傅立葉轉換對應於圓周摺積，因此需要將這兩個乘式的係數按照次數升序排列，序列後「補零」，使它們的長度d大於兩式最高項次數的和：d > deg(a(x)) + deg(b(x))。然後作圓周摺積：

$\mathbf {c} =\mathbf {a} \otimes \mathbf {b}$

其中c就是c(x)係數的向量。由於圓周摺積的DFT是乘積，有：

${\mathcal {F}}\mathbf {c} ={\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b}$

則

$\mathbf {c} ={\mathcal {F}}^{-1}({\mathcal {F}}\mathbf {a} \cdot {\mathcal {F}}\mathbf {b} )$

利用快速傅立葉轉換，這一算法的運算複雜度為${\mathcal {O}}(N\log N)$。

OFDM

主條目：OFDM

OFDM（正交頻分復用）在寬帶無線通信中有重要的應用。這種技術將帶寬分為N個等間隔的子載波，可以證明這些子載波相互正交。尤其重要的是，OFDM調製可以由IDFT實現，而解調可以由DFT實現。OFDM還利用DFT的移位性質，在每個幀頭部加上循環前綴（Cyclic Prefix），使得只要信道延時小於循環前綴的長度，就能消除信道延時對傳輸的影響。

特殊例子

數論轉換

主條目：數論轉換

數論轉換是離散傅利葉轉換(DFT)的一個特例 $F=Z/p$，此運算是根據模運算 而取得的，$p$需要是質數 ，如此可以建構出有限體，並且存在 $n$ 個可以整除 $(p-1)$ 的實數根。如此可以得到$p=k\cdot n+1$，$k$ 為正整數。令 $\omega$ 為第 $(p-1)$ 個單位根，則第 $n$ 個單位根 $\alpha$ 可以表示成 $\alpha =\omega ^{k}$ 。另外，再令$N$ 為 $\alpha$ 次方 $p$ 模運算之循環個數。

則數論矩陣為

${\begin{bmatrix}{\underset {-}{F}}\end{bmatrix}}={\begin{bmatrix}{\underset {-}{\alpha ^{cr}}}\end{bmatrix}}{\begin{bmatrix}{\underset {-}{f}}\end{bmatrix}}$

$c$ 與 $r$ 各為 Column 與 Row 的指數(index), 令 $C$ 與 $R$ 各代表Column 與 Row 的總數，則$C=R=N$， $c\propto {\begin{Bmatrix}0,1,...,C-1\end{Bmatrix}},r\propto {\begin{Bmatrix}0,1,...,R-1\end{Bmatrix}}$.

舉個例子來說，當 $p=5,\alpha =2$ 則

$\alpha ^{1}=2\qquad (mod\quad 5)$

$\alpha ^{2}=4\qquad (mod\quad 5)$

$\alpha ^{3}=3\qquad (mod\quad 5)$

$\alpha ^{4}=1\qquad (mod\quad 5)$

因為 $\alpha ^{4}$ 經 $5$ 的模運算為 $1$ ，因此可以判定此情況為 $4$ 個次方一循環，所以 $N=4$，$N$可以整除 $(p-1)$。則數論矩陣可以表示成

${\begin{bmatrix}F(0)\\F(1)\\F(2)\\F(3)\end{bmatrix}}={\begin{bmatrix}1&1&1&1\\1&2&4&3\\1&4&1&4\\1&3&4&2\end{bmatrix}}{\begin{bmatrix}f(0)\\f(1)\\f(2)\\f(3)\end{bmatrix}}$

在一些特殊的情況下，令 $F=Z/m$ ，而 $m$ 不是值數也是有意義的。像是 Fermat Number Transform 中$(m=2^{k}+1)$，以及 Mersenne Number Transform 中 $(m=2^{k}-1)$.

參閱

• 傅立葉級數
• 傅立葉轉換
• 快速傅立葉轉換
• 數位訊號處理
• Chirp-Z轉換

參考文獻

1. Oppenheim, Alan V.; Schafer, R. W.; and Buck, J. R., (1999). Discrete-time signal processing, Upper Saddle River, N.J. : Prentice Hall. ISBN 0137549202
2. Mallat, S., A Wavelet Tour of Signal Processing, Second Edition, Academic Press, ISBN 0-12-466606-x
3. Gill, J., Fourier Transform and Its Applications（[1] （頁面存檔備份，存於網際網路檔案館））