《數(shù)字信號處理第三版 程佩青 第4章 快速傅立葉變換》由會員分享，可在線閱讀，更多相關(guān)《數(shù)字信號處理第三版 程佩青 第4章 快速傅立葉變換（30頁珍藏版）》請在裝配圖網(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ù)序列，對某一個k值，直接按(4.2.1)式計算一個系數(shù)X(k)值需要：復(fù)數(shù)乘法：N次 復(fù)數(shù)加法：(N-1)次計算全部X(k)值需要：N2次 N(N-1)次 當(dāng)N1時，N(N-1)N2；隨著N增大復(fù)乘、復(fù)加次數(shù)非線性增大。(4.2.1)4.2.1 直接計算直接計算DFT的特點(diǎn)及減少運(yùn)算量的基本途徑的特點(diǎn)及減少運(yùn)算量的基本途徑 一、一、直接計算直接計算DF

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

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

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

5、度為N，且滿足：為自然數(shù)為自然數(shù)按按n的奇偶把的奇偶把x(n)分解為兩個分解為兩個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個個DFT系數(shù)，那么，還有系數(shù)，那么，還有N/2個個DFT系數(shù)如何方便地得到呢？系數(shù)如何方便地得到呢？第第4章章 快速傅里葉變換快

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

7、)第第4章章 快速傅里葉變換快速傅里葉變換(FFT)由于N=2M，與第一次分解相同，將x1(r)按奇偶分解成兩個N/4長的子序列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的第二次時域抽取分解圖的第二次時域抽取分解圖(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時，時，x3(l)和和x4(l)已是兩個長度為已是兩個長度為2的子序列的子序列：經(jīng)過經(jīng)過M-1次分解，將次分解，將N點(diǎn)點(diǎn)DFT分解成了分解成了N/2個個2點(diǎn)的點(diǎn)的DFT，因此因此N=2M時，時，F(xiàn)FT總共需要總共需要M級運(yùn)算，每級級運(yùn)算，每級N/2個蝶形。個蝶形。WN/21=WN2第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.3 DITFFT算法與直接計算DFT運(yùn)算量的比較每一級運(yùn)算都需要N/2次復(fù)數(shù)乘和N次復(fù)數(shù)加(每個蝶形需要兩次復(fù)數(shù)加法)。所以，M級運(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時時直接計算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，此時不需進(jìn)行復(fù)數(shù)乘法。此時不需進(jìn)行復(fù)數(shù)乘法。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.4 DIT-FFT的實(shí)現(xiàn) 1.原位計算 DIT-FFT的運(yùn)算過程很有規(guī)律。N=2M點(diǎn)的FFT共進(jìn)行M級運(yùn)算，每級由N/2個蝶形運(yùn)算組成。同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶同一級中，每個蝶形的兩個輸入數(shù)據(jù)只對計算本蝶形有用，而且每個蝶形的輸入、輸出數(shù)據(jù)結(jié)點(diǎn)又同在一形

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

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

12、里葉變換(FFT)5、序列的倒序、序列的倒序DIT-FFT算法的輸入序列的排序看起來似算法的輸入序列的排序看起來似乎很亂，但實(shí)際排序是很有規(guī)律的。乎很亂，但實(shí)際排序是很有規(guī)律的。實(shí)現(xiàn)按時間抽取實(shí)現(xiàn)按時間抽取FFT算法的算法的關(guān)鍵關(guān)鍵是將輸入數(shù)據(jù)排列成滿足是將輸入數(shù)據(jù)排列成滿足連續(xù)運(yùn)用奇偶分解所需的次序。連續(xù)運(yùn)用奇偶分解所需的次序。N=2M，原輸入序列的順序原輸入序列的順序表示表示為：為：n=(nM-1nM-2n1n0)2 對對輸輸入入數(shù)數(shù)據(jù)據(jù)次次序序的的變變化化可可根根據(jù)據(jù)一一個個簡簡單單的的位位對對換換規(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ù)對照表制數(shù)對照表第第4章章 快速傅里葉變換快速傅里葉變換(FFT)4.2.5頻域抽取基2FFT算法算法的推導(dǎo)頻域抽取算法頻域抽取算法頻域

14、抽取算法頻域抽取算法是把時間序列是把時間序列前后對半分解為兩個長前后對半分解為兩個長為為N/2N/2點(diǎn)的序列，則：點(diǎn)的序列，則：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)的的N N點(diǎn)點(diǎn)DFTDFT按按 k k的奇偶分組可分為兩個的奇偶分組可分為兩個N/2N/2的的DFTDFT第第4章章 快速傅里葉變換快速傅里葉變換(FFT)這一結(jié)論表明：這一結(jié)論表明：求求求求 的的的的N N點(diǎn)點(diǎn)點(diǎn)點(diǎn)DFT DFT 再次分解成再次分解成再次分解成再次分解成 求兩個求兩個求兩個求兩個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時時時時第第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ù)組，這樣每個組和奇數(shù)組，這樣每個 N/2N/2點(diǎn)點(diǎn)DFTDFT又可分解成兩個又可分解成兩個 N/4N/4點(diǎn)點(diǎn)DFTDFT，其輸入序列分別是，其輸入序列分別是和和按上下對半分開后通按上下對半分開后通過蝶式運(yùn)算構(gòu)成的過蝶式運(yùn)算構(gòu)成的 4 4個子序列，如

16、下圖所示：個子序列，如下圖所示：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)按照以上方法繼續(xù)分解下去，經(jīng)過按照以上方法繼續(xù)分解下去，經(jīng)過 M-1M-1 次分解，最后分次分解，最后分解為解為 N/2N/2 個兩點(diǎn)個兩點(diǎn)DFTDFT，這，這 N/2N/2個個2 2點(diǎn)點(diǎn)DFTDFT的輸出就是的輸出就是 NN點(diǎn)點(diǎn)DFTDFT的結(jié)果的結(jié)果X X(k k)，如下圖所示：，如下圖所示：第第4章章 快速傅里葉變換快速傅里葉變換(FFT)有關(guān)說明以上給出了以上給出了以上給出了以上給出了 N=8 N=8 時完整的時完整的時完整的時完整的 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ù)與存儲量相同運(yùn)算次數(shù)與存儲量相同運(yùn)算次數(shù)與存儲量相同運(yùn)算次數(shù)與存儲量相同不同點(diǎn)：不同點(diǎn)：不同點(diǎn)：不同點(diǎn)：輸入序列為自然序列而輸輸入序列為自然序列而輸輸入序列為自然序列而輸輸入序列為自然序列而輸出為碼位倒置序列出為碼位倒置序列出為碼位倒置序列出為碼位倒置序列 蝶式運(yùn)算過程不同

18、蝶式運(yùn)算過程不同蝶式運(yùn)算過程不同蝶式運(yùn)算過程不同 是序列先乘旋轉(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來完成來完成 IFFT。第第4章章 快速傅里葉變換快速傅里葉變換(FFT)如果希望直接調(diào)用如果希望直接調(diào)用FFTFFT子程序計算子程序計算IFFTIFFT，則可用下面的方法：則可用下面的方法：這種方法雖然用了兩次取共軛運(yùn)算，但可以用同一個這種方法雖然用了兩次取共軛運(yùn)算，但可以用同一個FFT子程序，因而用起來很方便。子程序，因而用起來很方便。把把X X*(k)(k)作作為為輸輸入入，用用一一個個FFTFFT可可得得到到 N N x x*(n)(n)，對對此此再再求復(fù)共扼并除以求復(fù)共扼并除以N N就得到所需的反變換就得到所需的反變換x(n)x(n)。