MEASUREMENTINFORMATIONSIGNALANALYSISINMECHANICALENGINEERING機械工程測試?信息?信號(xìnhào)分析機械(jīxiè)科學與工程學院機械(jīxiè)電子信息工程系精品資料課件資料下載：郵箱地址：密碼：注意下載時不要刪除(shānchú)原始文件精品資料第六章數字信號分析(fēnxī)(I)

DFT與FFT精品資料§6-5現代(xiàndài)譜分析方法-最大熵譜估計§6-3FFT§6-4譜分析與譜估計§6-2DFT§6-1模擬信號離散(lísàn)化目錄精品資料6-3FFT算法(suànfǎ)6.3.1、DFT的計算(jìsuàn)工作量FFT背景兩者的差別僅在指數的符號和因子1/N.精品資料通常x(n)和WNnk都是復數，所以計算一個x(k)的值需要N次復數乘法運算，和N-1次復數加法運算。那么，所有(suǒyǒu)的X(k)就要N2次復數乘法運算，N(N-1)次復數加法運算。當N很大時，運算量將是驚人的,如N=1024，則要完成1048576次(一百多萬次)運算。難以做到實時處理。計算(jìsuàn)一個X(k)的值的計算(jìsuàn)量，如X(1)，k=1精品資料6.3.2、改進(gǎijìn)的途徑2.WNnk的對稱性和周期性得:對稱性:周期性:1.WN0=1；WNN/2=[e-j2/N]N/2=-1不必(bùbì)運算精品資料利用上述特性，可以將有些項合并，并將DFT分解為短序列(xùliè)，從而降低運算次數，提高運算速度。1965年，庫利(cooley)和圖基(Tukey)首先提出FFT算法。對于N點DFT，僅需(N/2)log2N次復數乘法運算。例如N=1024=210時，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%，速度提高20倍。精品資料6.3.3、庫利-圖基算法(suànfǎ)一、算法原理(基2FFT)(一)N/2點DFT1.先將x(n)按n的奇偶分為兩組作DFT，設N=2L，不足時，可補些零。有:n為偶數(ǒushù)時：n為奇數時：因此，按時間抽取(DIT)的FFT算法—庫利-圖基算法精品資料庫利-圖基算法(suànfǎ)所以(suǒyǐ)，上式可表示為：(n為偶數)(n為奇數)精品資料庫利-圖基算法(suànfǎ)2.兩點結論(jiélùn):(1)X1(k)，X2(k)均為N/2點的DFT。(2)X(k)=X1(k)+WNkX2(k)只能確定出X(k)的k=N/2-1個、即前一半的結果。其中,精品資料庫利-圖基算法(suànfǎ)同理，X2(N/2+k)=X2(k)，即X1(k)，X2(k)的后一半，分別(fēnbié)等于其前一半的值。由于WN/2r(k+N/2)=WN/2rk(周期性）,所以:(3)X(k)的后一半的確定精品資料庫利-圖基算法(suànfǎ)可見(kějiàn)，X(k)的后一半，也完全由X1(k)，X2(k)的前一半所確定。*N點的DFT可由兩個N/2點的DFT來計算。又由于WN(N/2+k)=WNN/2WNk=-WNk，所以精品資料4.蝶形運算(yùnsuàn)實現上式運算(yùnsuàn)的流圖稱作蝶形運算(yùnsuàn)前一半后一半（N/2個蝶形)(前一半)(后一半)1111-1由X1(k)、X2(k)表示X(k)的運算是一種特殊的運算-碟形運算精品資料5.計算(jìsuàn)工作量分析(1)N/2點的DFT運算量：復乘次數:(N/2)2=N2/4 復加次數:N/2(N/2-1)(2)兩個(liǎnɡɡè)N/2點的DFT運算量：復乘次數:N2/2 復加次數:N/2(N/2-1)(3)N/2個蝶形運算的運算量：復乘次數:N/2 復加次數:2.N/2=N復乘:復加:總共運算量:按奇、偶分組后的計算量：但是，N點DFT的復乘為N2；復加為N(N-1)；與分解后相比可知，計算工作點差不多減少一半。精品資料例如：N=8時的DFT,可以分解為兩個(liǎnɡɡè)N/2=4點的DFT。具體方法如下：(1)n為偶數時，即x(0)，x(1)，x(2)，x(3)；分別記作：進行(jìnxíng)N/2=4點的DFT，得X1(k)精品資料(2)n為奇數(jīshù)時，分別記作:進行(jìnxíng)N/2=4點的DFT，得X2(k)精品資料x1(0)=x(0)x1(1)=x(2)x1(2)=x(4)x1(3)=x(6)x2(0)=x(1)x2(1)=x(3)x2(2)=x(5)x2(3)=x(7)

