數(shù)字信號課件（鄭楚君）第3章2

13.5

快速傅里葉變換直接計算DFT的問題及改進的途徑按時間抽取的基2-FFT算法

按頻率抽取的基2-FFT算法

快速傅里葉逆變換(IFFT)算法

Matlab實現(xiàn)3DFT在實際應用中很重要:可以計算信號的頻譜、功率譜和線性卷積等。直接按DFT變換進行計算，當序列長度N很大時，計算量非常大，所需時間會很長。FFT并不是一種與DFT不同的變換，而是DFT的一種快速計算的算法。

43.5.1直接計算DFT的問題及改進的途徑

DFT的運算量

設復序列x(n)長度為N點，其DFT為k=0，，…，N-1（1）計算一個X(k)值的運算量復數(shù)乘法次數(shù)：N復數(shù)加法次數(shù)：N－15DFT的運算量（2）計算全部N個X(k)值的運算量復數(shù)乘法次數(shù)：N2復數(shù)加法次數(shù)：N(N－1)（3）對應的實數(shù)運算量6一次復數(shù)乘法：4次實數(shù)乘法2次實數(shù)加法＋一個X(k)

：4N次實數(shù)乘法＋2N+2(N-1)=2(2N-1)次實數(shù)加法所以整個N點DFT運算共需要：N×2(2N-1)=2N(2N-1)實數(shù)乘法次數(shù)：4N2實數(shù)加法次數(shù)：7DFT運算量的結論N點DFT的復數(shù)乘法次數(shù)舉例NN2NN22464404941612816384864256655361625651226214432102810241048576結論：當N很大時，其運算量很大，對實時性很強的信號處理來說，要求計算速度快，因此需要改進DFT的計算方法，以大大減少運算次數(shù)。8

減少運算工作量的途徑

主要原理是利用系數(shù)的以下特性對DFT進行分解：（1）對稱性（2）周期性（3）可約性另外，93.5.2按時間抽取的基2-FFT算法

算法原理按時間抽取基-2FFT算法與直接計算DFT運算量的比較按時間抽取的FFT算法的特點按時間抽取FFT算法的其它形式流程圖10算法原理

設N＝2L，將x(n)按n的奇偶分為兩組：

r=0，1，…，則11式中，X1(k)和X2(k)分別是x1(n)和x2(n)的N/2的DFT。另外，式中k的取值范圍是：0，1，…，N/2－1。12因此，只能計算出X(k)的前一半值。后一半X(k)值，N/2，N/2＋1，…，N？利用可得到同理可得13考慮到因此可得后半部分X(k)及前半部分X(k)k=0，1，…，N/2－1k=0，1，…，N/2－114蝶形運算蝶形運算式蝶形運算信號流圖符號

因此，只要求出2個N/2點的DFT，即X1(k)和X2(k)，再經(jīng)過蝶形運算就可求出全部X(k)的值，運算量大大減少。15以8點為例第一次按奇偶分解以N=8為例，分解為2個4點的DFT，然后做8/2=4次蝶形運算即可求出所有8點X(k)的值。16蝶形運算量比較復數(shù)乘法次數(shù)：

N2復數(shù)加法次數(shù)：

N(N－1)復數(shù)乘法次數(shù)：

2*(N/2)2+N/2=N2/2+N/2復數(shù)加法次數(shù)：

2*(N/2)(N/2－1)+2*N/2=N2/2N點DFT的運算量

分解一次后所需的運算量＝2個N/2的DFT＋N/2蝶形：因此通過一次分解后，運算工作量減少了差不多一半。

17進一步按奇偶分解

由于N＝2L，因而N/2仍是偶數(shù)，可以進一步把每個N/2點子序列再按其奇偶部分分解為兩個N/4點的子序列。以N/2點序列x1(r)為例

則有

k=0,1,…,

18且k=0,1,…,由此可見，一個N/2點DFT可分解成兩個N/4點DFT。同理，也可對x2(n)進行同樣的分解，求出X2(k)。19以8點為例第二次按奇偶分解20算法原理

