數(shù)字信號處理2課件

1、4.3 基2頻率抽取 FFT算法 1、將N點DFT分解為兩個N/2點DFT序列基礎(chǔ)上。4.3 .1 基2頻率抽取 FFT算法礎(chǔ)上；頻選法FFT建立在把X(k)分解成越來越短的子做法：將x(n)分成前后兩段時選FFT建立在把將x(n)分解成越來越短的子序列基N = 2M對第二項令n=n-N/2n=n+N/2n:0(N/2)-1n : N/2N-1則令N/2點DFT(X(k)的偶次項)N/2點DFT(X(k)的奇次項)即有：(4.3-3)上式的運算關(guān)系可以用蝶形表示運算量：一次復(fù)乘；兩次復(fù)加。n=0,1,2, (N/2)-1 同樣是利用兩個N/2點DFT，合成一個N點DFT。 均為N/2點DFT合

2、成N點(4.3-4)即例 N=8復(fù)乘計算量：2、繼續(xù)將N/2點DFT分解為兩個N/4點DFT。 對第二項令n=n-N/4n=n+N/4n:0(N/4)-1n : N/4(N/2)-1令l=0,1,2, (N/4)-1則：N/4點DFT(X1(k)的偶次項)l=0,1,2, (N/4)-1N/4點DFT(X1(k)的奇次項)l=0,1,2, (N/4)-1如法炮制，直至最后分解到2點DFT為止。(3)合成N/2點X1(r)即有：同理， X2(r)與X1(r)一樣，可再分解為兩個N/4點DFT ，即有X5(r)、X6(r) 。-1-1-1-1-1-1-1-1-1-1-1-1L級L-1級第L級蝶形運

3、算如圖4.3-5所示。由圖4.3-5可以看到頻選FFT運算規(guī)律有以下幾點二、運算規(guī)律計算量：復(fù)乘 mF=M(N/2)=(N/2)log2NXL-1(p)XL(p)XL-1(q)XL(q)1、同址計算計算。因為每個節(jié)點與前列的節(jié)點平行對應(yīng)，所以是同址2、變址輸出后，要經(jīng)過變址運算再輸出以保證輸出的正確。輸入是自然順序，輸出是碼位倒序的，所以計算完以3、與時選蝶形轉(zhuǎn)置頻選的蝶形與時選蝶形互為轉(zhuǎn)置關(guān)系，所以總的時選法與頻選法互為轉(zhuǎn)置關(guān)系。例圖4.2-6轉(zhuǎn)置圖4.3-4。時選蝶形頻選蝶形L級L-1級XL-1(p)XL(p)XL-1(q)XL(q)L級L-1級XL-1(p)XL(p)XL-1(q)XL(

4、q)其它形式的頻選FFTFFT。由其它形式的時選FFT轉(zhuǎn)置可以得到其它形式的頻選由圖4.2-12的轉(zhuǎn)置形式得到如圖4.3-7所示另一種形式的頻選流圖。由此可見，兩者計算量相同mF=M(N/2)=(N/2)log2N圖4.3-74.4、 IDFT的快速計算方法IFFT4.4.1、的快速計算方法IFFTIDFT的快速計算方法即快速傅里葉反變換，一般可用英文縮寫為IFFT。上面所討論的無論時選還是頻選FFT算法均可用于IDFT運算，因為DFT與IDFT運算公式分別為及運算量進一步減少的方法X (k)=DFTx(n)比較兩式可見，只要將，再將結(jié)果乘以1/N 就可以用DFT程序計算IDFT。x(n) =

5、IDFTX(k)但因為輸入是頻域序列X (k ) ，輸出為時域序列 x(n) ，1)時選的FFT頻選的IFFT；頻選的FFT 時選的IFFT。2)為減少有限字長影響，一般 1/N = (1/2)M 可分到M級的運算中去。其基本蝶形為所以時選IFFT蝶形頻選IFFT蝶形1/21/2L級XL(p)XL(q)L級XL(p)XL(q)L-1級XL-1(p)XL-1(q)L-1級XL-1(p)XL-1(q)流圖的FFT、IFFT計算均為同址的。4.3-7，所以其反變換也對應(yīng)這幾個常用的流圖。這幾個每個蝶形的運算量：兩次復(fù)乘；兩次復(fù)加?？偟挠嬎懔浚阂驗樽畛Ｓ玫腇FT算法的流圖是4.2-6、4.2-12、

6、4.3-4、共有M級，每級N/2個蝶形。mF=M(N/2)2=MN=Nlog2NaF=M(N/2)2=MN=Nlog2N所以， 可以IFFT與FFT子程共用。如果希望FFT與IFFT子程序共用，還可以選擇下面的方法。因為又因為 對結(jié)果再取共軛； 訪問FFT子程序； 乘以1/N。 對X(k)取共軛得X*(k) ；步驟思路：適當選擇FFT與IFFT算法，有可能避免倒序位的算法。處理過的數(shù)據(jù)。這時DFT與IDFT相當是兩個變換的級聯(lián)。乘以系統(tǒng)的DFT（H(k)），然后再作乘積的IDFT，得到如果只對數(shù)據(jù)作一次變換，顯然在同址計算情況下，要在輸入或輸出作變址運算。但在許多實際應(yīng)用中，是將數(shù)據(jù)的DFT經(jīng)

