第4章離散變換及其快速算法

《測(cè)試信號(hào)分析與處理》課程

第四章離散傅里葉變換及其

快速算法

第一節(jié)序列的傅里葉變換（DTFT）第二節(jié)離散傅里葉級(jí)數(shù)（DFS）第三節(jié)離散傅里葉變換（DFT）第四節(jié)離散傅里葉變換的性質(zhì)《測(cè)試信號(hào)分析與處理》課程第五節(jié)快速傅里葉變換（FFT）第六節(jié)IDFT的快速算法（IFFT）第七節(jié)實(shí)序列的FFT高效算法第八節(jié)用FFT計(jì)算線卷積和相關(guān)運(yùn)算第九節(jié)MATLAB中用于FFT計(jì)算的函數(shù)簡(jiǎn)介第一節(jié)序列的傅里葉變換一、定義已知序列的Z變換為如X(Z)在單位圓上是收斂的，則將在單位圓上的Z變換定義為序列的傅里葉變換，即由于序列的傅里葉變換定義為單位圓上的Z變換，因此其同Z變換具有相同的性質(zhì)。第一節(jié)序列的傅里葉變換二、物理意義與存在條件連續(xù)信號(hào)的傅里葉反變換為Z反變換的圍線積分公式為將積分圍線c取在單位圓上，則有第一節(jié)序列的傅里葉變換兩者相比前者是連續(xù)信號(hào)不同頻率的復(fù)指數(shù)分量，后者是序列不同頻率的復(fù)指數(shù)分量；兩者都是頻域中頻率的概念，

ω表示模擬角頻率，Ω表示數(shù)字角頻率；前者是連續(xù)信號(hào)在時(shí)域的表示，可以分解為一系列不同頻率的復(fù)指數(shù)分量的疊加，分量的復(fù)振幅為

，后者是序列在時(shí)域的表示，可以分解為一系列不同數(shù)字角頻率分量的疊加，分量的復(fù)振幅為。第一節(jié)序列的傅里葉變換前者有連續(xù)信號(hào)頻譜密度的意義，是頻譜的概念，后者是序列的傅里葉變換，可以看作是序列的頻譜。ω是模擬角頻率，變化范圍是沒有限制的，高頻部分可以趨于∞；而數(shù)字角頻率Ω的變化雖然是連續(xù)的，但變化范圍限制在±π內(nèi)序列的傅里葉變換對(duì)第一節(jié)序列的傅里葉變換

序列的傅里葉變換既然定義為單位圓上的Z變換，所以它的存在條件是序列的Z變換必須在單位圓上是收斂的，即

上式說明序列的傅里葉變換存在的條件是序列必須絕對(duì)可和。第一節(jié)序列的傅里葉變換

三、特點(diǎn)與應(yīng)用非周期序列的傅里葉變換（頻譜）的特點(diǎn)在于它是的連續(xù)周期函數(shù)，其周期為。序列x(n)與其傅里葉變換兩者正好是互為傅里葉級(jí)數(shù)的變換關(guān)系。第一節(jié)序列的傅里葉變換

序列可以表示為復(fù)指數(shù)序列分量的疊加，適用于疊加原理在線性時(shí)不變系統(tǒng)的分析。這種系統(tǒng)對(duì)復(fù)指數(shù)序列的響應(yīng)完全由系統(tǒng)的頻率響應(yīng)確定。一個(gè)線性時(shí)不變系統(tǒng)對(duì)于輸入的輸出響應(yīng)，就是對(duì)它的每個(gè)復(fù)指數(shù)序列分量的響應(yīng)的疊加，則輸出響應(yīng)應(yīng)為則輸出的傅里葉變換為第二節(jié)離散傅里葉級(jí)數(shù)（DFS）一、傅里葉變換在時(shí)域和頻域中的對(duì)稱規(guī)律a)時(shí)域上的非周期性對(duì)應(yīng)頻域上的連續(xù)性第二節(jié)離散傅里葉級(jí)數(shù)（DFS）b)時(shí)域上的周期性將產(chǎn)生頻域的離散性。第二節(jié)離散傅里葉級(jí)數(shù)（DFS）c)時(shí)域上的離散性將產(chǎn)生頻譜的周期性。