X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)(3)對X1(k)和X2(k)進行(jìnxíng)蝶形運算，前半部為X(0)X(3)，后半部分為X(4)X(7)，整個過程如下圖所示:N/2點DFTN/2點DFT精品資料(二)N/4點DFT由于N=2L，所以N/2仍為偶數，可以進一步把每個N/2點的序列再按其奇偶部分分解為兩個(liǎnɡɡè)N/4的子序列。例如，n為偶數時的N/2點分解為:進行(jìnxíng)N/4點的DFT，得到(偶中偶)(偶中奇)精品資料從而(cóngér)可得到前N/4點的X1(k)后N/4點的X1(k)為：精品資料(奇中偶)(奇中奇)同樣對n為奇數時，N/2點分為兩個(liǎnɡɡè)N/4點的序列進行DFT，則有：精品資料例如(lìrú)，N=8時的DFT可分解為四個N/4的DFT，具體步驟如下：(1)將原序列(xùliè)x(n)的“偶中偶”部分：構成N/4點DFT，從而得到X3(0)，X3(1)。精品資料(2)將原序列(xùliè)x(n)的“偶中奇”部分:構成N/4點DFT，從而(cóngér)得到X4(0),X4(1)。(3)將原序列x(n)的“奇中偶”部分:構成N/4點DFT，從而得到X5(0),X5(1)。精品資料(4)將原序列(xùliè)x(n)的“奇中奇”部分:構成(gòuchéng)N/4點DFT，從而得到X6(0),X6(1)。（5）由X3(0),

X3(1),

X4(0),

X4(1)進行碟形運算,

得到X1(0),X1(1),X1(2),X1(3)。（6）由X5(0),X5(1),X6(0),X6(1)進行碟形運算,

得到X2(0),X2(1),X2(2),X2(3)。精品資料-1-1-1-2-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)（7）由X1(0),X1(1),X1(2)，X1(3)，X2(0)，X2(1)，X2(2)，X2(3)進行碟形運算(yùnsuàn)，得到X(0),X(1),X(2),X(3)X(4),X(5),X(6),X(7)。x3(0)=x1(0)=x(0)x3(1)=x1(2)=x(4)x4(0)=x1(1)=x(2)x4(1)=x1(3)=x(6)x5(0)=x2(0)=x(1)x5(1)=x2(2)=x(5)x6(0)=x2(1)=x(3)x6(1)=x2(3)=x(7)N/4DFTN/4DFTN/4DFTN/4DFT精品資料這樣(zhèyàng),又一次分解,得到四個N/4點DFT，兩級蝶形運算，其運算量有大約減少一半即為N點DFT的1/4。對于N=8時DFT，N/4點即為兩點DFT，因此精品資料亦即,精品資料-1-1-1-1-1-1-1-1-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)因此,8點DFT的FFT的運算(yùnsuàn)流圖如下x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)精品資料此FFT算法，是在時間上對輸入序列的次序是屬于偶數還是屬于奇數(jīshù)來進行分解的，所以稱作按時間抽取的算法(DIT)。二、運算量由上述分析可知，N=8需三級蝶形運算N=2=8，由此可知，N=2L共需L級蝶形運算,而且每級都由N/2個蝶形運算組成，每個蝶形運算有一次復乘，兩次復加。3精品資料因此，N點的FFT的運算量為：復乘:mF=(N/2)L=(N/2)log2N復加:aF=NL=Nlog2N由于計算機的乘法運算比加法(jiāfǎ)運算所需的時間多得多，故以乘法運算作為比較基準。精品資料三、DIT的FFT算法(suànfǎ)的特點-1-1-1-1-1-1-1-1.....1.原位運算輸入數據、中間運算結果和最后輸出(shūchū)均用同一存儲器。x(0)=X0(0)x(4)=X0(1)

x(2)=X0(2)

