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

13.5

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

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

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

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

43.5.1直接計(jì)算DFT的問題及改進(jìn)的途徑

DFT的運(yùn)算量

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

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

減少運(yùn)算工作量的途徑

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

算法原理按時間抽取基-2FFT算法與直接計(jì)算DFT運(yùn)算量的比較按時間抽取的FFT算法的特點(diǎn)按時間抽取FFT算法的其它形式流程圖10算法原理

設(shè)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因此，只能計(jì)算出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蝶形運(yùn)算蝶形運(yùn)算式蝶形運(yùn)算信號流圖符號

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

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

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

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

2*(N/2)(N/2－1)+2*N/2=N2/2N點(diǎn)DFT的運(yùn)算量

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

17進(jìn)一步按奇偶分解

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

則有

k=0,1,…,

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

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

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

級蝶形運(yùn)算；每級都由

個蝶形運(yùn)算組成，而每個蝶形有

次復(fù)乘、

次復(fù)加，因此每級運(yùn)算都需

次復(fù)乘和

次復(fù)加。

LN/2

N/2

12N23這樣

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

復(fù)數(shù)加法：

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

復(fù)數(shù)加法：

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

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

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

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

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

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

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

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

33

的確定

以N=8為例：

的確定

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

算法原理再把輸出X(k)按k的奇偶分組先把輸入按n的順序分成前后兩半設(shè)序列長度為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，…，則式可轉(zhuǎn)化為38令n=0，1，…，代入r=0，1，…，可得為2個N/2點(diǎn)的DFT，合起來正好是N點(diǎn)X(k)的值。39蝶形運(yùn)算將稱為蝶形運(yùn)算與時間抽選基2FFT算法中的蝶形運(yùn)算符號略有不同。40例按頻率抽取(N=8)

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

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

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

433.5.5

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

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

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

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

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

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

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

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

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

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

DFT67時域頻域（1）取樣（離散化）→周期化（2）截?。ㄓ邢揲L）↓

↓

→波皺↓

取樣←↓

（3）周期化

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

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

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

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

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

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

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

式中，

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

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

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

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