離散傅里葉變換

目錄
·從連續(xù)到離散
·DFT與CT
·DFT與DTFT
·從空間的角度分析
·DFT與圓周卷積
·性質(zhì)
·應(yīng)用
·參閱










離散傅里葉變換（Discrete Fourier Transform，縮寫(xiě)為DFT），是傅里葉變換在時(shí)域和頻域上都呈離散的形式，將信號(hào)的時(shí)域采樣變換為其DTFT的頻域采樣。在形式上，變換兩端（時(shí)域和頻域上）的序列是有限長(zhǎng)的，而實(shí)際上這兩組序列都應(yīng)當(dāng)被認(rèn)為是離散周期信號(hào)的主值序列。即使對(duì)有限長(zhǎng)的離散信號(hào)作DFT，也應(yīng)當(dāng)將其看作其周期延拓的變換。在實(shí)際應(yīng)用中通常采用快速傅里葉變換計(jì)算DFT。
下面給出離散傅里葉變換的變換對(duì)：
對(duì)于N點(diǎn)序列，它的離散傅里葉變換（DFT）為
其中e 是自然對(duì)數(shù)的底數(shù)，i 是虛數(shù)單位。通常以符號(hào)表示這一變換，即
離散傅里葉變換的逆變換（IDFT）為：
可以記為：
實(shí)際上，DFT和IDFT變換式中和式前面的歸一化系數(shù)并不重要。在上面的定義中，DFT和IDFT前的系數(shù)分別為1 和1/N。有時(shí)會(huì)將這兩個(gè)系數(shù)都改成。





從連續(xù)到離散

連續(xù)時(shí)間信號(hào)x(t) 以及對(duì)應(yīng)的連續(xù)傅里葉變換都是連續(xù)函數(shù)。由于數(shù)字系統(tǒng)只能處理有限長(zhǎng)的離散信號(hào)，因此必須將x和都離散化，并且建立對(duì)應(yīng)的傅里葉變換。
假設(shè)x(t)時(shí)限于[0, L]，再通過(guò)時(shí)域采樣將x(t)離散化，就可以得到有限長(zhǎng)離散信號(hào)，記為x_discrete(t)。設(shè)采樣周期為T(mén)，則時(shí)域采樣點(diǎn)數(shù)N=L/T。

它的傅里葉變換為

這就是x(t)在時(shí)域采樣后的連續(xù)傅里葉變換，也就是離散時(shí)間傅里葉變換，它在頻域依然是連續(xù)的。
下面將頻域信號(hào)轉(zhuǎn)化為有限長(zhǎng)離散信號(hào)。與對(duì)時(shí)域信號(hào)的處理類似，假設(shè)頻域信號(hào)是帶限的，再經(jīng)過(guò)離散化，即可得到有限長(zhǎng)離散信號(hào)。依據(jù)采樣定理，時(shí)域采樣若要能完全重建原信號(hào)，頻域信號(hào)應(yīng)當(dāng)帶限于(0,1/T)。由于時(shí)域信號(hào)時(shí)限于[0, L]，由采樣定理以及時(shí)頻對(duì)偶的關(guān)系，頻域的采樣間隔應(yīng)為1/L。故，頻域采樣點(diǎn)數(shù)為：

即頻域采樣的點(diǎn)數(shù)和時(shí)域采樣同為N，頻域采樣點(diǎn)為 在DTFT頻域上采樣：

令T=1，將其歸一化，就得到前面定義的離散傅里葉變換。因此，DFT就是先將信號(hào)在時(shí)域離散化，求其連續(xù)傅里葉變換后，再在頻域離散化的結(jié)果。



DFT與CT

參見(jiàn)連續(xù)傅里葉變換

下面考察離散傅里葉變換與連續(xù)傅里葉變換（CT，Continuous Fourier Transform）的關(guān)系。連續(xù)傅里葉變換
的采樣為：

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

這一結(jié)論指出離散傅里葉變換確實(shí)是連續(xù)傅里葉變換在某種意義上的近似。不過(guò)必須注意以下兩點(diǎn)：

時(shí)域采樣必須滿足采樣定理
離散傅里葉變換的處理對(duì)象是時(shí)限的

