快速傅里葉變換.doc

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

1、第四章快速傅里葉變換有限長(zhǎng)序列可以通過(guò)離散傅里葉變換(DFT)將其頻域也離散化成有限長(zhǎng)序列.但其計(jì)算量太大,很難實(shí)時(shí)地處理問(wèn)題,因此引出了快速傅里葉變換(FFT).1965年，Cooley和Tukey提出了計(jì)算離散傅里葉變換（DFT）的快速算法，將DFT的運(yùn)算量減少了幾個(gè)數(shù)量級(jí)。從此，對(duì)快速傅里葉變換（FFT）算法的研究便不斷深入，數(shù)字信號(hào)處理這門新興學(xué)科也隨FFT的出現(xiàn)和發(fā)展而迅速發(fā)展。根據(jù)對(duì)序列分解與選取方法的不同而產(chǎn)生了FFT的多種算法，基本算法是基２DIT和基２DIF。FFT在離散傅里葉反變換、線性卷積和線性相關(guān)等方面也有重要應(yīng)用?？焖俑道锶~變換（FFT）是計(jì)算離散傅里葉變換（DFT）

2、的快速算法。DFT的定義式為=在所有復(fù)指數(shù)值的值全部已算好的情況下，要計(jì)算一個(gè)需要N次復(fù)數(shù)乘法和N－1次復(fù)數(shù)加法。算出全部N點(diǎn)共需次復(fù)數(shù)乘法和次復(fù)數(shù)加法。即計(jì)算量是與成正比的。FFT的基本思想：將大點(diǎn)數(shù)的DFT分解為若干個(gè)小點(diǎn)數(shù)DFT的組合，從而減少運(yùn)算量。因子具有以下兩個(gè)特性，可使DFT運(yùn)算量盡量分解為小點(diǎn)數(shù)的DFT運(yùn)算：（1）周期性：（2）對(duì)稱性：利用這兩個(gè)性質(zhì)，可以使DFT運(yùn)算中有些項(xiàng)合并，以減少乘法次數(shù)。例子：求當(dāng)N＝4時(shí)，X(2)的值通過(guò)合并，使乘法次數(shù)由4次減少到1次，運(yùn)算量減少。FFT的算法形式有很多種，但基本上可以分為兩大類：按時(shí)間抽?。―IT）和按頻率抽?。―IF）。4.1按

3、時(shí)間抽?。―IT）的FTT為了將大點(diǎn)數(shù)的DFT分解為小點(diǎn)數(shù)的DFT運(yùn)算，要求序列的長(zhǎng)度N為復(fù)合數(shù)，最常用的是的情況（M為正整數(shù)）。該情況下的變換稱為基2FFT。下面討論基2情況的算法。先將序列x(n)按奇偶項(xiàng)分解為兩組將DFT運(yùn)算也相應(yīng)分為兩組（因?yàn)椋┢渲?、分別是的N/2點(diǎn)的DFT至此，一個(gè)N點(diǎn)DFT被分解為兩個(gè)N/2點(diǎn)的DFT。上面是否將全部N點(diǎn)的求解出來(lái)了？分析：和只有N/2個(gè)點(diǎn)（），則由只能求出的前N/2個(gè)點(diǎn)的DFT，要求出全部N點(diǎn)的，需要找出、和的關(guān)系，其中。由式子可得化簡(jiǎn)得＝，這樣N點(diǎn)DFT可全部由下式確定出來(lái)：（＊）上式可用一個(gè)專用的碟形符號(hào)來(lái)表示，這個(gè)符號(hào)對(duì)應(yīng)一次復(fù)乘和兩次復(fù)加運(yùn)

