信號分析與處理15

1、第十章第十章 快速離散傅立葉變換快速離散傅立葉變換 本章的教學內容本章的教學內容 改進改進DFTDFT計算的方法計算的方法 按時間抽取的按時間抽取的FFTFFT算法（算法（DIT FFT） 按頻率抽取的按頻率抽取的FFTFFT算法（算法（DIF FFT）第第十章章 快速離散傅立葉變換快速離散傅立葉變換 （1） FFT:Fast Fourier Transform（2）傅立葉級數和傅立葉變換理論在19世紀就已經提出,時域離散傅立葉變換理論也在20世紀初發(fā)展完善.但由于其手工計算的復雜性,在工程實踐中并沒有得到廣泛應用.相反,在應用中使用廣泛的是其它一些手工計算相對簡單的數學分析手段,如沃爾什變換

2、.直到1965年, 庫利-圖基提出了針對N時復合數情況的快速離散傅立葉變換算法,與傳統(tǒng)算法相比降低了1個數量級,由此引發(fā)了研究快速算法的熱潮.這些算法統(tǒng)稱為FFT. FFT算法的廣泛應用，不僅奠定了離散傅立葉變換在數字信號處理中的經典地位,也極大推動了數字信號處理應用與發(fā)展.第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法衡量算法的復雜性: 乘.加法運算次數,不考慮控制調度等操作;只考慮DFT的正變換,因為:10( )( )NknNnX kx n W K=0,1, ,N-1 DFT正變換110011( )( )( )NNknknNNkkx nX k WXk WNNDFT反變換反變換相對正變換:

3、輸入取共扼;輸出取共軛并加權.直接計算直接計算DFT的運算量的運算量( )x n n=0,1, ,N-1 10()( )NknNnXkx n W k=0,N-1復數運算復數運算 對每一個對每一個k值值: 復乘復乘: N 復加: N-1第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法 對所有對所有k: 復乘復乘: 復加復加: N(N-1)即復數運算量與即復數運算量與 近似成正比近似成正比(不考慮 情況) 2N2N01NW 實數運算10( )Re( )Im( )ReImNknknNNnX kx njx nWjW1100Re( ) ReIm( ) ImNNknknNNnnx nWx nW1100Re

4、( ) ImIm( ) ReNNknknNNnnjx nWx nW k=0,N-1第一節(jié)第一節(jié) 改進改進DFT計計算的方法算的方法對每一個固定對每一個固定k : 實乘實乘: 4N 實加實加: 2(1) 1242NN對所有對所有k : 實乘實乘: 4N2實加實加: 2N(2N-1)= 4N2 -2N實數運算量與實數運算量與2N近似成正比近似成正比 結論結論:直接計算直接計算DFT的乘的乘.加運算量近似與加運算量近似與 成正比成正比.第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法2N改善運算效率的途徑改善運算效率的途徑（1）利用）利用 的對稱性和周期性等特性合并運算項的對稱性和周期性等特性合并運

5、算項復共軛對稱性復共軛對稱性: 對對n和和k的周期性的周期性: 可約性可約性 特殊值特殊值knNW()k N nknknNNNWWW()()knk n Nk N nNNNWWW第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法11/rNN rMWWW/20/2/4 1 1 kNkNNNNNNNWWWWWj NrM式中其它各對稱項也可以找到類似歸并辦法式中其它各對稱項也可以找到類似歸并辦法. .這樣乘法這樣乘法次數大約可減少一半次數大約可減少一半. .(2) (2) 大點數大點數DFTDFT逐次分解成小點數逐次分解成小點數DFT)DFT)分解分解 正是正是FFTFFT算法的基本原理算法的基本原理

