數(shù)字信號(hào)處理第三版 程佩青 第4章 快速傅立葉變換

《數(shù)字信號(hào)處理第三版 程佩青 第4章 快速傅立葉變換》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)字信號(hào)處理第三版 程佩青 第4章 快速傅立葉變換（30頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第4章 快速傅里葉變換(FFT)4.1 引言4.2 基2FFT算法4.3 進(jìn)一步減少運(yùn)算量的措施第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2 基2FFT算法 一般情況下，x(n)為復(fù)數(shù)序列，對(duì)某一個(gè)k值，直接按(4.2.1)式計(jì)算一個(gè)系數(shù)X(k)值需要：復(fù)數(shù)乘法：N次 復(fù)數(shù)加法：(N-1)次計(jì)算全部X(k)值需要：N2次 N(N-1)次 當(dāng)N1時(shí)，N(N-1)N2；隨著N增大復(fù)乘、復(fù)加次數(shù)非線性增大。(4.2.1)4.2.1 直接計(jì)算直接計(jì)算DFT的特點(diǎn)及減少運(yùn)算量的基本途徑的特點(diǎn)及減少運(yùn)算量的基本途徑 一、一、直接計(jì)算直接計(jì)算DF

2、T的運(yùn)算量的運(yùn)算量 長(zhǎng)度為長(zhǎng)度為N的有限長(zhǎng)序列的有限長(zhǎng)序列x(n)的的DFT為：為：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)二、減少運(yùn)算量的基本途徑 在DFT定義式中只有兩種運(yùn)算：x(n)與WmN的乘和加，WmN的特性對(duì)運(yùn)算量必有影響。（1）根據(jù)旋轉(zhuǎn)因子WmN的周期性、對(duì)稱性和特殊值減少乘法運(yùn)算次數(shù)。WmN的的可約性可約性為：為：WmN的的對(duì)稱性對(duì)稱性表現(xiàn)為：表現(xiàn)為：WmN的的周期性周期性表現(xiàn)為：表現(xiàn)為：(4.2.2)或者或者(4.2.3)WmN的的特殊值特殊值為：為：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)（2）把）把N點(diǎn)點(diǎn)DFT分解為分解為幾個(gè)較短幾個(gè)較短DFT的組合的

3、組合，可使乘法次可使乘法次數(shù)大大減少。數(shù)大大減少。v FFT算法就是不斷地算法就是不斷地把長(zhǎng)序列的把長(zhǎng)序列的DFT分解分解成幾個(gè)短序列的成幾個(gè)短序列的DFT，并利用并利用旋轉(zhuǎn)因子旋轉(zhuǎn)因子的周期性和對(duì)稱性的周期性和對(duì)稱性來(lái)減少來(lái)減少DFT的運(yùn)算次的運(yùn)算次數(shù)。數(shù)。因?yàn)?，因?yàn)?，DFT的運(yùn)算次數(shù)的運(yùn)算次數(shù) N2若若序列長(zhǎng)度序列長(zhǎng)度N，則運(yùn)算次數(shù)則運(yùn)算次數(shù)。最常用的算法是基最常用的算法是基2-FFT(N2M)。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.2 時(shí)域抽取法（DIT）基2-FFT基本原理 根據(jù)減少運(yùn)算量的途徑，巧妙地在時(shí)域或頻域進(jìn)行不同的抽取分解與組合，可得到不同的快速算法。FF

4、T算法基本上分為兩大類：時(shí)域抽取法FFT(Decimation In Time-FFT，DIT-FFT)頻域抽取法FFT(Decimation In Frequency-FFT，DIF-FFT)v 我們介紹基2DIT-FFT算法。所謂基2是序列x(n)的長(zhǎng)度N滿足：為自然數(shù)為自然數(shù) （1）算法思想）算法思想：進(jìn)行時(shí)域：進(jìn)行時(shí)域 M 級(jí)奇偶抽取，并利用：級(jí)奇偶抽取，并利用：將將N點(diǎn)點(diǎn)DFT變成變成 M 級(jí)蝶形運(yùn)算。級(jí)蝶形運(yùn)算。（2）特點(diǎn)）特點(diǎn)：運(yùn)算流程圖結(jié)構(gòu)規(guī)則，可原位計(jì)算，程序簡(jiǎn)單。：運(yùn)算流程圖結(jié)構(gòu)規(guī)則，可原位計(jì)算，程序簡(jiǎn)單。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)設(shè)序列x(n)的長(zhǎng)

