信號分析及處理15

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

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

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

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

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

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

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

8、FTFFT算法算法第一級分解定義偶序列與奇序列:( )( )( )knknNNnnX kx n Wx n W為偶數(shù)為奇數(shù)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點(diǎn)的DFT可以分解成兩個 點(diǎn)的DFT. 這兩個 點(diǎn)的DFT又可按式合成一個N點(diǎn)DFT一個問題: 和 的長度為 , 它們的DFT 和 的點(diǎn)數(shù)也為 , 而x(k)卻有N個點(diǎ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表達(dá)為前

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ū)間內(nèi)全部X(k)的值.這就是FFT運(yùn)算的關(guān)鍵所在。用以下信號流圖表示為：1( )X k2( )Xk/2N根據(jù)流圖的形狀，上述運(yùn)算稱為碟形運(yùn)算。第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法復(fù)乘: 1 復(fù)加: 2一次蝶形運(yùn)算: 運(yùn)算分析:當(dāng)3

11、28N 一次分解后DFT運(yùn)算的信號流圖為：第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法 仍為偶數(shù),可以2N NNN2(1)22222 直接計算N點(diǎn)DFT所需復(fù)乘 ,復(fù)加N(N-1),可見當(dāng)2N N較大時,一次分解后運(yùn)算量減少近一半. 由于 N= 2M(M1), 經(jīng)一次分解后 N2N2 點(diǎn)DFT再分別分解為兩個 點(diǎn)DFT的組合.進(jìn)一步把每個N2復(fù)乘: 2NNN(N 1)21222 一次分解: 2個 N2點(diǎn)DFT+ 個蝶形運(yùn)算N2 復(fù)加: 第二節(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點(diǎn)DFT分解成兩個 N2 點(diǎn)的DFT.其流圖為:第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法2( )Xk也可以進(jìn)行同樣分解: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算法算法其中:系數(shù)統(tǒng)一為 (今后都使用統(tǒng)一的系數(shù)),這樣,N22kkNWW一個N點(diǎn)DFT就分解成4個N/4點(diǎn)的DFT,其信號流圖為:第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法根據(jù)前面的分析,第二級分解組合比第一級分解后的運(yùn)算量又降低了一半.對于N=8點(diǎn)的DFT,經(jīng)過兩次分解后,最后剩下四

15、個N/4=2 的DFT,即 3456( )( ),( )( )Xk XkXkXk和(k =0,1).盡管2點(diǎn)長的DFT只有加減法,仍然可用蝶式運(yùn)算單元來統(tǒng)一表示.第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法例如 組成的2點(diǎn)DFT 可用公式計算: 類似,其它3個2點(diǎn)長DFT都可以用一個蝶式運(yùn)算單元求得,綜合這三級分解過程,可得到一個完整的8點(diǎn)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算法算法這種方法每次分解都是按輸入序列在時域上的次序是偶數(shù)還是奇數(shù)來抽取的，故稱之為按時間抽取法.運(yùn)算量分析由DIT FFT信號流圖可見,對于任何一個 點(diǎn)DFT運(yùn)算,都可以通過M次分解,最后分解成2點(diǎn)DFT運(yùn)算的組合.這樣的M級分解,就構(gòu)成了M級運(yùn)算過程.每級N/2個蝶形運(yùn)算.每一級: 復(fù)乘: 復(fù)加: 2MN 122NN 22NN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法結(jié)論: DIF FFT運(yùn)算量與 近似成正比.全部M級:復(fù)乘 復(fù)加 2NNlog22pmMN2logpaNMNN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFF

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

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

19、保存.因此,任何一個蝶行運(yùn)算的兩個輸出結(jié)果仍然可以存放兩個輸入值所在的存儲單元中.這樣,整個運(yùn)算只需要N個寄存器,他們保存輸入數(shù)據(jù),并不斷對每一級運(yùn)算結(jié)果刷新,直到最后輸出。其優(yōu)點(diǎn)在于節(jié)省存儲資源.第二節(jié)第二節(jié) 按時間抽取按時間抽取FFT算法算法3. 倒位序 觀察同址運(yùn)算結(jié)構(gòu),可以發(fā)現(xiàn)FFT輸出端X(k)正好按07自然順序排列的，而輸出序列x(n)不是按07自然順序排列。x(n)排列表面上混亂無序，而隱含著有規(guī)律的排列，即”倒位序”存貯,以N=8點(diǎn)FFT結(jié)構(gòu)來說明。存儲器號 數(shù)據(jù)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結(jié)論: 21020122()()n n nx n n n第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法倒位序排列是由于不斷將DFT運(yùn)算分解為較小點(diǎn)數(shù)DFT計算造成的。序列x(n)首先分成偶數(shù)標(biāo)號和奇數(shù)標(biāo)號兩個子序列：偶數(shù)序列出現(xiàn)在流圖上半部,奇數(shù)序列出現(xiàn)在流圖下半部。從形式上說,這樣的劃分可通過分析標(biāo)號n的二進(jìn)制表示 的最低位 來實(shí)現(xiàn)。標(biāo)號為偶數(shù)，則 =0，標(biāo)號為奇數(shù)，則 =1。這樣 =0的標(biāo)號出現(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的標(biāo)號出現(xiàn)在下半部。下一次奇偶序列的分解又分別根據(jù)標(biāo)號二進(jìn)制表示的倒數(shù)第二位 開始,根據(jù) 分別將第一次分解生成的兩個子序列再一次按奇偶性分開。持續(xù)該過程,直得到N個長度為1的子序列。最后的排列順序呈”倒位序”0n1n1n第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法所以要實(shí)現(xiàn)FFT算法，首先必須把按自然順序存放的數(shù)據(jù)變換成按倒序存放。這一過程稱為整序，N=8時的整序過

22、程下圖所示。第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法小結(jié):1. 算法原理2. 計算量: 復(fù)乘:復(fù)加:3. 運(yùn)算特點(diǎn):蝶式運(yùn)算.同址運(yùn)算.倒位序2log2NN2logNN第二節(jié)第二節(jié) 按時間抽取按時間抽取FFTFFT算法算法第三節(jié)第三節(jié) 按頻率抽取按頻率抽取FFTFFT算法算法DIT:將輸入序列x(n)按其標(biāo)號n為奇數(shù)或偶數(shù)分解成短序列DIF:將輸出序列X(k)按其k值為奇數(shù)或偶數(shù)分解成短序列算法原理仍討論基-2FFT,即 頻域抽取法是將X(k)按標(biāo)號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為偶數(shù)或是奇數(shù)將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