對此例N=8，最后剩下的是4個N/4=2點的DFT，2點DFT也可以由蝶形運算來完成。以X3(k)為例。k=0,1即這說明，N=2M的DFT可全部由蝶形運算來完成。21以8點為例第三次按奇偶分解N=8按時間抽取法FFT信號流圖22按時間抽取基2-FFT算法與直接計算DFT運算量的比較

由按時間抽取法FFT的信號流圖可知，當N=2L時，共有

級蝶形運算；每級都由

個蝶形運算組成，而每個蝶形有

次復乘、

次復加，因此每級運算都需

次復乘和

次復加。

LN/2

N/2

12N23這樣

級運算總共需要：L復數(shù)乘法：

復數(shù)加法：

直接DFT算法運算量復數(shù)乘法：

復數(shù)加法：

N2N(N－1)直接計算DFT與FFT算法的計算量之比為M24FFT算法與直接DFT算法運算量的比較NN2計算量之比MNN2計算量之比M2414.01281638444836.641644.025665536102464.0864125.45122621442304113.816256328.0102410485765120204.83210288012.82048419430411264372.464404919221.4253.5.3按時間抽取的FFT算法的特點序列的逆序排列同址運算（原位運算）蝶形運算兩節(jié)點間的距離的確定26序列的逆序排列

由于x(n)被反復地按奇、偶分組，所以流圖輸入端的排列不再是順序的，但仍有規(guī)律可循：因為N=2M，

對于任意n（0≤n≤N-1)，可以用M個二進制碼表示為：

n反復按奇、偶分解時，即按二進制碼的“0”“1”分解。序列的逆序排列27倒位序的樹狀圖（N=8）

28碼位的倒位序(N=8)

自然順序n二進制數(shù)倒位序二進制數(shù)倒位序順序數(shù)000000001001100420100102301111064100001151011015611001137111111729倒位序的變址處理（N=8）30同址運算（原位運算）

某一列任何兩個節(jié)點k和j的節(jié)點變量進行蝶形運算后，得到結果為下一列k、j兩節(jié)點的節(jié)點變量，而和其他節(jié)點變量無關。這種原位運算結構可以節(jié)省存儲單元，降低設備成本。運算前運算后例同址運算（原位運算）31觀察原位運算規(guī)律32蝶形運算兩節(jié)點間的距離

以N=8為例：第一級蝶形，距離為：第二級蝶形，距離為：第三級蝶形，距離為：規(guī)律：對于共L級的蝶形而言，其m級蝶形運算的節(jié)點間的距離為124蝶形運算兩節(jié)點間的距離

33

的確定

以N=8為例：

的確定

343.5.4按頻率抽取的基2-FFT算法

算法原理再把輸出X(k)按k的奇偶分組先把輸入按n的順序分成前后兩半設序列長度為N=2L，L為整數(shù)前半子序列x(n)后半子序列

0≤n≤0≤n≤35算法原理由DFT定義得k=0，1，…，N36由于所以則k=0，1，…，N37然后按k的奇偶可將X(k)分為兩部分r=0，1，…，則式可轉化為38令n=0，1，…，代入r=0，1，…，可得為2個N/2點的DFT，合起來正好是N點X(k)的值。39蝶形運算將稱為蝶形運算與時間抽選基2FFT算法中的蝶形運算符號略有不同。40例按頻率抽取(N=8)

例按頻率抽取，將N點DFT分解為兩個N/2點DFT的組合(N=8)41

與時間抽取法的推導過程一樣，由于N=2L，N/2仍然是一個偶數(shù)，因而可以將每個N/2點DFT的輸出再分解為偶數(shù)組與奇數(shù)組，這就將N/2點DFT進一步分解為兩個N/4點DFT。N=842頻率抽取法與時間抽取法的異同