5、度為N，且滿足：為自然數(shù)為自然數(shù)按按n的奇偶把的奇偶把x(n)分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的子序列：點(diǎn)的子序列：則則x(n)的的DFT為：為：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)所以所以由于由于其中其中X1(k)和和X2(k)分別為分別為x1(r)和和x2(r)的的 N/2 點(diǎn)點(diǎn)DFTk=0,1,N-1 由于X1(k)和X2(k)均以N/2為周期，則由復(fù)指數(shù)序列的周期性可得:雖然雖然k=0,1,N-1，但從此式只能方便地但從此式只能方便地得到得到N/2個(gè)個(gè)DFT系數(shù)，那么，還有系數(shù)，那么，還有N/2個(gè)個(gè)DFT系數(shù)如何方便地得到呢？系數(shù)如何方便地得到呢？第第4章章 快速傅里葉變換快

6、速傅里葉變換(FFT)所以所以:另外由旋轉(zhuǎn)因子另外由旋轉(zhuǎn)因子WmN的的對(duì)稱性對(duì)稱性：(4.2.7)(4.2.8)這樣將這樣將N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT運(yùn)算，用如圖所示運(yùn)算，用如圖所示的的流圖符號(hào)（蝶形）流圖符號(hào)（蝶形）表示。表示。要完成一個(gè)蝶形運(yùn)算，要完成一個(gè)蝶形運(yùn)算，需一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運(yùn)算。需一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運(yùn)算。僅經(jīng)過(guò)一次分解，就使僅經(jīng)過(guò)一次分解，就使運(yùn)算量減少近一半：運(yùn)算量減少近一半：N2(N2/4)+(N2/4)+N/2第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖圖4.2.2 N點(diǎn)點(diǎn)DFT的一次時(shí)域抽取分解圖的一次時(shí)域抽取分解圖(N=8

7、)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)由于N=2M，與第一次分解相同，將x1(r)按奇偶分解成兩個(gè)N/4長(zhǎng)的子序列x3(l)和x4(l)，即：那么，那么，X1(k)又可表示為：又可表示為：式中：式中：N/4點(diǎn)點(diǎn)DFT(4.2.10)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)用同樣的方法，將x2(r)按奇偶分解，可得：其中其中l(wèi)=0l=0N/4點(diǎn)點(diǎn)DFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖圖4.2.3 N點(diǎn)點(diǎn)DFT的第二次時(shí)域抽取分解圖的第二次時(shí)域抽取分解圖(N=8)(4.2.10)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)圖圖4.2.4 N點(diǎn)點(diǎn)DI

