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

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

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

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

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

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

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

6、構(gòu)簡稱蝶形結(jié)，采用這種表示法，就可以將以上所討論的分解過程用流圖表示。兩個(gè)N/2點(diǎn)的DFT需要2(N/2)2=N2/2次復(fù)乘，再加上將兩個(gè)N/2點(diǎn)的DFT合成為N點(diǎn)DFT時(shí)蝶形結(jié)前的N/2次復(fù)乘，一共需要次復(fù)乘。可見，分解后運(yùn)算量大約節(jié)省了一倍。既然這樣的分解是有效的，由于N/2仍然是偶數(shù)，因此可以對兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步分解。如右圖所示：N/4點(diǎn)DFTN/4點(diǎn)DFTN=23=8的例子。N/2點(diǎn)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點(diǎn)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兩個(gè)4點(diǎn)DFT組成8點(diǎn)DFT與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4長的子序列x3(l)和x4(l)，即那么，X1(k)又可表示為式中同理，由X3(k)和X4(k)的周期性和WmN/2的對稱性Wk+N/4N/2=-WkN/2最后得到：用同樣的方法可計(jì)算出其中N/4點(diǎn)N/4點(diǎn)N/4點(diǎn)N/4點(diǎn)由四個(gè)2點(diǎn)DFT組成8點(diǎn)DFT最后剩下的是2點(diǎn)DFT，它可以用一個(gè)蝶形結(jié)表示：這樣，一個(gè)8點(diǎn)的完整的按時(shí)間抽取運(yùn)算的流圖由