第五章離散傅里葉變換及其快速算法

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

2、。過(guò)程見(jiàn)圖1。A4原函數(shù)用于抽樣用于截?cái)嘟財(cái)嗪笥糜谘油囟xDFT疊加干涉卷積波IT時(shí)或t或nT圖1DFT推導(dǎo)過(guò)程示意圖Lt訂單f處理后信號(hào)的連續(xù)時(shí)間傅里葉變換：H(f),h(nT,)e-j2kn/N.5(f_kf0)f)是離散函數(shù)，僅在離散頻率點(diǎn)fkfk=k處存在沖激，強(qiáng)度為a,其0T0NTSk余各點(diǎn)為0。f)是周期函數(shù)，周期為Nf皿亠丄，每個(gè)周期內(nèi)有N個(gè)不同的幅值。0TNTT0ss時(shí)域的離散時(shí)間間隔(或周期)與頻域的周期(或離散間隔)互為倒數(shù)。2DFT及IDFT的定義(1)DFT定義：設(shè)h%丿是連續(xù)函數(shù)h(t)的N個(gè)抽樣值n0,1,n-1，這N個(gè)點(diǎ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個(gè)抽樣值k0,1,N-1這N個(gè)點(diǎn)(3)DFTN-1INTs丿丄NL1HNk0INTs、ej2兀nk/N丿e-j2兀nk/N稱(chēng)為N點(diǎn)DFT的變換核函數(shù)，ej2兀nk/N(k0,1,.,N-1)稱(chēng)為N點(diǎn)IDFT的變換核函數(shù)。它們互為共軛。(4)同樣的信號(hào)，寬度不同的DFT會(huì)有不同的結(jié)果。DFT正逆變換的對(duì)應(yīng)關(guān)系是唯一的,或者說(shuō)它們是互逆的。引入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ì)：周期性和對(duì)稱(chēng)性：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ì)離散譜定義：稱(chēng)HH、(kZ)為離散序列h(nTs)(0nN)的DFT離散譜，簡(jiǎn)稱(chēng)離kfINTS丿散譜。性質(zhì)：周期性：序列

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

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

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

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