《第四章快速傅里葉變換(FFT)》

1、本章主要內(nèi)容本章主要內(nèi)容 引言引言 基基2FFT2FFT算法算法第第4 4章章 快速傅里葉變換快速傅里葉變換(FFT)(FFT) DFTDFT是信號分析與處理中的一種重要變換。但是信號分析與處理中的一種重要變換。但直接計(jì)算直接計(jì)算DFTDFT的的計(jì)算量與變換區(qū)間長度計(jì)算量與變換區(qū)間長度N N的平方成正比的平方成正比，當(dāng)，當(dāng)N N較大時(shí)，計(jì)算量較大時(shí)，計(jì)算量太大，不適合直接用太大，不適合直接用DFTDFT算法進(jìn)行譜分析和信號的實(shí)時(shí)處理。算法進(jìn)行譜分析和信號的實(shí)時(shí)處理。 19651965年發(fā)現(xiàn)了年發(fā)現(xiàn)了DFTDFT的的快速算法快速算法，使，使DFTDFT的運(yùn)算效率提高的運(yùn)算效率提高1 12 2個(gè)個(gè)

2、數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實(shí)時(shí)處理創(chuàng)數(shù)量級，為數(shù)字信號處理技術(shù)應(yīng)用于各種信號的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。 19841984年，提出了年，提出了分裂基快速算法分裂基快速算法，使運(yùn)算效率進(jìn)一步提高；，使運(yùn)算效率進(jìn)一步提高；4.1 4.1 引言引言 4.2.1 4.2.1 直接計(jì)算直接計(jì)算DFTDFT的特點(diǎn)及減少運(yùn)算量的途徑的特點(diǎn)及減少運(yùn)算量的途徑 1.1.直接計(jì)算直接計(jì)算DFTDFT 長度為長度為N N的有限長序列的有限長序列x(n)x(n)的的DFTDFT為：為：2 2、減少運(yùn)算量的思路、減少運(yùn)算量的思路 N點(diǎn)點(diǎn)DFT的復(fù)乘

