快速離散傅立葉變換

《快速離散傅立葉變換》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。

1、第十章快速離散傅立葉變換本章的教學(xué)內(nèi)容改進(jìn)DFT計(jì)算的方法按時(shí)間抽取的FFT算法（DITFFT）按頻率抽取的FFT算法（DIFFFT）第十章快速離散傅立葉變換（1）FFT:FastFourierTransform（2）傅立葉級(jí)數(shù)和傅立葉變換理論在19世紀(jì)就已經(jīng)提出,時(shí)域離散傅立葉變換理論也在20世紀(jì)初發(fā)展完善.但由于其手工計(jì)算的復(fù)雜性,在工程實(shí)踐中并沒(méi)有得到廣泛應(yīng)用.相反,在應(yīng)用中使用廣泛的是其它一些手工計(jì)算相對(duì)簡(jiǎn)單的數(shù)學(xué)分析手段,如沃爾什變換.直到1965年,庫(kù)利-圖基提出了針對(duì)N時(shí)復(fù)合數(shù)情況的快速離散傅立葉變換算法,與傳統(tǒng)算法

2、相比降低了1～２個(gè)數(shù)量級(jí),由此引發(fā)了研究快速算法的熱潮.這些算法統(tǒng)稱(chēng)為FFT.FFT算法的廣泛應(yīng)用，不僅奠定了離散傅立葉變換在數(shù)字信號(hào)處理中的經(jīng)典地位,也極大推動(dòng)了數(shù)字信號(hào)處理應(yīng)用與發(fā)展.第一節(jié)改進(jìn)DFT計(jì)算的方法衡量算法的復(fù)雜性:乘.加法運(yùn)算次數(shù),不考慮控制調(diào)度等操作;只考慮DFT的正變換,因?yàn)?K=0,1,…,N-1DFT正變換DFT反變換反變換相對(duì)正變換:輸入取共扼;輸出取共軛并加權(quán).直接計(jì)算DFT的運(yùn)算量n=0,1,…,N-1k=0,…,N-1復(fù)數(shù)運(yùn)算對(duì)每一個(gè)k值:復(fù)乘:N復(fù)加:N-1第一節(jié)改進(jìn)DFT計(jì)算的方法對(duì)所有k:復(fù)

3、乘:復(fù)加:N(N-1)即復(fù)數(shù)運(yùn)算量與近似成正比(不考慮情況)實(shí)數(shù)運(yùn)算k=0,…,N-1第一節(jié)改進(jìn)DFT計(jì)算的方法對(duì)每一個(gè)固定k:實(shí)乘:4N實(shí)加:對(duì)所有k:實(shí)乘:4N2實(shí)加:2N(2N-1)=4N2-2N實(shí)數(shù)運(yùn)算量與近似成正比結(jié)論:直接計(jì)算DFT的乘.加運(yùn)算量近似與成正比.第一節(jié)改進(jìn)DFT計(jì)算的方法改善運(yùn)算效率的途徑（1）利用的對(duì)稱(chēng)性和周期性等特性合并運(yùn)算項(xiàng)復(fù)共軛對(duì)稱(chēng)性:對(duì)n和k的周期性:可約性特殊值第一節(jié)改進(jìn)DFT計(jì)算的方法式中其它各對(duì)稱(chēng)項(xiàng)也可以找到類(lèi)似歸并辦法.這樣乘法次數(shù)大約可減少一半.(2)大點(diǎn)數(shù)DFT逐次分解成小點(diǎn)數(shù)DFT

4、)分解正是FFT算法的基本原理第一節(jié)改進(jìn)DFT計(jì)算的方法例:利用對(duì)稱(chēng)性,可以合并對(duì)稱(chēng)項(xiàng):FFT的基本原理：為了提高DFT的運(yùn)算效率,把大點(diǎn)數(shù)DFT按倒位序逐次分解為更小點(diǎn)數(shù)DFT的合成.在分解過(guò)程中,要利用系數(shù)的對(duì)稱(chēng)性和周期性.如果算法是逐次分解時(shí)間序列得到的,那么這種分解算法稱(chēng)為按時(shí)間抽取算法.闡述按時(shí)間抽取原理最方便的方法是研究這種特殊情況.由于N為2的整數(shù)冪,可以不斷將x(n)一分為二.這就是最常用的基-2FFT算法.如果序列不滿足這個(gè)條件,可以人為地加上若干零點(diǎn)得到.第一節(jié)改進(jìn)DFT計(jì)算的方法第二節(jié)按時(shí)間抽取FFT算法算法