7、系統(tǒng)處理后再作IDFT得到處理后的數(shù)據(jù)。例如，用DFT實現(xiàn)FIR DF時，對輸入的一段數(shù)據(jù)作DFT，例如，對DFT我們選圖4.2-12的時選法， （是輸入為自然對IDFT我們選圖4.4-3的IFFT頻選法， （是輸入為倒都不需做倒序運算，運算框圖如圖4.4-4所示。序位的，輸出位自然順序的）。這樣，正、反兩次變換序位、輸出倒序位的）。將系統(tǒng)的H(k)也按倒序位存儲；出順序IDFT入順序出倒序DFT入倒序倒序存FIR DF 圖4.2-12(時選FFT)圖4.4-3(頻選IFFT)圖4.4-4選；反之，F(xiàn)FT為頻選，IFFT必為時選。注意：系統(tǒng)序位要一致的話，F(xiàn)FT為時選，IFFT必為頻4.4.2

8、、運算量進一步減少的方法前面討論的時選FFT與頻選FFT算法，算法簡單，編程效率高，得到廣泛應(yīng)用。由前面討論的FFT算法可知，N = 2M 點FFT的復(fù)數(shù)乘法次數(shù)為NM/2 。實際運算量是否還能再減少？回答是肯定的。下面介紹以程序的復(fù)雜換取運算量減少的方法。1、無需運算的因子旋轉(zhuǎn)因子，如、等。 在DFT運算中，若，則稱其為無關(guān)緊要的級蝶形、。由圖4.2-6可以看到在第一級蝶形中，只有一種旋轉(zhuǎn)因子因為與這些因子相乘時不用作實際的復(fù)數(shù)乘法。以時選FFT流圖為例，從左到右依次為第一級蝶形、第二，因此不需要復(fù)數(shù)乘法運算；第二級蝶形有兩個無關(guān)緊要的旋轉(zhuǎn)因子 、兩級不需要復(fù)數(shù)乘法的運算外，所需實際復(fù)數(shù)乘法

9、數(shù)為 (4.4-3) 所以也不需要復(fù)數(shù)乘法運算。去除一、二在第三級蝶形有兩個無關(guān)緊要的旋轉(zhuǎn)因子與也不需要復(fù)數(shù)乘法運算。 以此類推，L3時，第L級的兩個無關(guān)緊要的旋轉(zhuǎn)因子與減少復(fù)數(shù)乘法的次數(shù)為2N / 2L = N/2L-1 。蝶形運算，所以第三級共有2N / 23 = N/4個蝶形。因為同一旋轉(zhuǎn)因子對應(yīng)著2M-L = N/2L個從 L=3 到 L = M共減少復(fù)數(shù)乘法的次數(shù)為考慮以上這些減少的復(fù)數(shù)乘法后，這時的復(fù)數(shù)乘法運算次數(shù)為實現(xiàn)一次復(fù)數(shù)乘法，一般需要四次實數(shù)乘法，兩次實2、減少運算的因子數(shù)加法。但當任意復(fù)數(shù) a+jb 與相乘時，有 式中，實數(shù)加法和兩次實數(shù)乘法。 由式(4.4-6) 可見，

10、任意復(fù)數(shù)與 相乘只需要兩次這樣，所有含有的蝶形，減少兩次實數(shù)乘法。從 L=3 到 L = M級，每級都包含，第 L 級中，最后一級，減少的實數(shù)乘法次數(shù)與 (4.4-4)式對應(yīng)2M-L = N/2L個蝶形運算，所以從第三級到相同為 (N/2) - 2次。 3、改進后的實數(shù)乘法計算量考慮所有相關(guān)的旋轉(zhuǎn)因子，從實數(shù)運算考慮，計算N = 2M點FFT的實數(shù)乘法次數(shù)為在基2FFT程序中，含有全部旋轉(zhuǎn)因子的，該算法為一類蝶形單元運算；去掉了 旋轉(zhuǎn)因子的，為二類蝶形單元運算；去掉了 、旋轉(zhuǎn)因子的，為三類蝶形單元運算；去掉了 、的旋轉(zhuǎn)因子，又對 作了處理的，為四類蝶形單元運算。 類型越多，編程越復(fù)雜。當N較大時，乘法運算的減少乘法次數(shù)是一類蝶形單元運算的75%。量是相當可觀的。例N=4096時，三類蝶形單元運算的后三種運算也稱為多類蝶形單元運算。顯然