為此，通常對(duì)連續(xù)信號(hào)的時(shí)域采樣再做一次加窗處理（Windowing），這樣就得到帶限的有限長(zhǎng)離散信號(hào)。



DFT與DTFT

參見(jiàn)離散時(shí)間傅里葉變換
離散時(shí)間傅里葉變換（DTFT）是在時(shí)域上對(duì)連續(xù)傅里葉變換的采樣。DFT則是在頻域上對(duì)DTFT的均勻采樣。離散信號(hào)x[n]（n=0,...,N-1）的DTFT為：
對(duì)在離散的頻點(diǎn)上采樣
即為x 的DFT。由于DTFT在頻域是周期的，所以在DTFT頻域上的均勻采樣也應(yīng)是周期的。實(shí)際上是這個(gè)周期序列的主值序列。

柵欄效應(yīng)
N 點(diǎn)序列的DFT只能在有限的N個(gè)頻點(diǎn)上觀察頻譜，這相當(dāng)于從柵欄的縫隙中觀察景色，對(duì)于了解信號(hào)在整個(gè)頻域上的特性是不夠的。為了觀察到其他頻率的信息，需要對(duì)原信號(hào)x[n]做一些處理，以便在不同的頻點(diǎn)上采樣。
將原來(lái)在DTFT頻域上的采樣點(diǎn)數(shù)增加到M 點(diǎn)，這樣采樣點(diǎn)位置變?yōu)�。則對(duì)應(yīng)的DFT成為
若在序列x[n] 之后補(bǔ)上M-N個(gè)零，設(shè)為x&＃39;&＃39;&＃39;&＃39;[n]，則上式變?yōu)?BR>
因此將x[n]補(bǔ)零再做DFT就可以得到x[n]的DTFT在其他頻率上的值，相當(dāng)于移動(dòng)了柵欄，因而能夠從其他位置進(jìn)行觀察。

頻譜分辨率
N 點(diǎn)DFT的頻譜分辨率是2π / N。柵欄效應(yīng)一節(jié)指出可以通過(guò)補(bǔ)零觀察到更多的頻點(diǎn)，但是這并不意味著補(bǔ)零能夠提高真正的頻譜分辨率。這是因?yàn)閤[n] 實(shí)際上是x(t) 采樣的主值序列，而將x[n]補(bǔ)零得到的x&＃39;&＃39;&＃39;&＃39;[n] 周期延拓之后與原來(lái)的序列并不相同，也不是x(t) 的采樣。因此與是不同離散信號(hào)的頻譜。對(duì)于補(bǔ)零至M點(diǎn)的x&＃39;&＃39;&＃39;&＃39;的DFT，只能說(shuō)它的分辨率2π / M僅具有計(jì)算上的意義，并不是真正的、物理意義上的頻譜。頻譜分辨率的提高只能在滿足采樣定理的條件下增加時(shí)域采樣長(zhǎng)度來(lái)實(shí)現(xiàn)。


從空間的角度分析

周期為N的離散信號(hào)構(gòu)成一個(gè)N 維歐氏空間。在這一空間上兩個(gè)信號(hào)x 和y 的內(nèi)積定義為
下面給出上的一組正交基：
將信號(hào)x 在這組正交基上分解，得
令
此即為離散傅里葉變換。又

則有

此即為離散傅里葉變換的逆變換。
由此可知，在正交分解的角度上說(shuō)，離散周期信號(hào)x的離散傅里葉變換實(shí)質(zhì)上是x在正交基{e_k}上的分量。而從線性變換的角度上說(shuō)，{e_k}是圓周卷積的特征向量，則是對(duì)應(yīng)的特征值。


DFT與圓周卷積

根據(jù)卷積定理，離散信號(hào)x與y的圓周卷積對(duì)偶于頻域上x(chóng)與y離散傅里葉變換的乘積。下面揭示DFT與圓周卷積的內(nèi)在關(guān)系。
對(duì)長(zhǎng)為N的離散信號(hào)與，如果要計(jì)算它們的卷積，就必須定義與在0≤n<N 之外的值。如果將與作周期為N的延拓，則有
如此，周期為N的圓周卷積：
卷積的結(jié)果仍然是以N為周期的離散信號(hào)。
前面指出，e_k是DFT的特征向量，實(shí)際上它也是圓周卷積的特征向量。定義x與y的圓周卷積算子：
則e_k與y的圓周卷積為