3、次數(shù)等于的復(fù)乘次數(shù)等于N2。把把N點(diǎn)點(diǎn)DFT分解為幾個(gè)較短的分解為幾個(gè)較短的DFT，可使乘法次數(shù)減少。，可使乘法次數(shù)減少。4.2 4.2 基基2FFT2FFT算法算法考慮考慮x(n)x(n)為復(fù)數(shù)序列的為復(fù)數(shù)序列的一般情況，對某一個(gè)一般情況，對某一個(gè)k k值，值，直接按上式計(jì)算直接按上式計(jì)算X(k)X(k)值值需要需要N N次復(fù)數(shù)乘法次復(fù)數(shù)乘法、(N-1)(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法。 3 3、減少運(yùn)算量的方法、減少運(yùn)算量的方法 分解分解N N為較小值為較小值，把序列分解為幾個(gè)較短的序列，分別計(jì)算其，把序列分解為幾個(gè)較短的序列，分別計(jì)算其DFTDFT值；值； 利用利用旋轉(zhuǎn)因子旋轉(zhuǎn)因子W WN

4、 Nk k的周期性、對稱性的周期性、對稱性進(jìn)行合并、歸類處理，以減進(jìn)行合并、歸類處理，以減少少DFTDFT的運(yùn)算次數(shù)。的運(yùn)算次數(shù)。 周期性周期性： 對稱性對稱性：4 4、FFTFFT算法思想算法思想 不斷地把不斷地把長序列長序列的的DFTDFT分解成分解成幾個(gè)短序列幾個(gè)短序列的的DFTDFT，并利用旋轉(zhuǎn)因，并利用旋轉(zhuǎn)因子的子的周期性周期性和和對稱性對稱性來減少來減少DFTDFT的運(yùn)算次數(shù)。的運(yùn)算次數(shù)。2mN mN mmNNNNNmmNNWWWWWW 2mN mN mmNNNNNmmNNWWWWWW 22()jm lNjmm lNmNNNNWeeW22()jm lNjmm lNmNNNNWeeW

5、22()jm lNjmm lNmNNNNWeeW2mN mN mmNNNNNmmNNWWWWWW 4.2.2 4.2.2 時(shí)域抽取法基時(shí)域抽取法基2FFT2FFT基本原理基本原理 FFTFFT算法分為兩大類：算法分為兩大類：時(shí)域抽取法時(shí)域抽取法FFT(FFT(簡稱簡稱DIT-FFT)DIT-FFT) 頻域抽取法頻域抽取法FFT(FFT(簡稱簡稱DIFDIFFFT)FFT)。1 1、時(shí)域抽取法時(shí)域抽取法FFTFFT的的算法思想算法思想 將序列將序列x(n)x(n)按按n n為奇、偶數(shù)分為為奇、偶數(shù)分為x x1 1(n)(n)、x x2 2(n)(n)兩組序列；用兩組序列；用2 2個(gè)個(gè)N/2N/2

6、點(diǎn)點(diǎn)DFTDFT來完成一個(gè)來完成一個(gè)N N點(diǎn)點(diǎn)DFTDFT的計(jì)算。的計(jì)算。 設(shè)序列設(shè)序列x(n)x(n)的長度為的長度為N N，且滿足：，且滿足： (1)(1)按按n n的奇偶把的奇偶把x(n)x(n)分解為兩個(gè)分解為兩個(gè)N/2N/2點(diǎn)的子序列點(diǎn)的子序列2 ,MNM為自然數(shù)為自然數(shù) 12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr(2)用用N/2點(diǎn)點(diǎn)X1(k)和和X2(k)表示序列

7、表示序列x(n)的的N點(diǎn)點(diǎn)DFT X(k)/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W偶數(shù)奇數(shù)/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNN

8、krkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W/ 2 1/ 2 12(21)00/ 2 1/ 2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWxrWxr W/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx n Wx n Wxr WxrWx rWx r W222222/2jkrNjkrkrkrNNNWeeW222222/2jkrN

9、jkrkrkrNNNWeeW/2 1/2 11/22/21200( )( )( )( )( )NNkrkkrkNNNNrrX kx r WWx r WX kW Xk注意：注意：這里的這里的k的取值范圍為的取值范圍為0，1，N-1由于由于X X1 1(k)(k)和和X X2 2(k)(k)均以均以N/2N/2為周期，且為周期，且 , X(k), X(k)可表示為可表示為: : 對上式的運(yùn)算用下圖所示的對上式的運(yùn)算用下圖所示的流圖符號流圖符號來表示來表示2NkkNNWW 這樣將N點(diǎn)DFT分解為兩個(gè)N/2點(diǎn)的DFTX1(k)X2(k)X1(k)+ WNkX2(k)X1(k)WNkX2(k)WNk圖：

10、蝶形運(yùn)算符號完成一個(gè)蝶形運(yùn)算需要完成一個(gè)蝶形運(yùn)算需要一次復(fù)數(shù)乘和兩次復(fù)數(shù)一次復(fù)數(shù)乘和兩次復(fù)數(shù)加法運(yùn)算，經(jīng)過一次分加法運(yùn)算，經(jīng)過一次分解后，共需要復(fù)數(shù)乘和解后，共需要復(fù)數(shù)乘和復(fù)數(shù)加的次數(shù)為復(fù)數(shù)加的次數(shù)為2(N/2)2+N/2和和N2/21212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkW XkkNNX kXkW Xkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW Xkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW

11、 Xkk1111N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(0)X2(0)WN0X (0)X (4)1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW Xkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW XkkN=8點(diǎn)的點(diǎn)的DIT-2FFT(時(shí)域抽取圖時(shí)域抽取圖)一次分解圖一次分解圖X1(1)X2(1)WN1X (1)X (5)X1(2)X2(2)WN2X (2)X (6)X1(3)X2(3)WN3X

12、 (3)X (7) 將將x x1 1(r)(r)按按r r取奇、偶可分解成取奇、偶可分解成2 2個(gè)長度為個(gè)長度為N/4N/4的子序列的子序列 根據(jù)上面推導(dǎo)可得：根據(jù)上面推導(dǎo)可得： 將將x2(r)按按r取奇、偶可分解成取奇、偶可分解成2個(gè)長個(gè)長N/4的子序列的子序列 )()()(4231kXWkXkXkNk=0,1,N/4-1；)()()4(4231kXWkXNkXkN)2()(13lxlx14,.,1 , 0Nl) 12()(14lxlx(3)(3)第二次分解第二次分解)()()(4231kXWkXkXkNk=0,1,k=0,1,N/2-1,N/2-1)2()(25lxlx) 12()(26l

13、xlx14,.,1 , 0Nl)()()(6252kXWkXkXkNk=0,1,N/4-1；)()()4(6252kXWkXNkXkNN / 4 點(diǎn)DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N / 4 點(diǎn)DFTN / 4 點(diǎn)DFTN / 4 點(diǎn)DFTX1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)N=8N=8點(diǎn)點(diǎn)DFTDFT的二次時(shí)域抽取分解圖的二次時(shí)域抽取分解圖 X3(0)X4(0)WN/20X3(1)X4(1)WN/21X5(0

14、)X6(0)WN/20X5(1)X6(1)WN/21)()()(4231kXWkXkXkN)()()4(4231kXWkXNkXkN)()()(6252kXWkXkXkNk=0,1,N/4-1；)()()4(6252kXWkXNkXkN再次分解，對再次分解，對N=8N=8點(diǎn)，可分解三次。點(diǎn)，可分解三次。X (5)N=8點(diǎn)DIT-FFT運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (6)X3(1)X4(0)X4(1)X5(0)X5(

15、1)X6(0)X6(1)WN/20WN/21WN/20WN/40 x(7)WN/21L=1級L=2L=3X (7)X3(0)X1(0)WN/40WN/40WN/40N=8點(diǎn)DIT-FFT運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)x(5)x(3)WN0WN1WN2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)WN0WN2WN0WN0WN0WN0 x(7)WN2WN0L=1級L=2L=3X (7)4.2.3 DITFFT4.2.3 DITFFT算法與直接計(jì)算算法與直接計(jì)算DFTDFT運(yùn)算量的比較運(yùn)算量的比較1 1、直接、直接DFTDFT運(yùn)算運(yùn)算N N點(diǎn)運(yùn)算點(diǎn)運(yùn)算