第二節(jié)離散傅里葉級(jí)數(shù)（DFS）d)時(shí)域上的離散周期信號(hào)，其頻譜是周期離散的。

第二節(jié)離散傅里葉級(jí)數(shù)（DFS）一個(gè)域中（時(shí)域或頻域）是連續(xù)的，對(duì)應(yīng)另一個(gè)域中（頻域或時(shí)域）是非周期的。一個(gè)域中（時(shí)域或頻域）是離散的，對(duì)應(yīng)另一個(gè)域中（頻域或時(shí)域）是周期的。

第二節(jié)離散傅里葉級(jí)數(shù)（DFS）二、離散傅里葉級(jí)數(shù)離散周期信號(hào)的頻譜，即離散傅里葉級(jí)數(shù)(DFS)。離散傅里葉級(jí)數(shù)的變換對(duì)表達(dá)式其中

第三節(jié)離散傅里葉變換（DFT）一、離散傅里葉變換DFT定義式離散傅里葉變換就是對(duì)有限長(zhǎng)序列進(jìn)行傅里葉變換的表示式。主值序列：對(duì)于一個(gè)周期序列，定義它的第一個(gè)周期的有限長(zhǎng)序列值為此周期序列的主值序列，用表示為主值序列也可以表示為周期序列和一個(gè)矩形序列相乘的結(jié)果，即第三節(jié)離散傅里葉變換（DFT）

周期序列也可以看作是長(zhǎng)度為N的有限長(zhǎng)序列以N為周期延拓而形成了。有了主值序列的概念，再來考察DFS的定義式，只需用主值序列，即可求出并完全地表達(dá)周期無限長(zhǎng)序列，，這樣就得到了任意有限長(zhǎng)序列的離散傅立葉變換對(duì)第三節(jié)離散傅里葉變換（DFT）矩陣形式或

第三節(jié)離散傅里葉變換（DFT）例4-1

用矩陣表示式求矩形序列的DFT，再由所得經(jīng)IDFT反求，驗(yàn)證所求結(jié)果的正確性。解：，故

再由反變換求第三節(jié)離散傅里葉變換（DFT）

第三節(jié)離散傅里葉變換（DFT）二、DFT的物理意義設(shè)一有限長(zhǎng)序列的長(zhǎng)度為N點(diǎn)，其Z變換為因序列為有限長(zhǎng)，滿足絕對(duì)可和的條件，其Z變換的收斂域必定包含單位圓在內(nèi)，則序列的傅里葉變換，即單位圓上的Z變換存在，且為第三節(jié)離散傅里葉變換（DFT）以為間隔，把單位圓均勻等分為N個(gè)點(diǎn)，則在第k個(gè)等分點(diǎn)，即點(diǎn)上的值為故有限長(zhǎng)序列的離散傅里葉變換DFT是這一序列頻譜（序列傅里葉變換）的抽樣值。第三節(jié)離散傅里葉變換（DFT）有限長(zhǎng)序列的DFT就是序列在單位圓上的Z變換（即有限長(zhǎng)序列的傅里葉變換或頻譜）以為間隔的抽樣值

第四節(jié)離散傅里葉變換的性質(zhì)線性特性

若，則式中a、b為任意常數(shù)。如果兩個(gè)序列的長(zhǎng)度不相等，以最長(zhǎng)的序列為基準(zhǔn)，對(duì)短序列要補(bǔ)零，使序列長(zhǎng)度相等，才能進(jìn)行線性相加，經(jīng)過補(bǔ)零的序列頻譜會(huì)變密，但不影響問題的性質(zhì)。第四節(jié)離散傅里葉變換的性質(zhì)時(shí)移特性

1）圓周移位序列將長(zhǎng)度為N的序列進(jìn)行周期延拓，周期為N，構(gòu)成周期序列，然后對(duì)周期序列作m位平行移位處理，得移位序列，再取其主值序列（與一矩形序列相乘），得到的就是圓周移位序列。第四節(jié)離散傅里葉變換的性質(zhì)

第四節(jié)離散傅里葉變換的性質(zhì)2）時(shí)移定理若

則時(shí)移定理表明，序列在時(shí)域上圓周移位，頻域上將產(chǎn)生附加相移，對(duì)上式進(jìn)行反變換可以得到