8、T-FFT運(yùn)算流圖運(yùn)算流圖(N=8)N=8時(shí)，時(shí)，x3(l)和和x4(l)已是兩個(gè)長(zhǎng)度為已是兩個(gè)長(zhǎng)度為2的子序列的子序列：經(jīng)過(guò)經(jīng)過(guò)M-1次分解，將次分解，將N點(diǎn)點(diǎn)DFT分解成了分解成了N/2個(gè)個(gè)2點(diǎn)的點(diǎn)的DFT，因此因此N=2M時(shí)，時(shí)，F(xiàn)FT總共需要總共需要M級(jí)運(yùn)算，每級(jí)級(jí)運(yùn)算，每級(jí)N/2個(gè)蝶形。個(gè)蝶形。WN/21=WN2第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.3 DITFFT算法與直接計(jì)算DFT運(yùn)算量的比較每一級(jí)運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個(gè)蝶形需要兩次復(fù)數(shù)加法)。所以，M級(jí)運(yùn)算共需運(yùn)算量為：復(fù)數(shù)乘法：m(M)=（N/2）M=（N/2）log2 N復(fù)數(shù)加法：a(

9、M)=N M=N log2 N例如，例如，N=210=1024時(shí)時(shí)直接計(jì)算FFT算法 在實(shí)際運(yùn)算中，在實(shí)際運(yùn)算中，F(xiàn)FT的運(yùn)算量還要減少，因?yàn)榈倪\(yùn)算量還要減少，因?yàn)閃NN=1，WN0=1，WNN/2=-1，WNN/4=-j，此時(shí)不需進(jìn)行復(fù)數(shù)乘法。此時(shí)不需進(jìn)行復(fù)數(shù)乘法。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.4 DIT-FFT的實(shí)現(xiàn) 1.原位計(jì)算 DIT-FFT的運(yùn)算過(guò)程很有規(guī)律。N=2M點(diǎn)的FFT共進(jìn)行M級(jí)運(yùn)算，每級(jí)由N/2個(gè)蝶形運(yùn)算組成。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一形

10、有用，而且每個(gè)蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一條水平線上，即計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù)可立條水平線上，即計(jì)算完一個(gè)蝶形后，所得輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存貯單元。即存入原輸入數(shù)據(jù)所占用的存貯單元。這這種種利利用用同同一一存存貯貯單單元元存存貯貯蝶蝶形形計(jì)計(jì)算算輸輸入入、輸輸出出數(shù)數(shù)據(jù)的方法稱為據(jù)的方法稱為原位原位(址址)計(jì)算計(jì)算。原位計(jì)算可節(jié)省大量?jī)?nèi)存，使設(shè)備成本降低。原位計(jì)算可節(jié)省大量?jī)?nèi)存，使設(shè)備成本降低。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)2 旋轉(zhuǎn)因子的變化規(guī)律旋轉(zhuǎn)因子的變化規(guī)律如上所述，如上所述，N點(diǎn)點(diǎn)DIT-FFT運(yùn)算流圖中，每級(jí)都有運(yùn)算流圖中，每級(jí)都有N/

11、2個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為個(gè)蝶形。每個(gè)蝶形都要乘以因子，稱其為旋轉(zhuǎn)因子旋轉(zhuǎn)因子，p為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子和循環(huán)方式都為旋轉(zhuǎn)因子的指數(shù)。但各級(jí)的旋轉(zhuǎn)因子和循環(huán)方式都有所不同。有所不同。用用L表示從左到右的運(yùn)算級(jí)數(shù)表示從左到右的運(yùn)算級(jí)數(shù)(L=1，2，M)。觀察圖觀察圖4.2.4不難發(fā)現(xiàn)，第不難發(fā)現(xiàn)，第L級(jí)共有級(jí)共有2L1個(gè)不同的旋轉(zhuǎn)個(gè)不同的旋轉(zhuǎn)因子。因子。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)對(duì)N=2M的一般情況，第L級(jí)的旋轉(zhuǎn)因子為第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)第第4章章 快速傅里葉變換快速傅

12、里葉變換(FFT)5、序列的倒序、序列的倒序DIT-FFT算法的輸入序列的排序看起來(lái)似算法的輸入序列的排序看起來(lái)似乎很亂，但實(shí)際排序是很有規(guī)律的。乎很亂，但實(shí)際排序是很有規(guī)律的。實(shí)現(xiàn)按時(shí)間抽取實(shí)現(xiàn)按時(shí)間抽取FFT算法的算法的關(guān)鍵關(guān)鍵是將輸入數(shù)據(jù)排列成滿足是將輸入數(shù)據(jù)排列成滿足連續(xù)運(yùn)用奇偶分解所需的次序。連續(xù)運(yùn)用奇偶分解所需的次序。N=2M，原輸入序列的順序原輸入序列的順序表示表示為：為：n=(nM-1nM-2n1n0)2 對(duì)對(duì)輸輸入入數(shù)數(shù)據(jù)據(jù)次次序序的的變變化化可可根根據(jù)據(jù)一一個(gè)個(gè)簡(jiǎn)簡(jiǎn)單單的的位位對(duì)對(duì)換換規(guī)規(guī)則則進(jìn)進(jìn)行行（稱為倒位序）：（稱為倒位序）：n=(n0n1 n M-2 nM-1)2v