16、 復(fù)數(shù)乘次數(shù)：復(fù)數(shù)乘次數(shù)：NN 復(fù)數(shù)加次數(shù)：復(fù)數(shù)加次數(shù)：N(N-1)2 2、 用用DIT-FFTDIT-FFT作作N N點(diǎn)運(yùn)算點(diǎn)運(yùn)算 復(fù)數(shù)乘次數(shù)：復(fù)數(shù)乘次數(shù)：MN/2=N/2log2N 復(fù)加次數(shù)：復(fù)加次數(shù)： 2N/2M= Nlog2N可見可見FFTFFT大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。整個(gè)運(yùn)算流圖中有M級蝶形，每一級運(yùn)算流圖中有N/2個(gè)蝶形，每個(gè)蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運(yùn)算。1. 1.原位計(jì)算原位計(jì)算 序列長為序列長為N=2M點(diǎn)的點(diǎn)的FFT，有，有M級蝶形級蝶形，每級有，每級有N/2個(gè)蝶形運(yùn)算個(gè)蝶形運(yùn)算。 同一級中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對本蝶形有用

17、同一級中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對本蝶形有用，每個(gè)蝶，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平線上。這樣，當(dāng)計(jì)算完一形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平線上。這樣，當(dāng)計(jì)算完一個(gè)蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)個(gè)蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元。單元。經(jīng)過經(jīng)過M級運(yùn)算后，原來存放輸入序列數(shù)據(jù)的級運(yùn)算后，原來存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元中個(gè)存儲(chǔ)單元中可依次存放可依次存放X(k)的的N個(gè)值。個(gè)值。原位計(jì)算原位計(jì)算：利用同一存儲(chǔ)單元存儲(chǔ)蝶形輸入、輸出數(shù)據(jù)的方法。：利用同一存儲(chǔ)單元存儲(chǔ)蝶形輸入、輸出數(shù)據(jù)的方法。 優(yōu)點(diǎn)優(yōu)點(diǎn)：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。：節(jié)