x(6)=X0(3)x(1)=X0(4)x(5)=X0(5)x(3)=X0(6)x(7)=X0(7)X2(0)X2(1)X2(2)X2(3)X2(4)X2(5)X2(6)X2(7)X3(0)=X(0)X3(1)=X(1)X3(2)=X(2)X3(3)=X(3)X3(4)=X(4)X3(5)=X(5)X3(6)=X(6)X3(7)=X(7)X1(0)X1(1)X1(2)X1(3)X1(4)X1(5)X1(6)X1(7)精品資料由運算流圖可知，一共有N個輸入/出行，一共有log2N=L列(級)蝶形運算(基本迭代(diédài)運算)。設用m(m=1,2,…,L)表示第m列；用k,j表示蝶形輸入數據所在的(上/下)行數(0,1,2,…,N-1)；這時任何一個蝶形運算可用下面通用式表示，即：精品資料所以(suǒyǐ)，當m=1時，則有（前兩個蝶形）精品資料當m=2時，則有(前兩個(liǎnɡɡè)蝶形)當m=3時，則有(前兩個(liǎnɡɡè)蝶形)精品資料可見，在某列進行(jìnxíng)蝶形運算的任意兩個節點(行)k和j的節點變量Xm-1(k)，Xm-1(j)就完全可以確定蝶形運算的結果Xm(k)，Xm(j)，與其它行(節點)無關。這樣，蝶形運算的兩個輸出值仍可放回蝶形運算的兩個輸入所在的存儲器中，即實現所謂原位運算。每一組(列)有N/2個蝶形運算，所以只需N個存儲單元，可以節省存儲單元。精品資料2.倒位序規律由圖可知，輸出X(k)按正常順序排列在存儲單元，而輸入(shūrù)是按順序：這種順序(shùnxù)稱作倒位序，即二進制數倒位。精品資料n0=0，(偶)n1=0n1=1n1=0n1=101010101

(n2)x(000)0乾x(100)4兌x(010)2離x(110)6震x(001)1巽x(101)5坎x(011)3艮x(111)7坤這是由奇偶分組造成的，以N=8為例說明(shuōmíng)如下：n0=1，(偶)精品資料3.倒位序實現輸入序列(xùliè)先按自然順序存入存儲單元，然后經變址運算來實現倒位序排列設輸入序列(xùliè)的序號為n，二進制為(n2n1n0)2，倒位序順序用表示，其倒位序二進制為(n0n1n2)2，例如，N=8時如下表：精品資料00

0

00

0

0010

0

11

0

0420

1

00

1

0230

1

11

1

0641

0

00

0

1151

0

11

0

1561

1

00

1

1371

1

11

1

17自然(zìrán)順序n二進制n2n1n0倒位序二進制n0n1n2倒位順序精品資料A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)變址處理(chǔlǐ)方法存儲單元(cúnchǔdānyuán)自然順序變址倒位序4.蝶形運算兩節點的距離：2m-1其中，m表示第m列，且m=1,…,L例如N=8=23，第一級(列)距離為21-1=1，第二級(列)距離為22-1=2，第三級(列)距離為23-1=4。精品資料5.WNr的確定(僅給出方法)考慮蝶形運算兩節點的距離為2m-1，蝶形運算可表為：Xm(k)=Xm-1(k)+Xm-1(k+2m-1)WNrXm(k+2m-1)=Xm-1(k)-Xm-1(k+2m-1)WNr由于N為已知，所以將r的值確定即可。為此，令k=(n2n1n0)2，再將k=(n2n1n0)2左移(L-m)位，右邊位置(wèizhi)補零，就可得到(r)2的值，即(r)2=(k)22L-m。精品資料例如(lìrú)：N=8=23(1)k=2，m=3的r值，因k=2=(010)2左移L-m=3-3=0，故r=(010)2=2；(2)k=3，m=3的r值；因k=3=(011)2左移0位，r=3；(3)k=5，m=2的r值；因k=5=(101)2左移L-m=1位，r=(010)2=2。精品資料6.存儲單元(cúnchǔdānyuán)存輸入序列(n)，n=0,1,…,N-1，計N個單元；存放系數WNr，r=0,1,…,(N/2)-1，需N/2個存儲單元(cúnchǔdānyuán)；共計(N+N/2)個存儲單元(cúnchǔdānyuán)。精品資料6.3.4IFFT算法(suànfǎ)一.稍微變動(biàndòng)FFT程序和參數可實現IFFT比較兩式可知,只要DFT的每個系數WNnk換成WN-nk，最后再乘以常數1/N就可以得到IDFT的快速算法--IFFT。另外，可以將常數1/N分配到每級運算中，1/N=1/2L=(1/2)L，也就是每級蝶形運算均乘以1/2。

精品資料利用(lìyòng)FFT程序實現IFFT二.不改(FFT)的程序(chéngxù)直接實現IFFT因為所以因此步驟為：先將X(k)取共軛，即將X(k)的虛部乘