6、Re( )Re()ReknNx nx NnWImIm( )Im()knNWx nx Nn 1222122NNNNNN第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法例:利用對稱性,可以合并對稱項:()Re( ) ReRe() ReReknk NnknNNNx nWx NnWW()Im( ) ImIm() Imknk N nNNx nWx NnWFFT的基本原理： 為了提高DFT的運算效率, 把大點數DFT按倒位序逐次分解為更小點數DFT的合成.在分解過程中,要利用系數 的對稱性和周期性. 如果算法是逐次分解時間序列得到的,那么這種分解算法稱為按時間抽取算法.闡述按時間抽取原理最方便的方法是研究

7、 這種特殊情況.由于N為2的整數冪,可以不斷將x(n)一分為二. 這就是最常用的基-2FFT算法. 如果序列不滿足這個條件,可以人為地加上若干零點得到.knNW2mN 第一節(jié)第一節(jié) 改進改進DFT計算的方法計算的方法第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法算法原理：假設序列x(n)長為 (n=0,N-1), 由于N為 偶數,可以將x(n)按n為奇數和偶數分解為兩個 N/2的長序列,并依此逐級分解來計算x(k).2mN 120,1,1(2 )( )2(21)( )0,1,12Nrxrx rxrx rNr是x(n)按n為奇、偶數分為2個子序列，得:第二節(jié)第二節(jié) 按時間抽取按時間抽取F

8、FTFFT算法算法第一級分解定義偶序列與奇序列:( )( )( )knknNNnnX kx n Wx n W為偶數為奇數11222(21)00(2 )(21)NNknkrNNrrxr WxrW1122221200( )( )NNkrkrkNNNrrx rWx rWW222221/2NjjNNNWeeW上式可寫為:第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 2211221200( )( )( )NNNNkrkrkNrrX kx rWx rWW12( )( )kNX kW Xk其中: 2211221100( )( )(2 )NNNNkrkrrrX kx rxrWW k=0,N/2-1

9、第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT算法算法上式表明一個N點的DFT可以分解成兩個 點的DFT. 這兩個 點的DFT又可按式合成一個N點DFT一個問題: 和 的長度為 , 它們的DFT 和 的點數也為 , 而x(k)卻有N個點。 利用 的周期性解決這一問題，即：/2N1( )x r2( )x r1( )X k2( )X kkNW/2/2k NNkkNNNNWWWW 第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法/2N/2N/2N/ 2/ 2/2 1/2 1/2111100(/2)( )( )( )NNNNkNrkrrrX kNx rWx rWX k22()( )2NXkXk表達為前

10、后兩個部分:( )X k前半部分 012( )( )( )kNXkX kW Xk后半部分 12(/2)( )( )kNX kNX kW Xk k=0, k=0, /2 1N1( )X k和2( )Xk的周期為/2N同樣可得把即：/2 1N第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法這樣只要求出0 -1 區(qū)間所有 和 ,就可以求出0N-1 區(qū)間內全部X(k)的值.這就是FFT運算的關鍵所在。用以下信號流圖表示為：1( )X k2( )Xk/2N根據流圖的形狀，上述運算稱為碟形運算。第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法復乘: 1 復加: 2一次蝶形運算: 運算分析:當3

11、28N 一次分解后DFT運算的信號流圖為：第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 仍為偶數,可以2N NNN2(1)22222 直接計算N點DFT所需復乘 ,復加N(N-1),可見當2N N較大時,一次分解后運算量減少近一半. 由于 N= 2M(M1), 經一次分解后 N2N2 點DFT再分別分解為兩個 點DFT的組合.進一步把每個N2復乘: 2NNN(N 1)21222 一次分解: 2個 N2點DFT+ 個蝶形運算N2 復加: 第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT算法算法第二級分解1( )x r1314(2 )( )0,14(21)( )xlx lNlxlx l可得: 2

12、2112(21)4411100( )(2 )(21)NNNNkrklllX kxlxlWW第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 與第一級分解一樣,利用 和 隱含的周期性, 為 改寫為前，后兩部分: 234( )( )NkXkXkW0,12Nk 其中: 414330( )( )NNkllXkx lW0,14Nk 414440( )( )NNkllXkx lW0,14Nk 3(k)X4(k)X1( )X k第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 2134( )( )( )NkX kXkW kW0,14Nk N2k134()(k)( )4NX kXXkW0,14Nk