18、約存儲(chǔ)空間、降低設(shè)備成本。4.2.4 DIT-FFT4.2.4 DIT-FFT的運(yùn)算規(guī)律及編程思的運(yùn)算規(guī)律及編程思想想每蝶形都要乘每蝶形都要乘以以旋轉(zhuǎn)因子旋轉(zhuǎn)因子 ，p p稱為旋轉(zhuǎn)因子的指數(shù)。稱為旋轉(zhuǎn)因子的指數(shù)。N N8 82 23 3時(shí)各級的旋轉(zhuǎn)因子時(shí)各級的旋轉(zhuǎn)因子 第一級第一級: :L=1,L=1,有有1 1個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子： 第二級第二級: :L=2,L=2,有有2 2個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子： 第三級第三級: :L=3,L=3,有有4 4個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子：對于對于N N2 2M M 的的一般情況，一般情況，第第L L級級共有共有2 2L-1L-1個(gè)不同的旋轉(zhuǎn)因子：個(gè)不同的旋轉(zhuǎn)

19、因子：2. 2.旋轉(zhuǎn)因子和運(yùn)算級數(shù)的關(guān)系旋轉(zhuǎn)因子和運(yùn)算級數(shù)的關(guān)系PNW024JWWWJLJNPN1 ,022JWWWJLJNPN3 ,2, 1 ,02JWWWJLJNPN12,.,1 , 012LJLPNJWWNMLMMLL2222LMJNJMLNPNWWW22LMJP2可以確定第可以確定第L L級運(yùn)算的旋轉(zhuǎn)因子級運(yùn)算的旋轉(zhuǎn)因子3 3、同一級中，同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目、同一級中，同一旋轉(zhuǎn)因子對應(yīng)蝶形數(shù)目 第第L L級級FFTFFT運(yùn)算中，運(yùn)算中，同一旋轉(zhuǎn)因子同一旋轉(zhuǎn)因子用在用在2M-L個(gè)蝶形中；個(gè)蝶形中；4 4、同一級中，使用相同旋轉(zhuǎn)因子的蝶形之間相隔的、同一級中，使用相同旋轉(zhuǎn)因子的蝶形之間

20、相隔的“距離距離” 第第L L級中，蝶距：級中，蝶距：D=2L。5 5、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離、同一蝶形運(yùn)算兩輸入數(shù)據(jù)的距離 在輸入倒序，輸出原序的在輸入倒序，輸出原序的FFTFFT變換中，第變換中，第L L級的每個(gè)蝶形的兩個(gè)級的每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距：輸入數(shù)據(jù)相距：B=2B=2L-1L-1。 6 6、碼位顛倒、碼位顛倒 輸入序列輸入序列x(n)x(n)經(jīng)過經(jīng)過M M級時(shí)域奇、偶抽選后，輸出序列級時(shí)域奇、偶抽選后，輸出序列X(k)X(k)的順序的順序和輸入序列的順序關(guān)系為和輸入序列的順序關(guān)系為倒位關(guān)系倒位關(guān)系。7 7、蝶形運(yùn)算的規(guī)律、蝶形運(yùn)算的規(guī)律 序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如