4、算。圖　蝶形運(yùn)算符號(hào)通過(guò)這樣的分解以后，每一個(gè)N／2點(diǎn)的DFT只需要次復(fù)數(shù)乘法，兩個(gè)N/2點(diǎn)的DFT需要次復(fù)乘，再加上將兩個(gè)N／2點(diǎn)DFT合并成為N點(diǎn)DFT時(shí)有N／2次與W因子相乘，一共需要次復(fù)乘?？梢?jiàn)，通過(guò)這樣的分解，運(yùn)算量節(jié)省了近一半。因?yàn)?，N/2仍然是偶數(shù)，因此可以對(duì)兩個(gè)N/2點(diǎn)的DFT再分別作進(jìn)一步的分解，將兩個(gè)N/2點(diǎn)的DFT分解成兩個(gè)N/4點(diǎn)的DFT。例如對(duì)，可以在按其偶數(shù)部分及奇數(shù)部分進(jìn)行分解：則的運(yùn)算可相應(yīng)分為兩組：　將系數(shù)統(tǒng)一為以Ｎ為周期，即，可得同樣，對(duì)也可進(jìn)行類似的分解。一直分解下去，最后是２點(diǎn)的DFT，２點(diǎn)DFT的運(yùn)算也可用碟形符號(hào)來(lái)表示。這樣，對(duì)于一個(gè)的DFT運(yùn)算，其

5、按時(shí)間抽取的分解過(guò)程及完整流圖如下圖所示。這種方法，由于每一步分解都是按輸入序列在時(shí)域上的次序是屬于偶數(shù)還是奇數(shù)來(lái)抽取的，故稱為“時(shí)間抽取法”。分析上面的流圖，，一共要進(jìn)行M次分解，構(gòu)成了從x(n)到X(k)的M級(jí)運(yùn)算過(guò)程。每一級(jí)運(yùn)算都是由N/2個(gè)蝶形運(yùn)算構(gòu)成，因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和N次復(fù)加，則按時(shí)間抽取的M級(jí)運(yùn)算后總共需要　　　復(fù)數(shù)乘法次數(shù)：　　　復(fù)數(shù)加法次數(shù)：根據(jù)上面的流圖，分析ＦＦＴ算法的兩個(gè)特點(diǎn)，它們對(duì)ＦＦＴ的軟硬件構(gòu)成產(chǎn)生很大的影響。（１）原位運(yùn)算也稱為同址運(yùn)算，當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然存儲(chǔ)在原來(lái)的存儲(chǔ)器中，直到最后輸出，中間無(wú)需其它的存儲(chǔ)器。根據(jù)運(yùn)

6、算流圖分析原位運(yùn)算是如何進(jìn)行的。原位運(yùn)算的結(jié)構(gòu)可以節(jié)省存儲(chǔ)單元，降低設(shè)備成本。（２）變址分析運(yùn)算流圖中的輸入輸出序列的順序，輸出按順序，輸入是“碼位倒置”的順序。見(jiàn)圖。自然順序二進(jìn)制表示碼位倒置碼位倒置順序0000000010011004201001023011110641000011510110156110011371111117　　　　　　　　　碼位倒置順序在實(shí)際運(yùn)算中，直接將輸入數(shù)據(jù)x(n)按碼位倒置的順序排好輸入很不方便，一般總是先按自然順序輸入存儲(chǔ)單元，然后通過(guò)變址運(yùn)算將自然順序的存儲(chǔ)換成碼位倒置順序的存儲(chǔ)，這樣就可以進(jìn)行FFT的原位運(yùn)算。變質(zhì)的功能如圖所示。用軟件實(shí)現(xiàn)是通用采用雷德

7、（Rader）算法，算出I的倒序Ｊ以后立即將輸入數(shù)據(jù)X(I)和X(J)對(duì)換。盡管變址運(yùn)算所占運(yùn)算量的比例很小，但對(duì)某些高要求的應(yīng)用（尤其在實(shí)時(shí)信號(hào)處理中），也可設(shè)法用適當(dāng)?shù)碾娐方Y(jié)構(gòu)直接實(shí)現(xiàn)變址。例如單片數(shù)字信號(hào)處理器TMS320C25就有專用于FFT的二進(jìn)制碼變址模式。4.２按頻率抽?。―IF）的FTT除時(shí)間抽取法外，另外一種普遍使用的FFT結(jié)構(gòu)是頻率抽取法。頻率抽取法將輸入序列不是按奇、偶分組，