13、 由此一個 N4點DFT分解成兩個 N2 點的DFT.其流圖為:第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法2( )Xk也可以進行同樣分解:2526(2 )( )0,14(21)( )xlx lNlxlx l第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法奇序列中的偶序列,奇序列中的奇序列 22112(21)4422200( )(2 )(21)NNNNkrklllXkxlxlWW 42411445600( )( )NNNNNkrkklllx lx lWWW 256( )( )NkXkXkW0,12Nk 第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法414550( )(

14、)NNkllXkx l W0,14Nk 414660( )( )NNkllXkx l W0,14Nk 為 2( )Xk改寫為前,后兩部分: N2256( )(k)(k)kXkXWX0,14Nk 2256()( )( )4NkNXkXkWXk0,14Nk 第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法其中:系數統(tǒng)一為 (今后都使用統(tǒng)一的系數),這樣,N22kkNWW一個N點DFT就分解成4個N/4點的DFT,其信號流圖為:第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法根據前面的分析,第二級分解組合比第一級分解后的運算量又降低了一半.對于N=8點的DFT,經過兩次分解后,最后剩下四

15、個N/4=2 的DFT,即 3456( )( ),( )( )Xk XkXkXk和(k =0,1).盡管2點長的DFT只有加減法,仍然可用蝶式運算單元來統(tǒng)一表示.第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法例如 組成的2點DFT 可用公式計算: 類似,其它3個2點長DFT都可以用一個蝶式運算單元求得,綜合這三級分解過程,可得到一個完整的8點DFT信號流圖.4( )Xk410444(0)(0)(1)(2)(6)(2)(6)NNXxW xxxxW x410444(1)(0)(1)(2)(6)(2)(6)NNXxW xxxxW x(2), (6)xx第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT

16、FFT算法算法第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法這種方法每次分解都是按輸入序列在時域上的次序是偶數還是奇數來抽取的，故稱之為按時間抽取法.運算量分析由DIT FFT信號流圖可見,對于任何一個 點DFT運算,都可以通過M次分解,最后分解成2點DFT運算的組合.這樣的M級分解,就構成了M級運算過程.每級N/2個蝶形運算.每一級: 復乘: 復加: 2MN 122NN 22NN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法結論: DIF FFT運算量與 近似成正比.全部M級:復乘 復加 2NNlog22pmMN2logpaNMNN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFF

17、T算法算法2logNN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法三. 按時間抽取的FFT算法特點.1. 蝶式運算 系統(tǒng)由大量蝶式運算單元組成,每個蝶式運算的迭代任務是:11( )( )( )rmmNmXpXpW Xq11( )( )( )rmmNmXqXpW Xq1mM 為節(jié)點，m：表示第m列疊代。p,q：為數據所在行數，對應信號流圖下圖所示：01pqN( )( )mmXp Xq第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT算法算法00( ),( )XpXq是輸入數據注：第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法（1）蝶式運算的節(jié)點距離 (p,q間的距離)以N=8為例m 1

18、2 3q-p 1 2 4推廣:基-2 DIF FFT中,第m級蝶式運算節(jié)點間距離為12m蝶式運算可寫成:111( )( )(2)rmmmNmXpXpW XprNW（2） 的確定每一級的旋轉因子都不相同，但排列很有規(guī)律，下表所示。第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法rNW2. 原址運算第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 多級蝶式運算結構會產生大量中間結果.如果運算式要保存這些中間結果,則需要耗費大量資源(存貯器)觀察FFT信號流圖,可以發(fā)現(xiàn)任何兩個節(jié)點(p與q)經過蝶式運算后,其結果即為下一列p,q兩節(jié)點的變量.而每一級蝶式運算的輸出,在該級運算結束之后無需