21、果蝶形運(yùn)算的兩個(gè)輸入序列經(jīng)過時(shí)域抽選后，存入數(shù)組中，如果蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距數(shù)據(jù)相距B B個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式：個(gè)點(diǎn)，應(yīng)用原位計(jì)算，蝶形運(yùn)算可表示成如下形式： XL-1(J)X L-1 (J+B)XL (J)= XL-1(J)+ WNp X L-1 (J+B)XL (J) = XL-1(J) WNp X L-1 (J+B)WNpp=J2M-L， J=0,1,2, ,2L-11B=2L-1(1)(1)倒序倒序: :根據(jù)倒序規(guī)律，對輸入自然順序根據(jù)倒序規(guī)律，對輸入自然順序序列序列x(n)x(n)進(jìn)行倒序處理；進(jìn)行倒序處理；(2)(2)循環(huán)層循環(huán)層1 1: :確定運(yùn)算的

22、級數(shù)，確定運(yùn)算的級數(shù)，L=1L=1 M M (N=2(N=2M M) )；確定一蝶形兩輸入數(shù)據(jù)距離；確定一蝶形兩輸入數(shù)據(jù)距離B=2B=2L-1L-1(3)(3)循環(huán)層循環(huán)層2 2: :確定確定L L級的級的(B=)2(B=)2L-1L-1個(gè)旋轉(zhuǎn)因個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)子；旋轉(zhuǎn)因子指數(shù)p=2p=2M-LM-LJ J，J=0J=0 B-1B-1；(4)(4)循環(huán)層循環(huán)層3 3: :對于同一旋轉(zhuǎn)因子，用于同對于同一旋轉(zhuǎn)因子，用于同一級一級2 2M-LM-L個(gè)蝶形運(yùn)算中：個(gè)蝶形運(yùn)算中：k k的取值從的取值從J J到到N-1N-1，步長為步長為2 2L L ( (使用同一旋轉(zhuǎn)因子的蝶形相距的使用同一旋

23、轉(zhuǎn)因子的蝶形相距的距離距離) )(5)(5)完成一個(gè)蝶形運(yùn)算完成一個(gè)蝶形運(yùn)算開 始送入 x(n)，MN 2 M倒 序L 1 , M 0 , B 1P 2 M LJk J , N 1 , 2LpNpNWBkXkXBkXWBkXkXkX)()()()()()(輸 出結(jié) 束B 2 L 18 8、 DIT-FFTDIT-FFT程序框圖程序框圖 N=2M，用，用M位二進(jìn)制數(shù)位二進(jìn)制數(shù)(nM-1nM-2n1n0)2表示序列的序號表示序列的序號n. M次偶奇時(shí)域抽選過程為次偶奇時(shí)域抽選過程為：對最低位按：對最低位按0、1分為偶、奇兩組，分為偶、奇兩組，次低位也按次低位也按0、1分組，依此類推，分組，依此類推

24、，M次分解后形成次分解后形成為：為： 二進(jìn)制數(shù)二進(jìn)制數(shù)(N=8)(N=8)分解倒序圖分解倒序圖10041015110611170000001101020113倒序前倒序前00111015011311170000100401021106倒序后倒序后可 見 ， 只 要可 見 ， 只 要將將 順 序 數(shù)順 序 數(shù) 的的二 進(jìn) 制 位 倒二 進(jìn) 制 位 倒置 可 得 到 對置 可 得 到 對應(yīng) 的 二 進(jìn) 制應(yīng) 的 二 進(jìn) 制倒序值倒序值。10n20101n100010n0111(n2n1n0)29 9、序列的倒序、序列的倒序思考題思考題：已知：已知N=16點(diǎn)，在點(diǎn)，在DIT-FFT運(yùn)算中，序數(shù)為運(yùn)算

25、中，序數(shù)為2的二進(jìn)制經(jīng)數(shù)的二進(jìn)制經(jīng)數(shù)倒序后為多少倒序后為多少?順序數(shù)增加1，是 在 順 序 數(shù)的 二 進(jìn) 制 數(shù)的最低位加1，向左進(jìn)位到序數(shù)是在M位二進(jìn)制數(shù)的最高位加 1 ， 向 右進(jìn)位(0010-0100)(0010-0100)順序和倒序二進(jìn)制數(shù)對照表順序和倒序二進(jìn)制數(shù)對照表 N=2M，用，用M位二進(jìn)制數(shù)表示，位二進(jìn)制數(shù)表示，則從左至則從左至右的十進(jìn)制權(quán)值為：右的十進(jìn)制權(quán)值為： N/2、N/4、N/8,、2, 1 對倒序數(shù)對倒序數(shù)J，其下一個(gè)序數(shù)是，其下一個(gè)序數(shù)是在該序數(shù)在該序數(shù)J的二進(jìn)制首位碼加的二進(jìn)制首位碼加1，相當(dāng)于十進(jìn)制運(yùn)算相當(dāng)于十進(jìn)制運(yùn)算J+N/2。 計(jì)算機(jī)上倒序數(shù)的實(shí)現(xiàn)過程為：計(jì)

26、算機(jī)上倒序數(shù)的實(shí)現(xiàn)過程為：JN/2？JN/4輸入當(dāng)前倒序數(shù)十進(jìn)制數(shù)值JNYNY2NJ 22NJ JN/2MNYMNJ2 結(jié)束J=J-N/2倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律為了實(shí)現(xiàn)原位運(yùn)算，在倒序數(shù)為了實(shí)現(xiàn)原位運(yùn)算，在倒序數(shù)J J形成后，需將原存儲(chǔ)器中存放的輸形成后，需將原存儲(chǔ)器中存放的輸入序列重新排列。下面先分析入序列重新排列。下面先分析N=8N=8點(diǎn)的倒序規(guī)律。點(diǎn)的倒序規(guī)律。 x(0)x(0)A(0)A(0)x(1)x(1)A(1)A(1)x(2)x(2)A(2)A(2)x(3)x(3)A(3)A(3)x(4)x(4)A(4)A(4)x(5)x(5)A(5)A(5)x(6)x(6

27、)A(6)A(6)x(7)x(7)A(7)A(7)A(0)A(0) A(1)A(1)A(2)A(2)A(3)A(3) A(4)A(4)A(5)A(5)A(6)A(6) A(7)A(7)輸入序列輸入序列數(shù)組數(shù)組分析上圖分析上圖N=8點(diǎn)倒序規(guī)律，順序數(shù)點(diǎn)倒序規(guī)律，順序數(shù)I與倒序數(shù)與倒序數(shù)J 存在關(guān)系：存在關(guān)系： I = J時(shí)，不交換；時(shí)，不交換； I J時(shí)，不交換，直接更新序數(shù)值；時(shí)，不交換，直接更新序數(shù)值；I IJ Jx(0)x(0)x(2)x(2)x(4)x(4)x(1)x(1)x(5)x(5)x(6)x(6)x(3)x(3) x(7)x(7)倒序程序框圖倒序程序框圖221NNLHJNLHI

28、1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY計(jì)算倒序值交換數(shù)組中的數(shù)據(jù)不交換數(shù)據(jù)，避免再次調(diào)換前面調(diào)換過的一對數(shù)據(jù)，計(jì)算下一個(gè)倒數(shù)值。在基在基2快速算法中，頻域抽取法快速算法中，頻域抽取法FFT也是一種常用的快速算法。也是一種常用的快速算法。1、算法思想和運(yùn)算過程、算法思想和運(yùn)算過程 設(shè)序列設(shè)序列x(n)長度為長度為N=2M，將，將序列序列x(n)前后對半分為前后對半分為x1(n)、x2(n)兩兩組序列，用組序列，用2個(gè)個(gè)N/2點(diǎn)點(diǎn)DFT來完成一個(gè)來完成一個(gè)N點(diǎn)點(diǎn)DFT的計(jì)算。的計(jì)算。10/ 2 110/ 2/ 2 1/ 2 1(/ 2)00/

29、2 1/ 20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnnNNNknk nNNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nWn10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )(

30、)( )( )()2 ( )()2NkNnNNknknNNnn NNNknk nNNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnn NNNknk nNNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nWk=偶數(shù) /21,( 1)1kNkNkWk ,k=奇數(shù) 4.2.5 4.2.5 頻域抽取法頻域抽取法FFT(DIFFFT)FF