第四節(jié)離散傅里葉變換的性質(zhì)頻移特性

若則上述特性說明，若序列在時(shí)域上乘以復(fù)指數(shù)序列，則在頻域上將圓周移位，這可以看作調(diào)制信號(hào)的頻譜搬移，因而又稱為“調(diào)制定理”。第四節(jié)離散傅里葉變換的性質(zhì)圓周卷積特性1）時(shí)域圓周卷積若對(duì)N點(diǎn)序列有，，，則2）頻域圓卷積若第四節(jié)離散傅里葉變換的性質(zhì)實(shí)數(shù)序列奇偶性（對(duì)稱性）設(shè)x(n)是實(shí)序列，則X(k)的幅度和相位分別為他們分別為k的偶函數(shù)和奇函數(shù)，并分別具有半周期偶對(duì)稱和奇對(duì)稱的特點(diǎn)。第四節(jié)離散傅里葉變換的性質(zhì)帕斯瓦爾定理若，則式左端代表離散信號(hào)在時(shí)域中的能量，右端代表在頻域中的能量，該式表明變換過程中能量是守恒的。第五節(jié)快速傅里葉變換一、DFT運(yùn)算的特點(diǎn)1.DFT直接運(yùn)算的工作量

N點(diǎn)序列x(n)的DFT為按定義計(jì)算DFT時(shí)，需作次復(fù)數(shù)乘和次復(fù)數(shù)加。由于直接計(jì)算量非常大，不可能實(shí)現(xiàn)信號(hào)的實(shí)時(shí)處理，因此必須改進(jìn)DFT的算法。第五節(jié)快速傅里葉變換2.DFT運(yùn)算特點(diǎn)

1)的周期性2)的對(duì)稱性

因?yàn)楣实谖骞?jié)快速傅里葉變換3)的可約性第五節(jié)快速傅里葉變換利用上述結(jié)果，如對(duì)應(yīng)于N=4的矩陣W可以簡(jiǎn)化為上式右端的矩陣中的元素有許多是相等的，計(jì)算量明顯減少。由原來的16個(gè)元素變成只有兩個(gè)獨(dú)立元素需要計(jì)算。

第五節(jié)快速傅里葉變換二、基2時(shí)析型FFT算法（時(shí)間抽取法）1.算法原理

對(duì)長(zhǎng)度為（L為正整數(shù)，若原序列的長(zhǎng)度不滿足此條件，則可用零補(bǔ)足）的序列x(n),按序列各項(xiàng)序號(hào)的奇偶將序列分成兩個(gè)子序列（大點(diǎn)數(shù)化為小點(diǎn)數(shù)），有偶序號(hào)序列奇序號(hào)序列其中，兩序列的長(zhǎng)度均為N/2。且其DFT分別為第五節(jié)快速傅里葉變換上式中，右邊即為x(n)的前一半DFT值第五節(jié)快速傅里葉變換對(duì)于另外N/2個(gè)點(diǎn)的DFT,即的

，可表示為根據(jù)周期性，有由對(duì)稱性，有

第五節(jié)快速傅里葉變換x(n)的DFT最后結(jié)果

x(n)的DFT可由奇偶對(duì)分序列的DFT合成而獲得。該計(jì)算關(guān)系可用右圖來表示。由于圖形酷似蝴蝶，所以稱之為蝶形圖（或蝶形單元）。上式也因而稱為蝶形算法。第五節(jié)快速傅里葉變換2.算法的具體實(shí)現(xiàn)對(duì)于長(zhǎng)度為的序列逐次奇偶對(duì)分，則最后一定能得到N個(gè)單項(xiàng)序列（序列的長(zhǎng)度為1），而單項(xiàng)序列的DFT就是其本身。因此根據(jù)蝶形圖，計(jì)算N項(xiàng)序列的DFT，只需要按照蝶形算法逐次合成，即由N個(gè)1點(diǎn)長(zhǎng)序列的DFT合成N/2個(gè)2點(diǎn)長(zhǎng)序列的DFT，再由N/2個(gè)2點(diǎn)長(zhǎng)序列的DFT合成N/4個(gè)4點(diǎn)長(zhǎng)序列的DFT，如此繼續(xù)下去，最后由兩個(gè)N/2點(diǎn)長(zhǎng)序列的DFT合成N點(diǎn)長(zhǎng)序列的DFT。第五節(jié)快速傅里葉變換第五節(jié)快速傅里葉變換當(dāng)序列的長(zhǎng)度為時(shí)，根據(jù)基2時(shí)析型FFT的算法，可畫出如下蝶形圖，求出序列的DFT值。第五節(jié)快速傅里葉變換3.流程圖規(guī)律1)蝶形圖參數(shù)蝶群序號(hào)蝶距（序號(hào)差）蝶群寬（點(diǎn)數(shù)）蝶群數(shù)第一級(jí)（2點(diǎn)DFT）