13、 當(dāng)把輸入數(shù)據(jù)進(jìn)行了重新排序，則輸出結(jié)果是正確的次序。當(dāng)把輸入數(shù)據(jù)進(jìn)行了重新排序，則輸出結(jié)果是正確的次序。例：例：n=23，輸入序輸入序“6”重新排序后為重新排序后為“3”，因?yàn)橐驗(yàn)?=1102倒位倒位序后序后n=0112=3。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)0 1 2 3 4 5 6 7 奇偶抽取奇偶抽取0 2 4 6 1 3 5 7 奇偶抽取奇偶抽取0 4 2 6 1 5 3 7倒位序倒位序表表4.2.1 順序順序和倒序二進(jìn)和倒序二進(jìn)制數(shù)對(duì)照表制數(shù)對(duì)照表第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.5頻域抽取基2FFT算法算法的推導(dǎo)頻域抽取算法頻域抽取算法頻域

14、抽取算法頻域抽取算法是把時(shí)間序列是把時(shí)間序列前后對(duì)半分解為兩個(gè)長(zhǎng)前后對(duì)半分解為兩個(gè)長(zhǎng)為為N/2N/2點(diǎn)的序列，則：點(diǎn)的序列，則：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)的的N N點(diǎn)點(diǎn)DFTDFT按按 k k的奇偶分組可分為兩個(gè)的奇偶分組可分為兩個(gè)N/2N/2的的DFTDFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT)這一結(jié)論表明：這一結(jié)論表明：求求求求 的的的的N N點(diǎn)點(diǎn)點(diǎn)點(diǎn)DFT DFT 再次分解成再次分解成再次分解成再次分解成 求兩個(gè)求兩個(gè)求兩個(gè)求兩個(gè)N/2N/2 點(diǎn)點(diǎn)點(diǎn)點(diǎn)DFTDFTDIF-FFT的蝶式運(yùn)算流圖第第4章章 快速傅里葉變換快速傅里葉變換(FFT)DIF-FF

15、T的一次分解運(yùn)算流圖先蝶式運(yùn)算，后先蝶式運(yùn)算，后先蝶式運(yùn)算，后先蝶式運(yùn)算，后 DFTDFT。例如：。例如：。例如：。例如：N=8N=8時(shí)時(shí)時(shí)時(shí)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)DIF-FFT的二次分解運(yùn)算流圖通常通常 N/2N/2仍然為仍然為 2 2的整數(shù)冪，繼續(xù)將的整數(shù)冪，繼續(xù)將 N/2N/2點(diǎn)點(diǎn)DFTDFT分成偶數(shù)分成偶數(shù)組和奇數(shù)組，這樣每個(gè)組和奇數(shù)組，這樣每個(gè) N/2N/2點(diǎn)點(diǎn)DFTDFT又可分解成兩個(gè)又可分解成兩個(gè) N/4N/4點(diǎn)點(diǎn)DFTDFT，其輸入序列分別是，其輸入序列分別是和和按上下對(duì)半分開(kāi)后通按上下對(duì)半分開(kāi)后通過(guò)蝶式運(yùn)算構(gòu)成的過(guò)蝶式運(yùn)算構(gòu)成的 4 4個(gè)子序列，如