顯然，y的DFT

就是圓周卷積的特征值。


性質(zhì)


完全性
離散傅里葉變換是可逆的線性變換

其中C表示復(fù)數(shù)集。即，任意N-維復(fù)向量都存在DFT和IDFT，而且其DFT和IDFT也是N-維復(fù)向量。

正交性
向量組exp(2πi kn/N)是N-維復(fù)數(shù)空間上的一組正交基：

其中 δ_kn是Kronecker delta。

移位定理
時(shí)域信號(hào)序列x_n的相位移動(dòng)exp(2πinm / N)（其中m為整數(shù)）在頻域反映為“循環(huán)移位”，即：頻域信號(hào)序列X_k變?yōu)椋�其中下�?biāo)是指將k-m 對(duì)N 取余。類似的，由對(duì)偶性，時(shí)域信號(hào)序列的循環(huán)移位對(duì)應(yīng)于頻域信號(hào)序列的相移：
若則
且有

周期性
上文中DFT與DTFT一節(jié)已經(jīng)證明，離散序列的傅里葉變換是周期的。有限長(zhǎng)序列x_n的離散傅里葉變換X_k可以被看作是它的周期延拓序列的離散時(shí)間傅里葉變換。由時(shí)頻對(duì)偶性可知X_k也可以被看作它的周期延拓的主值。
上一節(jié)的移位定理隱含著DFT的周期性，因?yàn)镈FT的幅度 | X_k | 不受輸入信號(hào)的循環(huán)移位的影響，因?yàn)闀r(shí)移在頻域?qū)ε加谙嘁�，循環(huán)移位僅僅使DFT的相位產(chǎn)生平移。周期性的邊界條件在DFT的許多應(yīng)用中有重要作用。解差分方程時(shí)，就假設(shè)邊界條件是滿足周期性的，這是一個(gè)很有用的性質(zhì)（參見(jiàn)應(yīng)用）。

Plancherel定理與Parseval定理
如果 X_k 和 Y_k 分別是 x_n 和 y_n 的離散傅立葉變換，那么就有 Plancherel 定理：
其中星號(hào)表示復(fù)共扼。Parseval定理 是 Plancherel 定理的一個(gè)特例：




應(yīng)用

DFT在諸多多領(lǐng)域中有著重要應(yīng)用，下面僅是頡取的幾個(gè)例子。需要指出的是，所有DFT的實(shí)際應(yīng)用都依賴于計(jì)算離散傅里葉變換及其逆變換的快速算法，即快速傅里葉變換。

快速傅里葉變換

主條目：快速傅里葉變換

快速傅里葉變換（即FFT）是計(jì)算離散傅里葉變換及其逆變換的快速算法。按照DFT的定義計(jì)算一個(gè)長(zhǎng)為n的序列的DFT需要的計(jì)算復(fù)雜度達(dá)到了，而同樣長(zhǎng)度FFT的計(jì)算復(fù)雜度僅為。由于DFT的逆變換可以由DFT表示，所以DFT逆變換的計(jì)算同樣可以由FFT完成。FFT算法的提出，使DFT得到了廣泛的實(shí)際應(yīng)用。

頻譜分析
前面指出，DFT是連續(xù)傅里葉變換的近似。因此可以對(duì)連續(xù)信號(hào)x(t)均勻采樣并截?cái)嘁缘玫接邢揲L(zhǎng)的離散序列，對(duì)這一序列作離散傅里葉變換，可以分析連續(xù)信號(hào)x(t)頻譜的性質(zhì)。前面還提到DFT應(yīng)用于頻譜分析需要注意的兩個(gè)問(wèn)題：即采樣可能導(dǎo)致信號(hào)混疊和截?cái)嘈盘?hào)引起的頻譜泄漏。可以通過(guò)選擇適當(dāng)?shù)牟蓸宇l率（見(jiàn)奈奎斯特頻率）消減混疊。選擇適當(dāng)?shù)男蛄虚L(zhǎng)度并加窗可以抑制頻譜泄漏。

數(shù)據(jù)壓縮

