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

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

1、第二章離散傅里葉變換及其快速算法§2.3快速傅里葉變換（FFT）快速傅里葉變換（FFT）是計(jì)算DFT的一種快速有效方法。從前面的討論中看到，有限長(zhǎng)序列在數(shù)字技術(shù)中占有很重要的地位。有限長(zhǎng)序列的一個(gè)重要特點(diǎn)是其頻域也可以離散化，即離散傅里葉變換（DFT）。雖然頻譜分析和DFT運(yùn)算很重要，但在很長(zhǎng)一段時(shí)間里，由于DFT運(yùn)算復(fù)雜，并沒(méi)有得到真正的運(yùn)用，而頻譜分析仍大多采用模擬信號(hào)濾波的方法解決，直到1965年首次提出DFT運(yùn)算的一種快速算法以后，情況才發(fā)生了根本變化，人們開(kāi)始認(rèn)識(shí)到DFT運(yùn)算的一些內(nèi)在規(guī)律，從而很快地發(fā)展和完善

2、了一套高速有效的運(yùn)算方法——快速付里變換（FFT）算法。FFT的出現(xiàn)，使DFT的運(yùn)算大大簡(jiǎn)化，運(yùn)算時(shí)間縮短一～二個(gè)數(shù)量級(jí)，使DFT的運(yùn)算在實(shí)際中得到廣泛應(yīng)用。1、DFT運(yùn)算的特點(diǎn)：一般，x(n)和wnkN都是復(fù)數(shù)，因此，每計(jì)算一個(gè)X(k)值，要進(jìn)行N次復(fù)數(shù)相乘，和N-1次復(fù)數(shù)相加，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ù)數(shù)相乘包括4個(gè)實(shí)數(shù)相乘和2個(gè)實(shí)數(shù)相加，例首先分析有限長(zhǎng)序列x(n)進(jìn)行一次DFT運(yùn)算所

3、需的運(yùn)算量。又每個(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（一百多萬(wàn)）次復(fù)數(shù)乘法，如果要求實(shí)時(shí)處理，則要求有很高的計(jì)算速度才能完成上述計(jì)算量。反變換IDFT與DFT的運(yùn)算結(jié)構(gòu)相同，只是多

4、乘一個(gè)常數(shù)1/N，所以二者的計(jì)算量相同。FFT算法的基本思想：考察DFT與IDFT的運(yùn)算發(fā)現(xiàn)，利用以下兩個(gè)特性可減少運(yùn)算量：1）系數(shù)是一個(gè)周期函數(shù)，它的周期性和對(duì)稱(chēng)性可用來(lái)改進(jìn)運(yùn)算，提高計(jì)算效率。例利用這些周期性和對(duì)稱(chēng)性，使DFT運(yùn)算中有些項(xiàng)可合并；2）利用的周期性和對(duì)稱(chēng)性，把長(zhǎng)度為N點(diǎn)的大點(diǎn)數(shù)的DFT運(yùn)算依次分解為若干個(gè)小點(diǎn)數(shù)的DFT。因?yàn)镈FT的計(jì)算量正比于N2，N小，計(jì)算量也就小。FFT算法正是基于這樣的基本思想發(fā)展起來(lái)的。它有多種形式，但基本上可分為兩類(lèi)：時(shí)間抽取法和頻率抽取法。又如因此2、按時(shí)間抽取的FFT（N

5、點(diǎn)DFT運(yùn)算的分解）先從一個(gè)特殊情況開(kāi)始，假定N是2的整數(shù)次方，N=2M，M：正整數(shù)首先將序列x（n）分解為兩組，一組為偶數(shù)項(xiàng)，一組為奇數(shù)項(xiàng)，將DFT運(yùn)算也相應(yīng)分為兩組：因?yàn)楣势渲凶⒁獾剑琀（k），G（k）有N/2個(gè)點(diǎn)，即k=0，1，…，N/2-1，還必須應(yīng)用系數(shù)wkN的周期性和對(duì)稱(chēng)性表示X（k）的N/2～N-1點(diǎn)：由得：可見(jiàn)，一個(gè)N點(diǎn)的DFT被分解為兩個(gè)N/2點(diǎn)的DFT，這兩個(gè)N/2點(diǎn)的DFT再合成為一個(gè)N點(diǎn)DFT.依此類(lèi)推，G(k)和H(k)可以繼續(xù)分下去，這種按時(shí)間抽取算法是在輸入序列分成越來(lái)越小的子序列上執(zhí)行DF

6、T運(yùn)算，最后再合成為Ｎ點(diǎn)的DFT。蝶形信號(hào)流圖將G(k)和H(k)合成X(k)運(yùn)算可歸結(jié)為：Wa+bWa-bW-W-1a+bWa-bWWabab蝶形運(yùn)算的簡(jiǎn)化(a)(b)圖(a)為實(shí)現(xiàn)這一運(yùn)算的一般方法，它需要兩次乘法、兩次加減法?？紤]到-bW和bW兩個(gè)乘法僅相差一負(fù)號(hào)，可將圖(a)簡(jiǎn)化成圖2.7(b)，此時(shí)僅需一次乘法、兩次加減法。圖(b)的運(yùn)算結(jié)構(gòu)像一蝴蝶通常稱(chēng)作蝶形運(yùn)算結(jié)構(gòu)簡(jiǎn)稱(chēng)蝶形結(jié)，采用這種表示法，就可以將以上所討論的分解過(guò)程用流圖表示。N=23=8的例子。N/2點(diǎn)DFTG(0)G(1)G(2)G(3)X(0)X

7、(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)x(1)x(3)x(5)x(7)WN1WN2WN3-1-1-1-1兩個(gè)4點(diǎn)DFT組成8點(diǎn)DFT按照這個(gè)辦法，繼續(xù)把N/2用２除，由于N=2M，仍然是偶數(shù)，可以被２整除，因此可以對(duì)兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步的分解。即對(duì){G(k)}和{H(k)}的計(jì)算，又可以分別通過(guò)計(jì)算兩個(gè)長(zhǎng)度為N/4=2點(diǎn)的DFT，進(jìn)一步節(jié)省計(jì)算量，見(jiàn)圖。這樣，一個(gè)８點(diǎn)的DFT就可以分解為四個(gè)２點(diǎn)的DFT。N/4點(diǎn)N

8、/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)算的流圖由于這種方法每一步分解都是按輸入時(shí)間序列是屬于偶數(shù)還是奇數(shù)來(lái)抽取的，所以稱(chēng)為“按時(shí)間抽取法”或“時(shí)間抽取法”。按時(shí)間抽取的8點(diǎn)FFT時(shí)間抽取法FFT的運(yùn)算特點(diǎn)：（1）蝶形運(yùn)算（