16、下圖所示：個(gè)子序列，如下圖所示：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)按照以上方法繼續(xù)分解下去，經(jīng)過(guò)按照以上方法繼續(xù)分解下去，經(jīng)過(guò) M-1M-1 次分解，最后分次分解，最后分解為解為 N/2N/2 個(gè)兩點(diǎn)個(gè)兩點(diǎn)DFTDFT，這，這 N/2N/2個(gè)個(gè)2 2點(diǎn)點(diǎn)DFTDFT的輸出就是的輸出就是 NN點(diǎn)點(diǎn)DFTDFT的結(jié)果的結(jié)果X X(k k)，如下圖所示：，如下圖所示：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)有關(guān)說(shuō)明以上給出了以上給出了以上給出了以上給出了 N=8 N=8 時(shí)完整的時(shí)完整的時(shí)完整的時(shí)完整的 DIF-FFTDIF-FFT 的運(yùn)算流圖。由于的運(yùn)算流圖。由于的運(yùn)算流

17、圖。由于的運(yùn)算流圖。由于這種方法是這種方法是這種方法是這種方法是 按按按按 在頻域進(jìn)行奇偶分解，因此稱之為在頻域進(jìn)行奇偶分解，因此稱之為在頻域進(jìn)行奇偶分解，因此稱之為在頻域進(jìn)行奇偶分解，因此稱之為頻域抽取基頻域抽取基頻域抽取基頻域抽取基2 2 運(yùn)算運(yùn)算運(yùn)算運(yùn)算。比較比較比較比較與與與與相同點(diǎn)：相同點(diǎn)：相同點(diǎn)：相同點(diǎn)：運(yùn)算次數(shù)與存儲(chǔ)量相同運(yùn)算次數(shù)與存儲(chǔ)量相同運(yùn)算次數(shù)與存儲(chǔ)量相同運(yùn)算次數(shù)與存儲(chǔ)量相同不同點(diǎn)：不同點(diǎn)：不同點(diǎn)：不同點(diǎn)：輸入序列為自然序列而輸輸入序列為自然序列而輸輸入序列為自然序列而輸輸入序列為自然序列而輸出為碼位倒置序列出為碼位倒置序列出為碼位倒置序列出為碼位倒置序列 蝶式運(yùn)算過(guò)程不同

18、蝶式運(yùn)算過(guò)程不同蝶式運(yùn)算過(guò)程不同蝶式運(yùn)算過(guò)程不同 是序列先乘旋轉(zhuǎn)因子后相加減是序列先乘旋轉(zhuǎn)因子后相加減是序列先乘旋轉(zhuǎn)因子后相加減是序列先乘旋轉(zhuǎn)因子后相加減 是序列先相加減后乘旋轉(zhuǎn)因子是序列先相加減后乘旋轉(zhuǎn)因子是序列先相加減后乘旋轉(zhuǎn)因子是序列先相加減后乘旋轉(zhuǎn)因子第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.6 IDFT的高效算法 上述FFT算法流圖也可以用于IDFT(Inverse Discrete Fourier Transform)。比較DFT和IDFT的運(yùn)算公式：v只要將只要將FFT的轉(zhuǎn)旋的轉(zhuǎn)旋因子因子WpN改為改為W-pN，最后輸出乘以最后輸出乘以1/N，輸入用輸入用X(k)

19、，則輸出就是則輸出就是 x(n)。由此，可以用由此，可以用FFT來(lái)完成來(lái)完成 IFFT。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果希望直接調(diào)用如果希望直接調(diào)用FFTFFT子程序計(jì)算子程序計(jì)算IFFTIFFT，則可用下面的方法：則可用下面的方法：這種方法雖然用了兩次取共軛運(yùn)算，但可以用同一個(gè)這種方法雖然用了兩次取共軛運(yùn)算，但可以用同一個(gè)FFT子程序，因而用起來(lái)很方便。子程序，因而用起來(lái)很方便。把把X X*(k)(k)作作為為輸輸入入，用用一一個(gè)個(gè)FFTFFT可可得得到到 N N x x*(n)(n)，對(duì)對(duì)此此再再求復(fù)共扼并除以求復(fù)共扼并除以N N就得到所需的反變換就得到所需的反變換x(n)x(n)。