頻率抽取法輸入是自然順序，輸出是倒位序的；時間抽取法正好相反。頻率抽取法的基本蝶形與時間抽取法的基本蝶形有所不同。頻率抽取法運算量與時間抽取法相同。頻率抽取法與時間抽取法的基本蝶形是互為轉置的。

433.5.5

(IFFT)算法IDFT公式DFT公式比較可以看出，IDFT多出M個1/2可分解到M級蝶形運算中。44例頻率抽取IFFT流圖(N=8)

45快速傅里葉逆變換另一種算法3.7用DFT計算線性卷積都是非周期如何用DFT來實現(xiàn)？DFT有快速算法存在什么矛盾補零補零DFTDFT相乘IDFT483.7用FFT計算線性卷積

設x1(n)和x2(n)都是長度為L的有限長因果序列，它們的循環(huán)卷積為且由時域循環(huán)卷積定理有0≤k≤L-149用DFT計算循環(huán)卷積方框圖用DFT計算循環(huán)卷積方框圖理由：DFT運算存在快速算法（FFT）。50循環(huán)卷積與線性卷積相等的條件條件：兩個長度分別為N和M的序列，其線性卷積可用長度為L的循環(huán)卷積來代替，但必滿足條件

L≥N+M-153卷積相等條件的討論假設h(n)長度為N，x(n)長度為M，則線性卷積為循環(huán)卷積為其中，L≥max[N，M]，54由上可得上式中因此55y2(n)是y1(n)以L為周期的周期延拓序列的主值序列。

由于卷積y1(n)的長度為N+M-1，因此當循環(huán)卷積的長度L≥N+M-1時，以為L周期的周期延拓才不會出現(xiàn)混疊現(xiàn)象，此時取主值序列顯然滿足y2(n)＝y(tǒng)1(n)。說明：

沒有全部進入，如何實現(xiàn)卷積全部進入再卷積，又如何保證實時實現(xiàn)3.8分段卷積(長序列卷積的計算)數(shù)字信號處理的優(yōu)勢是“實時實現(xiàn)”，即信號進來后，經(jīng)處理后馬上輸出出去。然而：？關鍵是將分段和卷積將分成段，每段長?Overlap—addmethod疊接相加法Overlap—savemethod疊接舍去法自己看書及使用MATLAB文件來掌握另外：較短（FIR：長度在20～50之間，IIR:盡管無限長，但有限長度要小于50），可能很長，也不適宜直接卷積。633.10.2用FFT進行信號譜分析

DFT是連續(xù)傅里葉變換的近似

分析連續(xù)時間信號的頻譜,即求其傅里葉變換：

借助計算機分析其頻譜時，需要在時域和頻域離散化，即對xa(t)的取樣序列求DFT

，這時，求出的X(k)是否能代表原信號的頻譜？精度如何保證？64用DFT計算信號頻譜原理6566N點

DFT67時域頻域（1）取樣（離散化）→周期化（2）截取（有限長）↓

↓

→波皺↓

取樣←↓

（3）周期化

可見，DFT是對連續(xù)傅里葉變換的近似，誤差主要由取樣引起的頻譜混疊及信號截取引起的頻譜波皺所造成。（1）時域取樣間隔(T)應足夠??；（2）頻域取樣間隔(F)應足夠?。唬?）截取長度(T0)應足夠大?！郉FT的點數(shù)應足夠大?；虿扇〖訖嗉夹g以提高近似程度。為提高近似精度：實際中，采用DFT進行數(shù)字頻譜分析時，需要考慮的主要參數(shù)有采樣頻率和DFT點數(shù)N。

一般根據(jù)采樣定理來選擇，即；N一般由頻率分辨率F來確定，即。上面兩個參數(shù)確定后，進而得到信號的記錄長度。69譜分析的參數(shù)選擇原則

（1）fc：已知信號最高頻率定義如下參數(shù)：（2）fs：取樣頻率fs≥2fc（4）F：譜分辨率，指頻域取樣中兩相鄰點的頻率間隔（3）T：取樣周期（5）tp：信號的最小記錄長度（6）N：一個記錄長度中的取樣點數(shù)DFT的譜線間隔等于，所以，等效的頻率分辨率為