第i級(jí)（點(diǎn)DFT)第L級(jí)（點(diǎn)DFT)第五節(jié)快速傅里葉變換2）每個(gè)蝶形單元的運(yùn)算，都包括乘，并與相應(yīng)的DFT結(jié)果加減各一次3）同一級(jí)中，的分布規(guī)律相同第一級(jí)（2點(diǎn)DFT）：

第二級(jí)（4點(diǎn)DFT）：；；

第i級(jí)(點(diǎn)DFT):;;...;第五節(jié)快速傅里葉變換序列輸入的自然順序十進(jìn)制二進(jìn)制碼碼位倒置結(jié)果（二進(jìn)制碼）亂序十進(jìn)制序列亂序的輸入順序4）輸入重排

第五節(jié)快速傅里葉變換4.運(yùn)算量比較N（）點(diǎn)的FFT總運(yùn)算量為復(fù)數(shù)乘復(fù)數(shù)加利用基2時(shí)析型FFT求序列的DFT同直接計(jì)算序列的DFT的復(fù)數(shù)乘運(yùn)算次數(shù)之比為第六節(jié)IDFT的快速算法（IFFT）利用FFT的程序求IFFT的方法先對(duì)DFT和IDFT兩者的定義式進(jìn)行比較，二者沒有本質(zhì)上的區(qū)別，可以利用FFT流圖（蝶形圖）來計(jì)算IFFT。第六節(jié)IDFT的快速算法（IFFT）對(duì)DFT的反變換取共軛，有與DFT的正變換式比較可知，完全可以利用FFT的計(jì)算程序，只需將作為輸入序列，并將最后結(jié)果取共軛，再除以N就得到了第七節(jié)實(shí)序列的FFT高效算法一、同時(shí)計(jì)算兩組實(shí)序列的DFT

設(shè)有兩組長(zhǎng)度均為N的實(shí)序列和，構(gòu)成新序列，根據(jù)DFT定義因?yàn)?，，有因此第七?jié)實(shí)序列的FFT高效算法解得由此說明用FFT子程序求得的DFT后，

和的DFT（、）可由的DFT()分離出來。第七節(jié)實(shí)序列的FFT高效算法二、用N點(diǎn)序列的DFT結(jié)果獲得2N點(diǎn)長(zhǎng)實(shí)序列的DFT結(jié)果將一個(gè)2N點(diǎn)的實(shí)序列按奇偶順序?qū)Ψ殖蓛蓚€(gè)序列再將和組合成N點(diǎn)的復(fù)序列可用N點(diǎn)FFT程序求出y(n)的DFT結(jié)果，然后從中分離出實(shí)數(shù)序列和的DFT結(jié)果第七節(jié)實(shí)序列的FFT高效算法

由于和是的奇偶對(duì)分序列，所以的DFT可用蝶形算法合成本節(jié)將討論兩有限長(zhǎng)序列的圓卷積與線卷積的等價(jià)條件，從而將圓卷積的快速算法應(yīng)用于線性卷積和相關(guān)的快速算法中。

第八節(jié)用FFT計(jì)算線卷積和相關(guān)運(yùn)算

主要內(nèi)容圓卷積的計(jì)算方法一圓卷積與線卷積的關(guān)系二用FFT計(jì)算有限長(zhǎng)序列的線卷積三分段快速卷積——重疊相加法四離散時(shí)間序列的相關(guān)運(yùn)算五一、圓卷積的計(jì)算方法兩個(gè)長(zhǎng)度均為（如長(zhǎng)度不等，將短序列補(bǔ)零至等長(zhǎng)）的有限長(zhǎng)序列、，其圓卷積定義為