31、T(DIFFFT)將將X(k)分解成分解成偶數(shù)偶數(shù)組組與與奇數(shù)奇數(shù)組組，當(dāng)，當(dāng)k取取偶數(shù)偶數(shù)(k=2r,r=0,1,N/2-1)時(shí)時(shí) 當(dāng)當(dāng)k取奇數(shù)取奇數(shù)(k=2r+1,r=0,1,N/2-1)時(shí)：時(shí)：將將x1(n)和和x2(n)分別代入上式，可得分別代入上式，可得/2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrNnNnnrNNnNXrx nx nWNx nx nWW/2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrNnNnnrNNnNXrx nx nWNx nx nWW/2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrN

32、nNnnrNNnNXrx nx nWNx nx nW Wx1(n)x2(n)/2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nW/2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nW/2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nW/ 2120/ 212/ 20(2)()()2()()2NrnNnNrnNnNXrx nx nWNx nx nW表明表明：X(k)按奇偶按奇偶k值分為兩組值分為兩組

33、: 偶數(shù)組是偶數(shù)組是x1(n)的的N/2點(diǎn)點(diǎn)DFT 奇數(shù)組是奇數(shù)組是x2(n)的的N/2點(diǎn)點(diǎn)DFT/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrxn W/ 2 11/ 20/ 2 12/ 20(2 )( )(21)( )NrnNnNrnNnXrxn WXrxn Wr=0,1,N/2-1那么對序列那么對序列x1(n)、x2(n) 和和x(n)可用蝶形運(yùn)算符號表示可用蝶形運(yùn)算符號表示x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n)x(n+N/2)WNnWNnx(n+N/2)DIF-FFT蝶形運(yùn)算流圖符號N=8N=8時(shí)第時(shí)第1 1