71譜分析參數(shù)間的關系參數(shù)間的關系：fs≥2fc分析：

（1）如果保持取樣點數(shù)N不變，要提高譜的分辨率，必須降低取樣頻率，取樣頻率的降低會引起譜分析范圍減少。（2）如維持fs不變，為提高譜的分辨率可以增加取樣點數(shù)N。72tp和N可按照下式選擇：≥

總之，為了提高譜分辨率，同時又照顧到譜分析范圍不減少，必須增長記錄時間，增加取樣點數(shù)。應當注意，這種提高譜分辨率的條件是時域取樣必須滿足取樣定理，甚至選取樣速率fs為信號最高頻率fc的3-5倍更好。利用DFT計算模擬信號時可能出現(xiàn)的問題１、頻域的混迭失真及參數(shù)的選擇２、截斷效應３、柵欄效應１、頻域的混迭失真及參數(shù)的選擇１）根據(jù)采樣定理，只有當采樣頻率fS大于信號的最高頻率fh兩倍時，才能避免頻域混迭。即fS>2fh。也就是抽樣間隔為T滿足Ｔ=1/fS<1/2fh。實際信號的持續(xù)時間都是有限的，從理論上來說，其頻譜寬度是無限的，在工程上總是對信號先進行低通濾波——預濾波或抗混迭濾波，限制高于的頻率分量出現(xiàn)。２）DFT得到的頻率函數(shù)也是離散的，其頻域抽樣間隔為F0，即頻率分辨力,T0=1/F0為最短信號記錄長度。為了對全部信號進行采樣，必須使抽樣點數(shù)N滿足條件２、截斷效應

在實際中遇到的序列x(n)，其長度往往是很長，甚至是無限長的，用DFT對其進行譜分析時，必須將它截斷為長度為N的有限長序列，即根據(jù)頻率卷積定理，有

式中，

其中部分稱為主瓣。假設，則|RN(ejω)||X(ejω)||Y(ejω)|ωωω2π/N-2π/Nπ/4-π/40(a)RN(ejω)的幅頻曲線(b)X(ejω)的幅頻曲線(c)Y(ejω)的幅頻曲線

序列截斷后的頻譜與原序列頻譜有著明顯的差別，這種差別對譜分析帶來兩方面的影響：1）頻譜泄露原序列x(n)的頻譜是離散譜線，經(jīng)截斷后使每根譜線都帶上一個辛格譜，就好象使譜線向兩邊延伸，通常將這種因時域上的截斷導致頻譜展寬稱之為“泄露”，顯然泄露使頻譜變得模糊，分辨率降低。2）譜間干擾因截斷使在主譜線兩邊形成許多旁瓣，引起不同分量間的干擾，稱之為譜間干擾，這不僅影響頻譜分辨率，嚴重時強信號的旁瓣可能湮滅弱信號的主譜線，或者將強信號譜的旁瓣誤認為是另一信號的譜線，從而形成假信號，使譜分析產(chǎn)生較大的偏差。

截斷效應是無法完全消除的，只能根據(jù)要求折衷選擇有關參量。首先可以取更長的數(shù)據(jù)，也就是使截斷窗加寬，當然數(shù)據(jù)太長也必然會導致存儲量和運算量增加，其次數(shù)據(jù)不要突然截斷，也就是不要加矩形窗，而是緩慢截斷，即加各種緩變的窗（如三角窗、升余弦窗等），使得窗譜的旁瓣能量更小，卷積后造成的泄露減小。３、柵欄效應

N點DFT是在頻率區(qū)間[0，2π]上對信號的頻譜進行N點等間隔采樣，得到的是若干個離散點X(k)，且它們只限制為基頻F0的整數(shù)倍，這就好象在柵欄的一邊通過縫隙看另一邊的景象，只能在離散點的地方看到真實的景象，其余部分頻譜成分被遮擋，所以稱為柵欄效應。