主條目：數(shù)據(jù)壓縮
由于人類感官的分辨能力存在極限，因此很多有損壓縮算法利用這一點(diǎn)將語(yǔ)音、音頻、圖像、視頻等信號(hào)的高頻部分除去。高頻信號(hào)對(duì)應(yīng)于信號(hào)的細(xì)節(jié)，濾除高頻信號(hào)可以在人類感官可以接受的范圍內(nèi)獲得很高的壓縮比。這一去除高頻分量的處理就是通過(guò)離散傅里葉變換完成的。將時(shí)域或空域的信號(hào)轉(zhuǎn)換到頻域，僅儲(chǔ)存或傳輸較低頻率上的系數(shù)，在解壓縮端采用逆變換即可重建信號(hào)。

解偏微分方程
主條目：偏微分方程

離散傅里葉變換及其多維形式在偏微分方程的求解中也有應(yīng)用。此時(shí)DFT被看作傅里葉級(jí)數(shù)的近似。傅里葉級(jí)數(shù)將函數(shù)在復(fù)指數(shù)einx上展開(kāi),這正是微分算子的特征方程：d/dx einx = in einx。因此，通過(guò)傅里葉級(jí)數(shù)的形式，線性常微分方程被轉(zhuǎn)換為代數(shù)方程，而后者是很容易求解的。此時(shí)得到的結(jié)果是偏微分方程解的級(jí)數(shù)表示，只要通過(guò)DFT逆變換即可得到其一般表示。這種方法被稱作譜方法或級(jí)數(shù)解法。

長(zhǎng)整數(shù)與多項(xiàng)式乘法
目前長(zhǎng)整數(shù)或多項(xiàng)式乘法最快速的算法是基于離散傅里葉變換的。由于整數(shù)（或多項(xiàng)式）乘法是逐位（或逐項(xiàng)）乘累加的形式，因此整數(shù)（或多項(xiàng)式）乘積的數(shù)字（或系數(shù)）可以用乘數(shù)數(shù)字（或乘式系數(shù)）的卷積表示。利用卷積定理，只要將數(shù)字（或系數(shù)）序列通過(guò)離散傅里葉變換變到頻域，就可以將逐個(gè)乘累加的卷積變?yōu)閷?duì)位的乘法，從而減少計(jì)算量，再以一次逆變換便可以得到乘法結(jié)果。需要注意整數(shù)乘法還有進(jìn)位的問(wèn)題。下面以多項(xiàng)式乘法為例說(shuō)明這一應(yīng)用：
假設(shè)需要計(jì)算多項(xiàng)式乘法c(x) = a(x) · b(x)，這一乘積結(jié)果的各項(xiàng)系數(shù)的表達(dá)式實(shí)際上是線性卷積的形式。由于離散傅里葉變換對(duì)應(yīng)于圓周卷積，因此需要將這兩個(gè)乘式的系數(shù)按照次數(shù)升序排列，序列后“補(bǔ)零”，使它們的長(zhǎng)度d 大于兩式最高項(xiàng)次數(shù)的和：d > deg(a(x)) + deg(b(x))。然后作圓周卷積：

其中c 就是c(x) 系數(shù)的向量。由于圓周卷積的DFT是乘積，有：

則

利用快速傅里葉變換，這一算法的運(yùn)算復(fù)雜度為 。

OFDM

主條目：OFDM
OFDM（正交頻分復(fù)用）在寬帶無(wú)線通信中有重要的應(yīng)用。這種技術(shù)將帶寬分為N個(gè)等間隔的子載波，可以證明這些子載波相互正交。尤其重要的是，OFDM調(diào)制可以由IDFT實(shí)現(xiàn)，而解調(diào)可以由DFT實(shí)現(xiàn)。OFDM還利用DFT的移位性質(zhì)，在每個(gè)幀頭部加上循環(huán)前綴（Cyclic Prefix），使得只要信道延時(shí)小于循環(huán)前綴的長(zhǎng)度，就能消除信道延時(shí)對(duì)傳輸?shù)挠绊憽?BR>

參閱


傅里葉級(jí)數(shù)
傅里葉變換
快速傅里葉變換
數(shù)字信號(hào)處理
Chirp-Z 變換

• 通信詞典解釋