34、次分解的運(yùn)算流圖次分解的運(yùn)算流圖N/2點(diǎn)DFTN/2點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)x(0)x(4)WN0X (3)X (0)X (2)X (4)X (6)X (1)X (5)X (7)x(1)x(5)WN1x(2)x(6)WN2x(3)x(7)WN3 N=2M，N/2仍是偶數(shù)仍是偶數(shù)，繼續(xù)將繼續(xù)將N/2點(diǎn)進(jìn)行分解點(diǎn)進(jìn)行分解。將輸入序列。將輸入序列x1(n)、x2(n)分別按前、后對半分解成分別按前、后對半分解成4個(gè)長個(gè)長N/4的子序列，其的子序列，其n=0,1,，N/4-1x3(n)= x1(n)+ x1(n+N/4) x4(n) =

35、x1(n)-x1(n+N/4)WN/2n x5(n)= x2(n)+ x2(n+N/4) x6(n) = x2(n)-x2(n+N/4)WN/2nX(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0 x1(0)x1(1)x1(2)x1(3)N/4 點(diǎn)DFTx3(0)x3(1)N/4 點(diǎn)DFTx4(0)x4(1)WN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2N/4 點(diǎn)DFTN/4 點(diǎn)DFTx2(0)x2(1)x2(2)x2(3)x5(0)x5(1)x6(0)x6(1)DIFFFT二次分解運(yùn)算流圖(N=8) 經(jīng)過三次分解

36、后，經(jīng)過三次分解后，DIFFFTDIFFFT運(yùn)算流圖運(yùn)算流圖(N=8)(N=8)為為x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)WN0WN1WN2WN3X (0)X (4)X (2)X (6)X (1)X (5)X (3)X (7)x3(0)x3(1)x4(0)x4(1)x5(0)x5(1)x6(0)x6(1)WN0WN2WN0WN2WN0WN0WN0WN0DIF-FFTDIF-FFT算法也可采用算法也可采用原位原位計(jì)算；計(jì)算；N=2N=2M M時(shí)，共有時(shí)，共有M M級運(yùn)算級運(yùn)算，每級共，每級共

