離散傅里葉變換及其快速算法(I)

《離散傅里葉變換及其快速算法(I)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、2.3快速傅里葉變換(FFT)一、直接計算DFT的問題及改進的途徑二、按時間抽取的基2FFT算法三、按頻率抽取的基2FFT算法四、離散傅立葉反變換的快速算法五、N為組合數(shù)的FFT算法六、Chirp——z變換一、直接計算DFT的問題及改進的途徑1.直接計算DFT的問題長度為N的有限長序列x(n)的DFT為考慮x(n)為復數(shù)序列的一般情況，對某一個k值，直接按(1)式計算X(k)值需要N次復數(shù)乘法、(N-1)次復數(shù)加法。(1)X（k）一共有N個點，故完成全部DFT運算，需要N2次復數(shù)相乘和N（N-1）次復數(shù)相加，在這些運算中，乘法比加法復雜，需要的運算時間多，尤其是復數(shù)相乘，每個復

2、數(shù)相乘包括4個實數(shù)相乘和2個實數(shù)相加，例又每個復數(shù)相加包括2個實數(shù)相加，所以，每計算一個X（k）要進行4N次實數(shù)相乘和2N+2（N-1）=2（2N-1）次實數(shù)相加，因此，整個DFT運算需要4N2實數(shù)相乘和2N（2N-1）次實數(shù)相加。從上面的分析看到，在DFT計算中，不論是乘法和加法，運算量均與N2成正比。因此，N較大時，運算量十分可觀。例，計算N=10點的DFT，需要100次復數(shù)相乘，而N=1024點時，需要1048576（一百多萬）次復數(shù)乘法，如果要求實時處理，則要求有很高的計算速度才能完成上述計算量。反變換IDFT與DFT的運算結(jié)構(gòu)相同，只是多乘一個常數(shù)1/N，所以二者的計

3、算量相同。DFT是信號分析與處理中的一種重要變換。因直接計算DFT的計算量與變換區(qū)間長度N的平方成正比，當N較大時，計算量太大，所以在快速傅里葉變換(簡稱FFT)出現(xiàn)以前，直接用DFT算法進行譜分析和信號的實時處理是不切實際的。直到1965年發(fā)現(xiàn)了DFT的一種快速算法以后，情況才發(fā)生了根本的變化。2.減少運算量的基本途徑顯然，把N點DFT分解為幾個較短的DFT，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子具有明顯的周期性和對稱性。其周期性表現(xiàn)為其對稱性表現(xiàn)為或者二、按時間抽取的基2FFT算法按n的奇偶把x(n)分解為兩個N/2點的子序列。偶數(shù)項為一組，奇數(shù)項為一組。FFT算法基本上分為

4、兩大類時域抽取法FFT(DecimationInTimeFFT,簡稱DIT-FFT)頻域抽取法FFT(DecimationInFrequencyFFT,簡稱DIF―FFT)。為自然數(shù)1.DIF―FFT算法。設序列x(n)的長度為N，且滿足則x(n)的DFT為所以由于于是，一個N點的DFT被分解為兩個N/2點的DFT了，這兩個N/2點的DFT再按照上式合并成一個N點DFT。（1）,只有N/2個點，而卻有N個點，要用,表達全部值，還必須利用系數(shù)的周期特性。即，同樣又考慮到的對稱性：將上述三個式子代入式(1),就可將表達為前后兩部分：(2)蝶形運算流圖符號(3)式（2）、（3）可以用

5、上圖的“蝶形結(jié)”來表示。通過上述分解后，每個N/2點DFT只需要(N/2)2=N2/4次復數(shù)相乘。依此類推，X1(k)和X2(k)可以繼續(xù)分下去，這種按時間抽取算法是在輸入序列分成越來越小的子序列上執(zhí)行DFT運算，最后再合成為Ｎ點的DFT。蝶形信號流圖將X1(k)和X2(k)合成X(k)運算可歸結(jié)為：Wa+bWa-bW-W-1a+bWa-bWWabab蝶形運算的簡化(a)(b)圖(a)為實現(xiàn)這一運算的一般方法，它需要兩次乘法、兩次加減法?？紤]到-bW和bW兩個乘法僅相差一負號，可將圖(a)簡化成圖(b)，此時僅需一次乘法、兩次加減法。圖(b)的運算結(jié)構(gòu)像一蝴蝶通常稱作蝶形運算結(jié)

6、構(gòu)簡稱蝶形結(jié)，采用這種表示法，就可以將以上所討論的分解過程用流圖表示。兩個N/2點的DFT需要2(N/2)2=N2/2次復乘，再加上將兩個N/2點的DFT合成為N點DFT時蝶形結(jié)前的N/2次復乘，一共需要次復乘?？梢姡纸夂筮\算量大約節(jié)省了一倍。既然這樣的分解是有效的，由于N/2仍然是偶數(shù)，因此可以對兩個N/2點的DFT再分別作進一步分解。如右圖所示：N/4點DFTN/4點DFTN=23=8的例子。N/2點DFTG(0)G(1)G(2)G(3)X(0)X(1)X(2)X(3)x(0)x(2)x(4)x(6)N/2點DFTH(0)H(1)H(2)H(3)X(4)X(5)X(6)X

7、(7)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1兩個4點DFT組成8點DFT與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為式中同理，由X3(k)和X4(k)的周期性和WmN/2的對稱性Wk+N/4N/2=-WkN/2最后得到：用同樣的方法可計算出其中N/4點N/4點N/4點N/4點由四個2點DFT組成8點DFT最后剩下的是2點DFT，它可以用一個蝶形結(jié)表示：這樣，一個8點的完整的按時間抽取運算的流圖由