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

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

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

3、算如圖4.3-5所示。由圖4.3-5可以看到頻選FFT運(yùn)算規(guī)律有以下幾點(diǎn)二、運(yùn)算規(guī)律計(jì)算量：復(fù)乘 mF=M(N/2)=(N/2)log2NXL-1(p)XL(p)XL-1(q)XL(q)1、同址計(jì)算計(jì)算。因?yàn)槊總€(gè)節(jié)點(diǎn)與前列的節(jié)點(diǎn)平行對應(yīng)，所以是同址2、變址輸出后，要經(jīng)過變址運(yùn)算再輸出以保證輸出的正確。輸入是自然順序，輸出是碼位倒序的，所以計(jì)算完以3、與時(shí)選蝶形轉(zhuǎn)置頻選的蝶形與時(shí)選蝶形互為轉(zhuǎn)置關(guān)系，所以總的時(shí)選法與頻選法互為轉(zhuǎn)置關(guān)系。例圖4.2-6轉(zhuǎn)置圖4.3-4。時(shí)選蝶形頻選蝶形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。由其它形式的時(shí)選FFT轉(zhuǎn)置可以得到其它形式的頻選由圖4.2-12的轉(zhuǎn)置形式得到如圖4.3-7所示另一種形式的頻選流圖。由此可見，兩者計(jì)算量相同mF=M(N/2)=(N/2)log2N圖4.3-74.4、 IDFT的快速計(jì)算方法IFFT4.4.1、的快速計(jì)算方法IFFTIDFT的快速計(jì)算方法即快速傅里葉反變換，一般可用英文縮寫為IFFT。上面所討論的無論時(shí)選還是頻選FFT算法均可用于IDFT運(yùn)算，因?yàn)镈FT與IDFT運(yùn)算公式分別為及運(yùn)算量進(jìn)一步減少的方法X (k)=DFTx(n)比較兩式可見，只要將，再將結(jié)果乘以1/N 就可以用DFT程序計(jì)算IDFT。x(n) =

5、IDFTX(k)但因?yàn)檩斎胧穷l域序列X (k ) ，輸出為時(shí)域序列 x(n) ，1)時(shí)選的FFT頻選的IFFT；頻選的FFT 時(shí)選的IFFT。2)為減少有限字長影響，一般 1/N = (1/2)M 可分到M級的運(yùn)算中去。其基本蝶形為所以時(shí)選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計(jì)算均為同址的。4.3-7，所以其反變換也對應(yīng)這幾個(gè)常用的流圖。這幾個(gè)每個(gè)蝶形的運(yùn)算量：兩次復(fù)乘；兩次復(fù)加?？偟挠?jì)算量：因?yàn)樽畛Ｓ玫腇FT算法的流圖是4.2-6、4.2-12、

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

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

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

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

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