5、原理：假設(shè)序列x(n)長(zhǎng)為(n=0,…,N-1),由于N為偶數(shù),可以將x(n)按n為奇數(shù)和偶數(shù)分解為兩個(gè)N/2的長(zhǎng)序列,并依此逐級(jí)分解來(lái)計(jì)算x(k).是x(n)按n為奇、偶數(shù)分為2個(gè)子序列，得:第二節(jié)按時(shí)間抽取FFT算法第一級(jí)分解定義偶序列與奇序列:上式可寫(xiě)為:第二節(jié)按時(shí)間抽取FFT算法其中:k=0,…N/2-1第二節(jié)按時(shí)間抽取FFT算法上式表明一個(gè)N點(diǎn)的DFT可以分解成兩個(gè)點(diǎn)的DFT.這兩個(gè)點(diǎn)的DFT又可按式合成一個(gè)N點(diǎn)DFT一個(gè)問(wèn)題:和的長(zhǎng)度為,它們的DFT和的點(diǎn)數(shù)也為,而x(k)卻有N個(gè)點(diǎn)。利用的周期性解決這一問(wèn)題，即：第二

6、節(jié)按時(shí)間抽取FFT算法表達(dá)為前后兩個(gè)部分:前半部分后半部分k=0,…k=0,…和的周期為同樣可得把即：第二節(jié)按時(shí)間抽取FFT算法這樣只要求出0~-1區(qū)間所有和,就可以求出0~N-1區(qū)間內(nèi)全部X(k)的值.這就是FFT運(yùn)算的關(guān)鍵所在。用以下信號(hào)流圖表示為：根據(jù)流圖的形狀，上述運(yùn)算稱(chēng)為碟形運(yùn)算。第二節(jié)按時(shí)間抽取FFT算法復(fù)乘:1復(fù)加:2一次蝶形運(yùn)算:運(yùn)算分析:當(dāng)一次分解后DFT運(yùn)算的信號(hào)流圖為：第二節(jié)按時(shí)間抽取FFT算法仍為偶數(shù),可以直接計(jì)算N點(diǎn)DFT所需復(fù)乘,復(fù)加N(N-1),可見(jiàn)當(dāng)N較大時(shí),一次分解后運(yùn)算量減少近一半.由于N=(M

7、>1),經(jīng)一次分解后點(diǎn)DFT再分別分解為兩個(gè)點(diǎn)DFT的組合.進(jìn)一步把每個(gè)復(fù)乘:一次分解:2個(gè)點(diǎn)DFT+個(gè)蝶形運(yùn)算復(fù)加:第二節(jié)按時(shí)間抽取FFT算法第二級(jí)分解可得:第二節(jié)按時(shí)間抽取FFT算法與第一級(jí)分解一樣,利用和隱含的周期性,為改寫(xiě)為前，后兩部分:其中:第二節(jié)按時(shí)間抽取FFT算法由此一個(gè)點(diǎn)DFT分解成兩個(gè)點(diǎn)的DFT.其流圖為:第二節(jié)按時(shí)間抽取FFT算法也可以進(jìn)行同樣分解:第二節(jié)按時(shí)間抽取FFT算法奇序列中的偶序列,奇序列中的奇序列第二節(jié)按時(shí)間抽取FFT算法為改寫(xiě)為前,后兩部分:第二節(jié)按時(shí)間抽取FFT算法其中:系數(shù)統(tǒng)一為(今后都使用統(tǒng)

8、一的系數(shù)),這樣,一個(gè)N點(diǎn)DFT就分解成4個(gè)N/4點(diǎn)的DFT,其信號(hào)流圖為:第二節(jié)按時(shí)間抽取FFT算法根據(jù)前面的分析,第二級(jí)分解組合比第一級(jí)分解后的運(yùn)算量又降低了一半.對(duì)于N=8點(diǎn)的DFT,經(jīng)過(guò)兩次分解后,最后剩下四個(gè)N/4=2的DFT,即(k=0