或(5-13)(5-14)

其主要計(jì)算方法有下面幾種。

一、圓卷積的計(jì)算方法1．公式法（解析法）直接利用圓卷積的上述定義式來求解，如下例所述。例5-1設(shè)，，計(jì)算5點(diǎn)長(zhǎng)圓卷積。解：為4點(diǎn)長(zhǎng)序列，在其尾部補(bǔ)零使其成為5點(diǎn)長(zhǎng)序列，然后進(jìn)行圓卷積。根據(jù)卷積定義式，5點(diǎn)長(zhǎng)序列的圓卷積為一、圓卷積的計(jì)算方法則時(shí)則時(shí)一、圓卷積的計(jì)算方法同理；；。因此，。

一、圓卷積的計(jì)算方法2．圖形法先變量置換，然后保持其中的一個(gè)序列不動(dòng)，將另外一個(gè)序列進(jìn)行反折、圓移位，最后將兩個(gè)序列對(duì)應(yīng)的元素相乘、求和。一、圓卷積的計(jì)算方法

由于圓移位的特點(diǎn)，還可以利用同心圓法求圓卷積，如圖5-8所示。將、分別分布在兩個(gè)同心圓上，內(nèi)圓按順時(shí)針方向刻度，外圈按逆時(shí)針方向刻度，并使與對(duì)齊。然后將兩個(gè)圓上的對(duì)應(yīng)值相乘并相加，則得到。再將外圓按順時(shí)針方向旋轉(zhuǎn)一位，對(duì)應(yīng)值相乘并相加，得到，如此下去，直到求出。

一、圓卷積的計(jì)算方法

圖5-8用同心圓作圖求圓卷積

一、圓卷積的計(jì)算方法3．矩陣法利用矩陣相乘來計(jì)算圓卷積。根據(jù)圓卷積的定義，式（5-14）可用矩陣表示為即（5-15）一、圓卷積的計(jì)算方法注意:式（5-15）表示序列不動(dòng)，序列對(duì)進(jìn)行了求模運(yùn)算。為循環(huán)矩陣，其元素排列是有規(guī)律的，第一行表示的是原點(diǎn)（）不動(dòng)時(shí)，序列的反折（倒序）；接下來的各行分別是上一行序列的循環(huán)右移。一、圓卷積的計(jì)算方法4．時(shí)域圓卷積定理法利用DFT的一個(gè)重要性質(zhì)――時(shí)域圓卷積定理來計(jì)算圓卷積。若，則 二、圓卷積與線卷積的關(guān)系

線卷積具有明確的物理意義，直接計(jì)算比較復(fù)雜。對(duì)于兩個(gè)有限長(zhǎng)序列求線卷積能否用圓卷積來代替，即采用FFT計(jì)算線卷積而使兩者結(jié)果又完全相同呢？答案是肯定的，但需要滿足一個(gè)條件：就是將進(jìn)行線卷積的兩序列的長(zhǎng)度（設(shè)兩序列的點(diǎn)數(shù)分別為）均通過補(bǔ)零的辦法，加長(zhǎng)至，然后再進(jìn)行N點(diǎn)的圓卷積，則圓卷積的結(jié)果與線卷積的結(jié)果相同。二、圓卷積與線卷積的關(guān)系設(shè)分別由點(diǎn)通過補(bǔ)零，加長(zhǎng)至N點(diǎn)，其線卷積為，可表示為計(jì)算結(jié)果的長(zhǎng)度要多出一些零值，但非零值長(zhǎng)度仍為點(diǎn)。

其圓卷積為，可表示為二、圓卷積與線卷積的關(guān)系而可得（5-16）式中，下標(biāo)p表示序列的周期化；是指對(duì)線卷積進(jìn)行周期為N的延拓后得到的周期序列；兩序列的圓卷積的結(jié)果，是的主值序列。