19、保存.因此,任何一個蝶行運算的兩個輸出結果仍然可以存放兩個輸入值所在的存儲單元中.這樣,整個運算只需要N個寄存器,他們保存輸入數據,并不斷對每一級運算結果刷新,直到最后輸出。其優(yōu)點在于節(jié)省存儲資源.第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT算法算法3. 倒位序 觀察同址運算結構,可以發(fā)現(xiàn)FFT輸出端X(k)正好按07自然順序排列的，而輸出序列x(n)不是按07自然順序排列。x(n)排列表面上混亂無序，而隱含著有規(guī)律的排列，即”倒位序”存貯,以N=8點FFT結構來說明。存儲器號 數據22222222222222220(000)(000)(0)1(001)(100)(4)2(010)(010)(2)

20、3(011)(110)(6)4(100)(001)(1)5(101)(101)(5)6(110)(011)(3)7(111)(111)(7)xxxxxxxxxxxxxxxx結論: 21020122()()n n nx n n n第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法倒位序排列是由于不斷將DFT運算分解為較小點數DFT計算造成的。序列x(n)首先分成偶數標號和奇數標號兩個子序列：偶數序列出現(xiàn)在流圖上半部,奇數序列出現(xiàn)在流圖下半部。從形式上說,這樣的劃分可通過分析標號n的二進制表示 的最低位 來實現(xiàn)。標號為偶數，則 =0，標號為奇數，則 =1。這樣 =0的標號出現(xiàn)在流圖上半部2 1

21、020 122x( )()()nx n n nn n n 存儲2 1 0 2()n nn0n從中我們可以發(fā)現(xiàn): 若 2 102()nn nn, 則: 0n0n0n第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 =1的標號出現(xiàn)在下半部。下一次奇偶序列的分解又分別根據標號二進制表示的倒數第二位 開始,根據 分別將第一次分解生成的兩個子序列再一次按奇偶性分開。持續(xù)該過程,直得到N個長度為1的子序列。最后的排列順序呈”倒位序”0n1n1n第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法所以要實現(xiàn)FFT算法，首先必須把按自然順序存放的數據變換成按倒序存放。這一過程稱為整序，N=8時的整序過

22、程下圖所示。第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法小結:1. 算法原理2. 計算量: 復乘:復加:3. 運算特點:蝶式運算.同址運算.倒位序2log2NN2logNN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法第三節(jié)第三節(jié) 按頻率抽取按頻率抽取FFTFFT算法算法DIT:將輸入序列x(n)按其標號n為奇數或偶數分解成短序列DIF:將輸出序列X(k)按其k值為奇數或偶數分解成短序列算法原理仍討論基-2FFT,即 頻域抽取法是將X(k)按標號k的自然順序分成前后兩半(注意:不再是奇偶順序)2MN 1/2 1100/2( )( )( )( )NNNknknknNNNnnn

23、NX kx n Wx n Wx n W/2 1/2 1(/2)00( )(/2)NNknk n NNNnnx n Wx nNW/2 1/20/2 10( )(/2)( )( 1)(/2)NkNknNNnNkknNnx nWx nNWx nx nNW 第三節(jié)第三節(jié) 按頻率抽取按頻率抽取FFTFFT算法算法/2 120( )(2 )( )(/2)NrnNnX kXrx nx nNW/2 1/20( )(/2)NrnNnx nx nNW/2 1(21)0( )(21)( )(/2)NrnNnX kXrx nx nNW按k為偶數或是奇數將x(k)分解成兩部分2 ,0,1,.,/2 1kr rN21,0,1,.,/2 1krrN/2 1/20( )(/2)NnrnNNnx nx nNWW第三節(jié)第三節(jié) 按頻率抽取按頻率抽取FFTFFT算法算法輸入序列前一半與后一半之差再與 乘積nNW1( )( )()2Nx nx nx n2( )( )()2nNNx nx nx nW令輸入序列前一半與后一半之和0,12Nn 0,12Nn 第三節(jié)第三節(jié) 按頻率抽取按頻率抽取FFTFFT算法算法1210212202(2 )( )0,1 2(21)( )NrnNnNnrNnXr