37、有有N/2N/2個(gè)蝶形個(gè)蝶形，DITDIT與與DIFDIF算法的算法的運(yùn)算次數(shù)運(yùn)算次數(shù)相同。相同。DITDIT與與DIFDIF不同的是：不同的是： DIF-FFTDIF-FFT算法算法輸入序列為自然序列輸入序列為自然序列，輸出為倒序輸出為倒序序列。在序列。在M M級運(yùn)級運(yùn)算完成后，需對輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的算完成后，需對輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的X(k)X(k)。 蝶形運(yùn)算符號不同蝶形運(yùn)算符號不同：DIT-FFTDIT-FFT蝶形是先相乘，后加蝶形是先相乘，后加/ /減；而減；而DIF-DIF-FFTFFT蝶形是先加蝶形是先加/ /減，后相乘。減，后相乘。DIT-FFT蝶形

38、運(yùn)算符號X1(k)X2(k)X1(k)+ WNkX2(k)X1(k)WNkX2(k)WNkx2(n)=x(n)x(n+N/2)WNnx(n)x1(n)=x(n)+x(n+N/2)WNnx(n+N/2)DIF-FFT蝶形運(yùn)算流圖符號2 2、DIF-FFTDIF-FFT運(yùn)算規(guī)律運(yùn)算規(guī)律改變改變輸入輸入/ /輸出節(jié)點(diǎn)輸出節(jié)點(diǎn), ,中間節(jié)點(diǎn)中間節(jié)點(diǎn)的排列順序的排列順序, ,可得到不同變形的可得到不同變形的FFTFFT運(yùn)算流圖。因此，運(yùn)算流圖。因此，DIT-FFTDIT-FFT和和DIF-FFTDIF-FFT運(yùn)算流圖都不是唯一的。運(yùn)算流圖都不是唯一的。 X(0)X(4)X(2)X(6)X(1)X(5)X

39、(3)X(7)X3(0)X5(0)X4(0)X6(0)X3(1)X5(1)X4(1)X6(1)WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN0WN2WN1WN3X1(0)X2(0)X1(2)X2(2)X1(1)X2(1)X1(3)X2(3)WN0WN0WN0WN2WN2輸出序列輸入序列DIT-FFT的一種變形運(yùn)算流圖（輸入順序，輸出倒序） 3 3、其它形式的、其它形式的DIT-FFTDIT-FFT運(yùn)算流圖運(yùn)算流圖 用同樣的方法可得用同樣的方法可得DIT-FFTDIT-FFT的另外一種變形運(yùn)算流圖，的另外一種變形運(yùn)算流圖，輸輸入和輸出均為順序排列，但不能采用原位計(jì)算。入和輸出均為順序排列，但不能采用原位計(jì)算。WN0WN0WN2WN0X(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)WN0WN2WN1WN3WN2WN0WN0WN0DITFFT的一種變形運(yùn)算流圖1 1、DFTDFT和和IDFTIDFT的公式比較的公式比較 上述上述FFTFFT算法流圖也可以用于離散傅里葉逆變換算法流圖也可以用于離散傅里葉逆變換IDFTIDFT