二、圓卷積與線卷積的關(guān)系上述過程說明:加長(zhǎng)至N點(diǎn)長(zhǎng)的、兩序列的圓卷積與線卷積作周期延拓所得到的序列的主值序列相同。在這個(gè)條件下（兩序列均加長(zhǎng)至N點(diǎn)），就可以通過計(jì)算序列的圓卷積來求解線卷積。從式（5-16）的推導(dǎo)過程還可以看出，如果兩序列不加長(zhǎng)至N，其線卷積的周期延拓序列將發(fā)生重疊或混疊現(xiàn)象（因?yàn)榫€卷積長(zhǎng)度為），相應(yīng)計(jì)算出的圓卷積也將產(chǎn)生失真，圓卷積的主值序列和線卷積就不相同。三、用FFT計(jì)算有限長(zhǎng)序列的線卷積根據(jù)上述圓卷積與線卷積的關(guān)系，可以得出用FFT求解兩序列線卷積的原理框圖，如圖5-9所示。其計(jì)算的具體步驟如下1）若兩序列、的長(zhǎng)度為N，將序列加長(zhǎng)至2N－1，并應(yīng)修正為2的冪次（基2算法）；2）計(jì)算、；3）計(jì)算；4）計(jì)算。圖5-9用FFT求線性卷積三、用FFT計(jì)算有限長(zhǎng)序列的線卷積在MATLAB中直接實(shí)現(xiàn)線卷積計(jì)算的函數(shù)有conv,conv2,convn。其中conv2和convn分別用于2維、n維的卷積運(yùn)算。conv則用于向量卷積與多項(xiàng)式乘的計(jì)算，調(diào)用的格式為c＝conv（a，b）。式中，a、b表示兩個(gè)序列，c＝a*b。在MATLAB中，序列可用向量來表示，若向量a的長(zhǎng)度為na，向量b的長(zhǎng)度為nb，則向量c的長(zhǎng)度為na＋nb－1。

四、分段快速卷積——重疊相加法分段快速卷積的方法:將長(zhǎng)序列分成若干小段，每小段分別與短序列作卷積運(yùn)算，然后將所有的分段卷積結(jié)果相疊加，就是線卷積的最后結(jié)果，這種方法又稱為重疊相加法。

四、分段快速卷積——重疊相加法設(shè)的長(zhǎng)度為M，為一長(zhǎng)序列，將進(jìn)行分段，每段的長(zhǎng)度為，將每一段分別與進(jìn)行線卷積，然后將結(jié)果重疊相加，如圖5-10所示。圖5-10疊加相加法的分段以及的重疊情況

四、分段快速卷積——重疊相加法設(shè)將分為第段表示為（5-17）則

（5-18）四、分段快速卷積——重疊相加法由于長(zhǎng)度為，的長(zhǎng)度為M，故的長(zhǎng)度為，即的范圍為（5-19）將式（5-19）與式（5-17）的范圍比較，顯然比長(zhǎng)點(diǎn)，而的范圍是（5-20）四、分段快速卷積——重疊相加法將式（5-19）與式（5-20）比較，可知的后部分與的前部分，有個(gè)點(diǎn)發(fā)生重疊。這樣，對(duì)于在此范圍的每一個(gè)值，原序列和的卷積之值應(yīng)為 （5-21）這就是說，式（5-18）中的求和并不是將各段線卷積的結(jié)果簡(jiǎn)單地拼接在一起，在某些點(diǎn)上是需要前后兩段的結(jié)果重疊相加的。五、離散時(shí)間序列的相關(guān)運(yùn)算設(shè)序列，，（），稱下述運(yùn)算

為序列和的線性相關(guān)。 對(duì)和均為實(shí)序列的情形，由式（5-22）可以得到

(5-22)

（5-23）

五、離散時(shí)間序列的相關(guān)運(yùn)算若序列和是不同的兩個(gè)序列，則稱相關(guān)為互相關(guān)，若＝，則稱相關(guān)為自相關(guān)。注意：相關(guān)和卷積是兩個(gè)不同的概念，它們的區(qū)別是明顯的。除了形式上的差異，它們還有一些其他的不同。例如，對(duì)相關(guān)運(yùn)算來說，既不具有交換性，也不具有結(jié)合性。一般來說，，第九節(jié)MATLAB中用于FFT計(jì)算的函數(shù)簡(jiǎn)介

MATLAB中提供了多種實(shí)現(xiàn)快速變換的函數(shù)，如fft，ifft，fft2，ifft2，fftn，ifftn，fftshift，ifftshift等函數(shù)。由于MATLAB中沒有零下標(biāo)，因此，它采用的公式上、下標(biāo)都相應(yīng)右