數(shù)字信號(hào)處理教程dsp-ch4-1

1、第四章學(xué)習(xí)目標(biāo)第四章學(xué)習(xí)目標(biāo) 理解按時(shí)間抽選的基理解按時(shí)間抽選的基-2FFT算法的算法原算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn) 理解按頻率抽選的基理解按頻率抽選的基-2FFT算法的算法原算法的算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn) 理解線性卷積的理解線性卷積的FFT算法及分段卷積方法算法及分段卷積方法4.1 引言 FFT: Fast Fourier Transform 1965年，Cooley-Turky 發(fā)表文章機(jī)器計(jì)算傅里葉級(jí)數(shù)的一種算法，提出FFT算法，解決DFT運(yùn)算量太大，在實(shí)際使用中受限制的問題。 FFT的

2、應(yīng)用。頻譜分析、濾波器實(shí)現(xiàn)、實(shí)時(shí)信號(hào)處理等。 DSP芯片實(shí)現(xiàn)。TI公司的TMS 320c30，10MHz時(shí)鐘，基2-FFT1024點(diǎn)FFT時(shí)間15ms。 典型應(yīng)用：信號(hào)頻譜計(jì)算、系統(tǒng)分析等)()(kXnxDFT )()()(nynhnxFFTnhnyIFFTFFTnx)()()( 系統(tǒng)分析系統(tǒng)分析 頻譜分析與功率譜計(jì)算頻譜分析與功率譜計(jì)算4.2 直接計(jì)算DFT的問題及改進(jìn)途徑10)()(NnknNWnxkX10)(1)(NkknNWkXNnx1、 DFT與與IDFT( )Nx n點(diǎn)有限長(zhǎng)序列2、DFT與與IDFT運(yùn)算特點(diǎn)運(yùn)算特點(diǎn)復(fù)數(shù)乘法復(fù)數(shù)加法一個(gè)X(k)NN 1N個(gè)X(k)(N點(diǎn)DFT)N

3、2N (N 1)10( )NnkNnx n Wajbcjdacbdj adcb同理：同理：IDFT運(yùn)算量與運(yùn)算量與DFT相同。相同。實(shí)數(shù)乘法實(shí)數(shù)加法一次復(fù)乘42一次復(fù)加2一個(gè)X (k)4N2N+2 (N 1)=2 (2N 1)N個(gè)X (k)(N點(diǎn)DFT)4N 22N (2N 1)3、降低DFT運(yùn)算量的考慮nkNW 的特性*()() ()nknkN n kn N kNNNNWWWW對(duì)稱性()() nkN n kn N kNNNWWW周期性 nkmnkNmNWW可約性/nknk mNN mWW0/2(/2) 11NkNkNNNNWWWW 特殊點(diǎn)：2jnknkNNWeNknkNNWWnNnkNNWW

4、2jmnkmNe221NjjNee FFT算法分類算法分類:q 時(shí)間抽選法時(shí)間抽選法DIT: Decimation-In-Timeq 頻率抽選法頻率抽選法DIF: Decimation-In-FrequencyFFTDFTDFTDFTDFT算法的基本思想： 利用系數(shù)的特性，合并運(yùn)算中的某些項(xiàng)， 把長(zhǎng)序列短序列，從而減少其運(yùn)算量。1、算法原理、算法原理設(shè)序列點(diǎn)數(shù)設(shè)序列點(diǎn)數(shù) N = 2L，L 為整數(shù)。為整數(shù)。 若不滿足，則補(bǔ)零若不滿足，則補(bǔ)零 12221xrx rxrxr0,1,.,/2 1rN將序列將序列x(n)按按n的奇偶分成兩組：的奇偶分成兩組：N為為2的整數(shù)冪的的整數(shù)冪的FFT算法稱基算法

5、稱基-2FFT算法。算法。4.3 按時(shí)間抽?。―IT）的FFT算法則則x(n)的的DFT: 111000NNNnknknkNNNnnnX kx n Wx n Wx n Wn為偶數(shù)n為奇數(shù)/2 1/2 121200221NNrkrkNNrrxr WxrW /2 1/2 1221200NNrkrkkNNNrrx rWWxrW )(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx /2 1/2 1221200NNrkrkkNNNrrx rWWxrW )(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx)()()(21

6、kXWkXkXkN記：記： （1 1）rkNrkNWW2/2（這一步利用：（這一步利用： ）,0,1,./2 1r kN再利用周期性求再利用周期性求X(k)的后半部分的后半部分/22NkNkkNNNNWWWW 又)(2)()()(222112/02/112/0)2/(2/11kXkNXkXWrxWrxkNXNrrkNNrkNrNrkNkNrNWW2/)2/(2/)2()2()2()2(12/,.2 , 1 , 0)()()(2)2/(121kNXWkNXkNXNkkXWkXkXkNNkN，12/,.2 , 1 , 0)()(21NkkXWkXkN，將上式表達(dá)的運(yùn)算用一個(gè)專用“蝶形”信流圖表示。

7、注：注：a. 上支路為加法，下支路為減法；上支路為加法，下支路為減法； b. 乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。乘法運(yùn)算的支路標(biāo)箭頭和系數(shù)。1212( )( )( )()( )( )2kNkNX kX kW XkNX kX kW Xk0,1,.,/2 1kN用“蝶形結(jié)”表示上面運(yùn)算的分解： 328N)0(x)1 (x)2(x)3(x)4(x)5(x)6(x)7(x)0(X) 1 (X)2(X)3(X)4(X)5(X)6(X)7(X1NW0NW2NW3NW)0(1X)1 (1X)2(1X)3(1X)0(2X)1 (2X(3)2X)2(2XDFTN點(diǎn)2DFTN點(diǎn)2-分解后的運(yùn)算量：分解后的運(yùn)算量：復(fù)數(shù)乘

8、法復(fù)數(shù)乘法復(fù)數(shù)加法復(fù)數(shù)加法一個(gè)一個(gè)N / 2點(diǎn)點(diǎn)DFT(N / 2)2N / 2 (N / 2 1)兩個(gè)兩個(gè)N / 2點(diǎn)點(diǎn)DFTN 2 / 2N (N / 2 1)一個(gè)蝶形一個(gè)蝶形12N / 2個(gè)蝶形個(gè)蝶形N / 2N總計(jì)總計(jì)22/2/2/2NNN2/2 1/2N NNN運(yùn)算量減少了近一半運(yùn)算量減少了近一半進(jìn)一步分解進(jìn)一步分解1314(2 )( )(21)( )xlx lxlx l0,1,.,/4 1lN13/2413/24( )( )( )()( )( )4kNkNX kXkWXkNX kXkWXk0,1,.,14Nk LN2122LN2N4N由于由于 ， 仍為偶數(shù)，因此，兩個(gè)仍為偶數(shù)，因此

9、，兩個(gè) 點(diǎn)點(diǎn)DFTDFT又可同樣進(jìn)一步分解為又可同樣進(jìn)一步分解為4 4個(gè)個(gè) 點(diǎn)的點(diǎn)的DFTDFT。02/NW12/NW)(3lx)(4lx)2(x)4(x)6(x)0(x)0(1X) 1 (1X)2(1X) 3(1X) 0(3X) 1 (3X)0(4X) 1 (4XDFTN點(diǎn)4DFTN點(diǎn)4“蝶形蝶形”信流圖表示信流圖表示 N點(diǎn)DFT分解為四個(gè)N/4點(diǎn)的DFTDFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)4DFTN點(diǎn)4)2(x)4( x)6( x)0( x) 1 ( x) 3 ( x)5(x)7( x0NW2NW0NW2NW1NW0NW2NW3NW)0(X) 1 (X) 2(X) 3(X) 4(X) 5(X

10、)6(X)7(X)(.kX)(.nx25/2625/26( )( )( )()( )( )4kNkNXkXkWXkNXkXkWXk0,1,.,14Nk 同理：其中：552( )( )(2 )XkDFT x lDFT xl662( )( )(21)X kDFT x lDFT xl0,1,.,/4 1lN2/2kkNNWW統(tǒng)一系數(shù)：這樣逐級(jí)分解，直到這樣逐級(jí)分解，直到2點(diǎn)點(diǎn)DFT當(dāng)當(dāng)N = 8時(shí)，即分解到時(shí)，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k = 0, 11點(diǎn)點(diǎn)DFTx(0)1點(diǎn)點(diǎn)DFTx(4)X3(0)X3(1)02W0003322301033223(0)(0)(1)(0

11、)(4)(1)(0)(1)(0)(4)NNXxWW xxW xXxWW xxW x/4 1133/43/400( )( )( )NlklkNNllXkx l Wx l W0,1k 0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x/4 1144/44/400( )( )( )NlklkNNllXkx l Wx l W0,1k 0004422401044224(0)(0)(1)(2)(6)(1)(0)(1)(2)(6)NNXxWW xxW xXxWW xxW x0NWX3(0)X3(1)x(0)x(4)2(x)

12、4(x)6(x)0(x) 1 ( x) 3 ( x)5(x)7(x0NW0NW0NW0NW第一級(jí).0NW2NW0NW2NW 第二級(jí).)(0kX1m)(1kX)(2kX)(3kX2m3m1NW0NW2NW3NW)0(X) 1 (X)2(X)3(X)4(X)5(X)6(X)7(X 第三級(jí). (0) (4) (2) (6) (1) (5) (3) (7)WN0WN0WN0W0N-1-1-1-1X (0)X (1)X (0)X (1)X (0)X (1)X (0)X (1)33445566WN0WN2WN0WN2-1-1-1-1X (0)X (1)X (2)X (3)X (0)X (1)X (2)X

13、(3)11121222WWWWN0N1N2N3-1-1-1-1X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)xxxxxxxx因此,8點(diǎn)DFT的FFT的運(yùn)算流圖如下2、運(yùn)算量、運(yùn)算量當(dāng)當(dāng)N = 2L時(shí)，共有時(shí)，共有L級(jí)蝶形，每級(jí)級(jí)蝶形，每級(jí)N / 2個(gè)蝶形，個(gè)蝶形，每個(gè)蝶形有每個(gè)蝶形有1次復(fù)數(shù)乘法次復(fù)數(shù)乘法2次復(fù)數(shù)加法。次復(fù)數(shù)加法。2log22FNNmLN復(fù)數(shù)乘法：復(fù)數(shù)乘法：2logFaNLNN復(fù)數(shù)加法：復(fù)數(shù)加法：222()2()loglog2FFmDFTNNNmFFTNN比較比較DFT 參考參考P150 表表4-1 圖圖4-6 DIT-FFT的運(yùn)算過程很有規(guī)律，共進(jìn)行的運(yùn)算過

14、程很有規(guī)律，共進(jìn)行L級(jí)運(yùn)算，級(jí)運(yùn)算，每級(jí)由每級(jí)由N/2個(gè)蝶形運(yùn)算組成。同一級(jí)中，每個(gè)蝶個(gè)蝶形運(yùn)算組成。同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，與其它形的兩個(gè)輸入數(shù)據(jù)只對(duì)計(jì)算本蝶形有用，與其它蝶形運(yùn)算無關(guān)。蝶形運(yùn)算無關(guān)。 這樣這樣,蝶形運(yùn)算的兩個(gè)輸出值仍蝶形運(yùn)算的兩個(gè)輸出值仍可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中可放回蝶形運(yùn)算的兩個(gè)輸入所在的存儲(chǔ)器中,這這種利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出的種利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出的方法即為原位運(yùn)算。每一級(jí)方法即為原位運(yùn)算。每一級(jí)(列列)有有N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算,所以只需所以只需N個(gè)存儲(chǔ)單元，可以節(jié)省存儲(chǔ)單元。個(gè)存儲(chǔ)單元，

15、可以節(jié)省存儲(chǔ)單元。3、算法特點(diǎn)、算法特點(diǎn)1）原位計(jì)算）原位計(jì)算1）原位計(jì)算）原位計(jì)算1111( )( )( )( )( )( )rmmmNrmmmNXkXkXj WXjXkXj Wm表示第表示第m級(jí)迭代，級(jí)迭代，k，j表示數(shù)據(jù)所在的行數(shù)表示數(shù)據(jù)所在的行數(shù)2）序列的倒序）序列的倒序 由由DIT-FFT的規(guī)律可知的規(guī)律可知,輸出輸出X(k)按正按正常順序排列在存儲(chǔ)單元常順序排列在存儲(chǔ)單元,而輸入是按順而輸入是按順序序: 這種順序稱作倒位序這種順序稱作倒位序,即二進(jìn)制數(shù)即二進(jìn)制數(shù)倒位。在編程時(shí)需完成倒位序，才能執(zhí)倒位。在編程時(shí)需完成倒位序，才能執(zhí)行原位計(jì)算。行原位計(jì)算。）；）；7(),3 (),5

16、(),1 (6(),2(),4(),0(xxxxxxxxn =00n =10n =01n =11n =01n =1101010101 ),(012nnnx(n2)x(000) 0 x(100) 4 x(010) 2 x(110) 6 x(001) 1x(101) 5 x(011) 3 x(111) 7 （偶）（偶）（奇）（奇） 倒位序由奇偶分組造成倒位序由奇偶分組造成,以以N=8為例為例 說明如下說明如下:順序順序I起始及終止序號(hào)為：起始及終止序號(hào)為：16倒序倒序J起始序號(hào)為：起始序號(hào)為：N/2=4 當(dāng)當(dāng)IJ 時(shí)，時(shí)，A(I)和和A(J)的內(nèi)容調(diào)換的內(nèi)容調(diào)換 x(0)x(1)x(2)x(3)x

17、(4)x(5)x(6)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)形成倒序后，將原存儲(chǔ)器放的輸入序列重新按倒序排列。形成倒序后，將原存儲(chǔ)器放的輸入序列重新按倒序排列。X(I)X(J)I=J時(shí)不時(shí)不需要需要交換交換例計(jì)算 ， 。 計(jì)算 點(diǎn)FFT。用時(shí)間抽取輸入倒序算法，問倒序前寄存器的數(shù) 和倒序后 的數(shù)據(jù)值？2)(nnx31.2 , 1 , 0n32N)13( x)13( x16913)13(2x5232 N210)01101()13(102

18、)22()10110(48422)13(2x解：倒序前解：倒序前 倒序倒序 倒序?yàn)榈剐驗(yàn)?倒序后倒序后 3）蝶形運(yùn)算對(duì)對(duì)N = 2L點(diǎn)點(diǎn)FFT，輸入倒位序，輸出自然序，輸入倒位序，輸出自然序，第第m級(jí)運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為級(jí)運(yùn)算每個(gè)蝶形的兩節(jié)點(diǎn)距離為 2m1，第第m級(jí)運(yùn)算：級(jí)運(yùn)算：1111111( )( )(2)(2)( )(2)mrmmmNmmrmmmNXkXkXkWXkXkXkW 4）存儲(chǔ)單元）存儲(chǔ)單元輸入序列輸入序列x(n) : N個(gè)存儲(chǔ)個(gè)存儲(chǔ)單元單元rNW系數(shù)系數(shù) ：N / 2個(gè)存儲(chǔ)單元個(gè)存儲(chǔ)單元5）翅權(quán)）翅權(quán)12, 1 , 0,NkWkN14, 1 , 0,22/NkWWkNkN18, 1 , 0,44/NkWWkNkN3 , 1 , 0,kWkN1 , 0,22/kWWkNkN0,44/kWWkNkN當(dāng)當(dāng) N=8時(shí)：時(shí)：4、DIT算法的其他形式流圖算