1、kk-x-n0第五章離散傅里葉變換及其快速算法1離散傅里葉變換(DFT)的推導(dǎo)(1)時域抽樣：目的：解決信號的離散化問題。效果：連續(xù)信號離散化使得信號的頻譜被周期延拓。(2)時域截斷：原因：工程上無法處理時間無限信號。方法：通過窗函數(shù)(一般用矩形窗)對信號進行逐段截取。結(jié)果：時域乘以矩形脈沖信號，頻域相當(dāng)于和抽樣函數(shù)卷積。(3)時域周期延拓：目的：要使頻率離散，就要使時域變成周期信號。方法：周期延拓中的搬移通過與5(tnT)的卷積來實現(xiàn)。表示：延拓后的波形在數(shù)學(xué)上可表示為原始波形與沖激串序列的卷積。(4)結(jié)果：周期延拓后的周期函數(shù)具有離散譜。經(jīng)抽樣、截斷和延拓后，信號時域和頻域都是離散、周期的

2、。過程見圖1。A4原函數(shù)用于抽樣用于截斷截斷后用于延拓定義DFT疊加干涉卷積波IT時或t或nT圖1DFT推導(dǎo)過程示意圖Lt訂單f處理后信號的連續(xù)時間傅里葉變換：H(f),h(nT,)e-j2kn/N.5(f_kf0)f)是離散函數(shù)，僅在離散頻率點fkfk=k處存在沖激，強度為a,其0T0NTSk余各點為0。f)是周期函數(shù)，周期為Nf皿亠丄，每個周期內(nèi)有N個不同的幅值。0TNTT0ss時域的離散時間間隔(或周期)與頻域的周期(或離散間隔)互為倒數(shù)。2DFT及IDFT的定義(1)DFT定義：設(shè)h%丿是連續(xù)函數(shù)h(t)的N個抽樣值n0,1,n-1，這N個點的寬度為N的DFT為：DFTNh(nTn0h

3、(nT)e-j2N的DFT為：DFTNh(nTn0h(nT)e-j2Knk/NAHIDFT定義：設(shè)H丄是連續(xù)頻率函數(shù)H(f)INTs丿的寬度為N的IDFT為：的n個抽樣值k0,1,N-1這N個點(3)DFTN-1INTs丿丄NL1HNk0INTs、ej2兀nk/N丿e-j2兀nk/N稱為N點DFT的變換核函數(shù)，ej2兀nk/N(k0,1,.,N-1)稱為N點IDFT的變換核函數(shù)。它們互為共軛。(4)同樣的信號，寬度不同的DFT會有不同的結(jié)果。DFT正逆變換的對應(yīng)關(guān)系是唯一的,或者說它們是互逆的。引入WN用途：(a)正逆變換的核函數(shù)分別可以表示為Wnk和W-nk。NN核函數(shù)的正交性可以表示為：L

4、knWkr)N(n-r)NNk0(c)DFT可以表示為：HLh(nT)W乎,(k=0,1,N-1)NTIsNI丿n0(ii)(d)IDFT可以表示為：h(nT)s性質(zhì)：周期性和對稱性：t1H(才“nkk0Is丿(n0,1,N-1)(a)(b)(c)(d)(e)WNej2兀1WNeWN/2ej-1WNeW#+rWWW”：NNNNWf/2+:-Wf/2W-W；NNNNWNm1(VmZ)(f)Wmne-j2兀mn/mN=e-j2兀n/N=WWmNeeWN(Vm,nZ)3離散譜的性質(zhì)離散譜定義：稱HH、(kZ)為離散序列h(nTs)(0nN)的DFT離散譜，簡稱離kfINTS丿散譜。性質(zhì)：周期性：序列

5、的N點的DFT離散譜是周期為N的序列。共扼對稱性：如果x(nTs)(0nn)為實序列，則其N點的DFT關(guān)于原點和N/2都(3)(3)具有共軛對稱性。即HkH；HNkH*；HH*-kk“-kkN,k性k22(iii)幅度對稱性：如果x(nTs)(0nN)為實序列，則其N點的DFT關(guān)于原點和N/2都具有幅度對稱性。即hII=HII；HNk=HkII;k一kN一kkHnk2Hnk2(3)改寫：(i)簡記h(nTs)為h(n)亠、1丿DFT對簡記為：h(n)DH(k)或h(n)H(k)hG)DFTlh(n)Lr(ii)(iii)(iv)(v)4DFT總結(jié)(1)(2)(3)(4)(5)(6)簡記H為H(

6、k)h(n)WNnk,n0h(n)DFT-1|H(k)=H(k)VNk0DFT求該序列具有周期性。-nkN(n0,1,，N一1)的定義是針對任意的離散序列x(nTs)中的有限個離散抽樣(0nN)的，它并不要由DFT求出的離散譜H(k)HHN嘰N/T0nt亠、NTs丿丄-f-丄-f。離散譜關(guān)于變元k的周期為NT0f0(kZ)是離散的周期函數(shù)，周期為、離散間隔為NTsN。如果稱離散譜經(jīng)過IDFT所得到的序列為重建信號，x(nTs)(nZ)，則重建信號是離散1(對應(yīng)離散譜的離散間隔的倒數(shù))、離散間隔為sss的周期函數(shù)，周期為ntToTNT/N=To丄(對應(yīng)離散譜周期的倒數(shù))。ssNNf0經(jīng)IDFT重

7、建信號的基頻就是頻域的離散間隔，或時域周期的倒數(shù)，為f11。0T0NTS實序列的離散譜關(guān)于原點和N(如果N是偶數(shù))是共軛對稱和幅度對稱的。因此，真正2有用的頻譜信息可以從0N一1范圍獲得，從低頻到高頻。2在時域和頻域oN范圍內(nèi)的N點分別是各自的主值區(qū)間或主值周期。5DFT性質(zhì)(1)線性性：對任意常數(shù)a(1mM)，有DFTm乙ax(n)mmm1aDFTL(n)mmm1(2)奇偶虛實性：DFT的反褶、平移：先把有限長序列周期延拓，再作相應(yīng)反褶或平移，最后取主值區(qū)間的序列作為最終結(jié)果。DFT有如下的奇偶虛實特性：奇奇；偶偶；實偶實偶；實奇虛奇；實(實偶)+j(實奇)；實(r-L)對偶結(jié)點的關(guān)系如圖2

8、所示：圖2FFT中對偶結(jié)點關(guān)系圖旋轉(zhuǎn)因子：Wk被稱為旋轉(zhuǎn)因子，可預(yù)先算好并保存。N整序：經(jīng)過r次迭代后，得到結(jié)果xCkk)，實際結(jié)果應(yīng)是x虹kk,，r01r1br110b所以流程的最后一步是按下標(biāo)的正常二進制順序?qū)Y(jié)果進行整序。FFT算法特點：(N=2r)共需r次迭代；第L(1Lr)次迭代對偶結(jié)點的偶距為KL_KL=2r-L=N/2L,因此一組結(jié)點覆蓋的序號個數(shù)是2(K-K)=N。2L-1第L(1Lr)次迭代結(jié)點的組數(shù)為N/12(KlKjL2L-1。wpl可以預(yù)先計算好，而且P的變化范圍是0N一1。NL2FFT算法流程：(N=2r)初女口化：x0(n)1x(n),0nN-1；第L(1Lr)次迭代：下標(biāo)控制變量初始化K=0；L“結(jié)點對”的個數(shù)初始化num=0；WHILE(num)DO2l按對偶結(jié)點對的計算公式進行置位運算，得到x(K)和x(K)的值；LLLLK1K+1；num1num+1；LL跳過已經(jīng)計算過的結(jié)點(即上面K所對應(yīng)的那些結(jié)點)：g+=N/2l；如果kN，轉(zhuǎn)到b)繼續(xù)計算下一組結(jié)點；否則結(jié)束本次迭代。當(dāng)r次迭代全部完成后，對結(jié)果x(k)(0kN1)按下標(biāo)二進制位進行整序，從而得到結(jié)果X(k)(0kN-1)。(6)FFT算法復(fù)雜度分析：(N=2r，Wk預(yù)先算好)N一個對偶結(jié)點對的計算需要2次