1、本章主要內(nèi)容本章主要內(nèi)容 理解按時(shí)間抽選的基理解按時(shí)間抽選的基2FFT2FFT算法原理、運(yùn)算流圖、算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)；所需計(jì)算量和算法特點(diǎn)； 理解按頻率抽選的基理解按頻率抽選的基2FFT2FFT算法原理、運(yùn)算流圖、算法原理、運(yùn)算流圖、所需計(jì)算量和算法特點(diǎn)；所需計(jì)算量和算法特點(diǎn)； 理解理解I IFFTFFT算法；算法； 實(shí)序列的實(shí)序列的FFTFFT算法算法第第4 4章章 離散離散傅里葉變換傅里葉變換的計(jì)算與應(yīng)用的計(jì)算與應(yīng)用 DFT是信號(hào)分析與處理中的一種重要變換。但是信號(hào)分析與處理中的一種重要變換。但直接直接計(jì)算計(jì)算DFT的計(jì)算量與變換區(qū)間長(zhǎng)度的計(jì)算量與變換區(qū)間長(zhǎng)度N的平方

2、成正比的平方成正比，當(dāng)當(dāng)N較大時(shí)，計(jì)算量太大，直接用較大時(shí)，計(jì)算量太大，直接用DFT算法進(jìn)行譜分算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。 1965年發(fā)現(xiàn)了年發(fā)現(xiàn)了DFT的一種快速算法的一種快速算法，使，使DFT的運(yùn)算的運(yùn)算效率提高效率提高12個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。理技術(shù)的發(fā)展。 1984年，提出了年，提出了分裂基快速算法分裂基快速算法，使運(yùn)算效率進(jìn)一，使運(yùn)算效率進(jìn)一步提高；步提高；4.1 離散傅里葉變換的高效計(jì)算思路

3、離散傅里葉變換的高效計(jì)算思路4.1 4.1 離散傅里葉變換的高效計(jì)算思路離散傅里葉變換的高效計(jì)算思路 直接計(jì)算直接計(jì)算DFT的運(yùn)算量的運(yùn)算量長(zhǎng)度為長(zhǎng)度為N的有限長(zhǎng)序列的有限長(zhǎng)序列x(n)的的DFT為：為：10( )( ),0,1,1NknNnX kx n WkN考慮考慮x(n)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)為復(fù)數(shù)序列的一般情況，對(duì)某一個(gè)k值，直接按上式計(jì)算值，直接按上式計(jì)算X(k)值需要值需要N次復(fù)數(shù)次復(fù)數(shù)乘法乘法、(N-1)次復(fù)數(shù)加法次復(fù)數(shù)加法。 02(1)(1)(0)(1)(2)(1)kkNkNNNNXxWxWxWx NW4.1 4.1 離散傅里葉變換的高效計(jì)算思路離散傅里葉變換的高效計(jì)算

4、思路例例N=1024，N2=1,048,5762 2、減少運(yùn)算量的思路和方法、減少運(yùn)算量的思路和方法思路：思路：N N點(diǎn)點(diǎn)DFTDFT的復(fù)乘次數(shù)等于的復(fù)乘次數(shù)等于N N2 2。把把N N點(diǎn)點(diǎn)DFTDFT分分 解為幾個(gè)較短的解為幾個(gè)較短的DFTDFT，可使乘法次數(shù)大大減少。，可使乘法次數(shù)大大減少。另外，旋轉(zhuǎn)因子另外，旋轉(zhuǎn)因子W Wm mN N具有周期性和對(duì)稱性。具有周期性和對(duì)稱性。4.1 4.1 離散傅里葉變換的高效計(jì)算思路離散傅里葉變換的高效計(jì)算思路3 3、FFTFFT算法思想算法思想 不斷地把不斷地把長(zhǎng)序列長(zhǎng)序列的的DFTDFT分解成分解成幾個(gè)短序列幾個(gè)短序列的的DFTDFT，并利用旋轉(zhuǎn)因子

5、的，并利用旋轉(zhuǎn)因子的周期性周期性和和對(duì)稱性對(duì)稱性來(lái)減少來(lái)減少DFTDFT的運(yùn)算次數(shù)。的運(yùn)算次數(shù)。方法：方法： 分解分解N為較小值為較小值：把序列分解為幾個(gè)較短的序列，：把序列分解為幾個(gè)較短的序列，分別計(jì)算其分別計(jì)算其DFT值；值； 利用利用旋轉(zhuǎn)因子旋轉(zhuǎn)因子WNk的周期性、對(duì)稱性的周期性、對(duì)稱性、可約性、可約性進(jìn)進(jìn)行合并、歸類處理，以減少行合并、歸類處理，以減少DFT的運(yùn)算次數(shù)。的運(yùn)算次數(shù)。 周期性周期性： 對(duì)稱性對(duì)稱性： 可約性可約性：4.1 4.1 離散傅里葉變換的高效計(jì)算思路離散傅里葉變換的高效計(jì)算思路2mN mN mmNNNNNmmNNWWWWWW 2mN mN mmNNNNNmmNNW

6、WWWWW 2mN mN mmNNNNNmmNNWWWWWW()()k n lNk lN nknNNNWWW/,kmnknkn mknmNNN mNWWWW 一、一、時(shí)域抽取法基時(shí)域抽取法基2FFT基本原理基本原理 FFT算法基本上分為兩大類：算法基本上分為兩大類：時(shí)域抽取法時(shí)域抽取法FFT(簡(jiǎn)稱簡(jiǎn)稱DIT-FFT)和和頻域抽取法頻域抽取法FFT(簡(jiǎn)稱簡(jiǎn)稱DIFFFT)。1、時(shí)域抽取法、時(shí)域抽取法FFT的算法思想：的算法思想： 將序列將序列x(n)按按n為奇、偶數(shù)分為為奇、偶數(shù)分為x1(n)、x2(n)兩組序兩組序列；用列；用2個(gè)個(gè)N/2點(diǎn)點(diǎn)DFT來(lái)完成一個(gè)來(lái)完成一個(gè)N點(diǎn)點(diǎn)DFT的計(jì)算。的計(jì)算

7、。 4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法 設(shè)序列設(shè)序列x(n)的長(zhǎng)度為的長(zhǎng)度為N，且滿足：，且滿足：(1) 按按n的奇偶把的奇偶把x(n)分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的子序列點(diǎn)的子序列4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法2 ,MNM為自然數(shù)為自然數(shù) 12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNxrxrr12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNxrxrr(2)用用N/2點(diǎn)點(diǎn)X1(k)和和X2(k)表示表示N點(diǎn)點(diǎn) X(k

8、)4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法/21/212(21)00/21/2121200()()()( 2)( 21)()()knknNNnnNNkrkrNNrrNNkkrNNrrXkxnWxnWxrWxrWxrWxrW偶數(shù)偶數(shù)奇數(shù)奇數(shù)/21/212(21)00/21/2121200()()()( 2)( 21 )()()k nk nNNnnNNk rkrNNrrNNkk rNNrrXkxnWxnWxrWxrWxrWxrW/2 1/2 12(21)00/2 1/2 121200( )( )( )(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrX kx

9、 nWx nWx r Wx rWx rWx r W/21/212(21 )00/21/2121200()()()( 2)( 21 )()()k nk nNNnnNNk rkrNNrrNNkk rNNrrX k xn W xn WxrWxr WxrW xrW / 21/ 212( 21)00/ 21/ 2121200()()()(2 )(21)( )( )knknNNnnNNkrkrNNrrNNkkrNNrrXkx n Wx n Wxr WxrWxrWxr W222222/2jk rNj k rk rk rNNNWe e W 222222/ 2jk rNjk rk rk rNNNW e eW/2

10、 1/2 11/22/21200( )( )( )( )( )NNkrkkrkNNNNrrX kx r WWx r WX kW X k注意：注意：這里這里k的取值范圍為的取值范圍為0，1，N-1？由 于由 于 X1( k ) 和和 X2( k ) 均均 隱 含隱 含 周 期 為周 期 為 N / 2 ，且且 , X(k)又可表示為又可表示為: 對(duì)上式的運(yùn)算用下圖所示的對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)流圖符號(hào)來(lái)表示來(lái)表示4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法2NkkNNWW 這樣將這樣將N點(diǎn)點(diǎn)DFT分解為兩個(gè)分解為兩個(gè)N/2點(diǎn)的點(diǎn)的DFT1212( )( )( )0,1 ,12()(

11、)( )0,1 ,122kNkNNXkX k WX k kNNXkX k WX k k 1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkWXkkNNX kXkWXkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkWXkkNNX kXkWXkk對(duì)上式的運(yùn)算用下圖所示的對(duì)上式的運(yùn)算用下圖所示的流圖符號(hào)流圖符號(hào)來(lái)表示來(lái)表示4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法X1(k)X2(k)X(k)X1(k)+ WNkX2(k)X(kN/2)X1(k) WNkX2(k)WNk蝶形運(yùn)算蝶形運(yùn)算圖圖-11212( )( )(

12、 )0,1 ,12()( )( )0,1 ,122kNkNNXkX k WX k kNNXkX k WX k k 1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkWXkkNNX kXkWXkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkWXkkNNX kXkWXkk例例:X(0)=X1(0)+ WN0X2(0)，X(1)=X1(1)+ WN1X2(1)x(0)x(2)x(4)x(6)WN0X (0)WN1X (1)WN2X (2)WN3X (3)X1(0)X1(1)X1(2)X1(3)N/2點(diǎn)點(diǎn)DFTX2(0)

13、X2(1)X2(2)X2(3)N/2點(diǎn)點(diǎn)DFTx1(0)x1(1)x1(2)x1(3)x(1)x(3)x(5)x(7)x2(0)x2(1)x2(2)x2(3)X (4)-1X (5)-1X (6)-1X (7)-1N=8點(diǎn)的點(diǎn)的DIT-2FFT(時(shí)域抽取圖時(shí)域抽取圖)一次分解圖一次分解圖x1x2(3)第二次分解：第二次分解： 將將x1(r)按按r取奇、偶可分解成取奇、偶可分解成2個(gè)長(zhǎng)度為個(gè)長(zhǎng)度為N/4的子序列的子序列 x3(l)= x1(2l)、 x4(l) = x1(2l+1)，根據(jù)上面推導(dǎo)可得：根據(jù)上面推導(dǎo)可得：X1 (k)= X3(k)+ WN/2k X4(k)， k=0,1,N/2-1

14、 將將x2(r)按按r取奇、偶可分解成取奇、偶可分解成2個(gè)長(zhǎng)個(gè)長(zhǎng)N/4的子序列的子序列 x5(l)= x2(2l) ， l=0,1,，N/4 x6(l) = x2(2l+1) ； 同理得同理得4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法l=0,1,，N/4-1；X1 (k+N/4)=X3(k) WN/2k X4(k)， k=0,1,N/4-1；X1 (k)=X3(k)+WN/2k X4(k)， k=0,1,N/4-1；X2(k) = X5(k)+ WN/2k X6(k)， k=0,1,N/4-1 ；X2(k+N/4) = X5(k) WN/2k X6(k), k=0,1,N/4-1；X1(

15、0)W40 x3(0)x3(1)x4(0)x4(1)W80X (0)W81X (1)W82X (2)W83X (3)X (4)-1X (5)-1X (6)-1X3(0)X3(1)N/2點(diǎn)點(diǎn)DFTX1(1)W41X (7)-1X1(2)-1X1(3)-1X4(0)X4(1)N/2點(diǎn)點(diǎn)DFTx1(0)x1(2)x1(1)x1(3)N/2點(diǎn)點(diǎn)DFTX2(0)X2(1)X2(2)X2(3)x5(0)x5(1)x6(0)x6(1)W40W41X5(0)X5(1)X6(0)X6(1)-1-1N/2點(diǎn)點(diǎn)DFTx2(0)x2(2)x2(1)x2(3)x(0)=x(4)=x(2)=x(6)=x(1)=x(5)=

16、x(3)=x(7)=N=8點(diǎn)點(diǎn)DFT的二次時(shí)域抽取分解圖的二次時(shí)域抽取分解圖 x3(l)= x1(2l) x4(l) = x1(2l+1)4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法l=0,1,，N/4-1；4 133404 14440 0 1/( )( ),( )( )NkrNrNkrNrX kx r WkX kx r W 0332303323001 101( )( )( )( )( )( )XxW xXxW x 以以N=8為例，將為例，將k=0,1代入得代入得4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法N=8點(diǎn)點(diǎn)DIT-FFT運(yùn)算流圖運(yùn)算流圖X(5)x(0)x(4)x(2)x(6)

17、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(1)X6(0)X6(1)WN/20WN/21WN/20WN/40 x(7)WN/21L=1級(jí)級(jí)L=2L=3X(7)X3(0)X1(0)WN/40WN/40WN/40-1-1-1-1-1-1-1-1-1-1-1-1二、二、 DITFFT算法與直接計(jì)算算法與直接計(jì)算DFT運(yùn)算量的比較運(yùn)算量的比較1、直接、直接DFT運(yùn)算運(yùn)算N點(diǎn)運(yùn)算點(diǎn)運(yùn)算： 復(fù)數(shù)乘次數(shù)：復(fù)數(shù)乘次數(shù)：NN 復(fù)數(shù)加次數(shù)：復(fù)數(shù)加次

18、數(shù)：N(N-1)2、 用用DIT-FFT作作N點(diǎn)運(yùn)算：點(diǎn)運(yùn)算： 復(fù)數(shù)乘次數(shù)：復(fù)數(shù)乘次數(shù)：MN/2=N/2log2N； 復(fù)加次數(shù)：復(fù)加次數(shù)： 2 N/2M= Nlog2N?？梢娍梢奆FT大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。大大減少了運(yùn)算次數(shù)，提高了運(yùn)算速度。4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法整個(gè)運(yùn)算流圖整個(gè)運(yùn)算流圖中有中有M級(jí)蝶形級(jí)蝶形，每 一 級(jí) 中 有每 一 級(jí) 中 有N/2個(gè)蝶形個(gè)蝶形，每個(gè)蝶形需每個(gè)蝶形需一一次復(fù)乘和兩次次復(fù)乘和兩次復(fù)數(shù)加復(fù)數(shù)加運(yùn)算。運(yùn)算。4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法1.蝶形運(yùn)算蝶形運(yùn)算 蝶形運(yùn)算可表示成如下形式：蝶形運(yùn)算可表示成如下形式

19、：11( )( )()pLLNLXkXkW XkB XL-1(k)X L-1 (k+B)p=J2M-L， J=0,1,2, ,2L-11B=2L-1WNp-1三、三、 DITFFT的運(yùn)算的運(yùn)算特點(diǎn)特點(diǎn)及編程思想及編程思想11()( )()pLLNLXkBXkW XkB 2.原位計(jì)算原位計(jì)算序列長(zhǎng)為序列長(zhǎng)為N=2M點(diǎn)的點(diǎn)的FFT，有，有M級(jí)蝶形級(jí)蝶形，每級(jí)有，每級(jí)有N/2個(gè)蝶個(gè)蝶形運(yùn)算形運(yùn)算。 同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)本蝶形同一級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)只對(duì)本蝶形有用有用，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平，每個(gè)蝶形的輸入、輸出數(shù)據(jù)節(jié)點(diǎn)在用一條水平線上。這樣，當(dāng)計(jì)算完一個(gè)蝶形

20、后，所得的輸出數(shù)據(jù)線上。這樣，當(dāng)計(jì)算完一個(gè)蝶形后，所得的輸出數(shù)據(jù)可立即存入原輸入數(shù)據(jù)所占用的存儲(chǔ)單元?？闪⒓创嫒朐斎霐?shù)據(jù)所占用的存儲(chǔ)單元。經(jīng)過(guò)經(jīng)過(guò)M級(jí)級(jí)運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的運(yùn)算后，原來(lái)存放輸入序列數(shù)據(jù)的N個(gè)存儲(chǔ)單元中可依個(gè)存儲(chǔ)單元中可依次存放次存放X(k)的的N個(gè)值。個(gè)值。原位計(jì)算原位計(jì)算：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸：利用同一存儲(chǔ)單元存儲(chǔ)蝶形計(jì)算輸入、輸出數(shù)據(jù)的方法。出數(shù)據(jù)的方法。 優(yōu)點(diǎn)優(yōu)點(diǎn)：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。：節(jié)約存儲(chǔ)空間、降低設(shè)備成本。4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法3.旋轉(zhuǎn)因子和運(yùn)算級(jí)數(shù)的關(guān)系旋轉(zhuǎn)因子和運(yùn)算級(jí)數(shù)的關(guān)系N點(diǎn)點(diǎn)DITFFT運(yùn)算流

21、圖中，每個(gè)蝶形都要乘以運(yùn)算流圖中，每個(gè)蝶形都要乘以旋轉(zhuǎn)因子旋轉(zhuǎn)因子WpN，p稱為旋轉(zhuǎn)因子的指數(shù)。稱為旋轉(zhuǎn)因子的指數(shù)。N8 23 時(shí)各級(jí)的旋轉(zhuǎn)因子時(shí)各級(jí)的旋轉(zhuǎn)因子 第一級(jí)：第一級(jí)：L=1， 有有1個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子： WNp =WN/4J =W2LJ J=0 第二級(jí)：第二級(jí)：L=2，有，有2個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子： WNp =WN/2J =W2LJ J=0,1 第三級(jí)：第三級(jí)：L=3，有，有4個(gè)旋轉(zhuǎn)因子：個(gè)旋轉(zhuǎn)因子： WNp =WNJ =W2LJ J=0,1,2,3 對(duì)于對(duì)于N2M 的的一般情況，一般情況，第第L級(jí)級(jí)共有共有2L-1個(gè)不同的旋轉(zhuǎn)因子：個(gè)不同的旋轉(zhuǎn)因子： WNp =W2LJ J

22、=0,1,2, ,2L-11 2L =2L M 2M = N 2L M4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目同一級(jí)中，同一旋轉(zhuǎn)因子對(duì)應(yīng)蝶形數(shù)目 第第L級(jí)級(jí)FFT運(yùn)算中，運(yùn)算中，同一旋轉(zhuǎn)因子同一旋轉(zhuǎn)因子用在用在2M-L個(gè)蝶形中；個(gè)蝶形中；同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的同一級(jí)中，蝶形運(yùn)算使用相同旋轉(zhuǎn)因子之間相隔的“距離距離” 第第L級(jí)中，蝶距：級(jí)中，蝶距：D=2L。4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法故：故： 按照上面兩式可以確定第按照上面兩式可以確定第L L級(jí)運(yùn)算的旋轉(zhuǎn)因子。級(jí)運(yùn)算的旋轉(zhuǎn)因子。JJ 2M-LWNp =W2LJ

23、=WN 2L-M = WNp=J2M-L， J=0,1,2, ,2L-114. 序列的倒序序列的倒序 N=2M，用，用M位二進(jìn)制數(shù)位二進(jìn)制數(shù)(nM-1nM-2n1n0)2表示序列的序號(hào)表示序列的序號(hào)n. M次偶奇時(shí)域抽選過(guò)程為次偶奇時(shí)域抽選過(guò)程為：對(duì)最低位按：對(duì)最低位按0、1分為偶、奇兩組，分為偶、奇兩組，次低位也按次低位也按0、1分組，依此類推，分組，依此類推，M次分解后形成次分解后形成為：為： 4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法二進(jìn)制數(shù)二進(jìn)制數(shù)(N=8)分解倒序圖分解倒序圖10041015110611170000001101020113倒序前倒序前00111015011311

24、170000100401021106倒序后倒序后可 見 ， 只 要可 見 ， 只 要將將 順 序 數(shù)順 序 數(shù) 的的二 進(jìn) 制 位 倒二 進(jìn) 制 位 倒置 可 得 到 對(duì)置 可 得 到 對(duì)應(yīng) 的 二 進(jìn) 制應(yīng) 的 二 進(jìn) 制倒序值倒序值。10n20101n100010n0111(n2n1n0)2思考題思考題：已知：已知N=16點(diǎn)，在點(diǎn)，在DIT-FFT運(yùn)算中，序數(shù)為運(yùn)算中，序數(shù)為2的二進(jìn)制的二進(jìn)制數(shù)經(jīng)倒序后為多少數(shù)經(jīng)倒序后為多少?4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法順序數(shù)順序數(shù)增加增加1，是 在 順 序 數(shù)是 在 順 序 數(shù)的 二 進(jìn) 制 數(shù)的 二 進(jìn) 制 數(shù)的的最低位加最低位加1

25、，向左向左進(jìn)位進(jìn)位到序數(shù)是在到序數(shù)是在M位二進(jìn)制位二進(jìn)制數(shù)的數(shù)的最高位最高位加加1，向右，向右進(jìn)位進(jìn)位(00100100)順序和倒序二進(jìn)制數(shù)對(duì)照表順序和倒序二進(jìn)制數(shù)對(duì)照表倒序程序框圖倒序程序框圖 為了實(shí)現(xiàn)原位運(yùn)算，以節(jié)約存貯空間，提高運(yùn)算速率。在為了實(shí)現(xiàn)原位運(yùn)算，以節(jié)約存貯空間，提高運(yùn)算速率。在倒序數(shù)倒序數(shù) J 形成后，需將原存儲(chǔ)器中存放的輸入序列重新排列。形成后，需將原存儲(chǔ)器中存放的輸入序列重新排列。下面先分析下面先分析N=8點(diǎn)的倒序規(guī)律。點(diǎn)的倒序規(guī)律。 4.2 基基2時(shí)間抽選的時(shí)間抽選的FFT算法算法x(0)A(0)x(1)A(1)x(2)A(2)x(3)A(3)x(4)A(4)x(5)A

26、(5)x(6)A(6)x(7)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)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ù)值；IJx(0)x(2)x(4)x(1)x(5)x(6)x(3)x(7)221NNLHJNLHI 1 , N1I JTJAJXIAIXT)()()()(J KLHK KJJ2KKKJJNNY計(jì)算倒計(jì)算倒序值序值交換數(shù)組交換數(shù)組中的數(shù)據(jù)中的數(shù)據(jù)不交換數(shù)據(jù)，避免不交換數(shù)據(jù)，避免再次

27、調(diào)換前面調(diào)換再次調(diào)換前面調(diào)換過(guò)的一對(duì)數(shù)據(jù)，計(jì)過(guò)的一對(duì)數(shù)據(jù)，計(jì)算下一個(gè)倒數(shù)值。算下一個(gè)倒數(shù)值。6.DIT-FFT程序框圖程序框圖根據(jù)根據(jù)DIT-FFT原理和過(guò)程，原理和過(guò)程，DIT-FFT的完整程序框的完整程序框圖包括以下幾部分：圖包括以下幾部分：(1)倒序倒序:輸入自然順序序列輸入自然順序序列x(n)，根據(jù)倒序，根據(jù)倒序規(guī)律，進(jìn)行倒序處理；規(guī)律，進(jìn)行倒序處理；(2)循環(huán)層循環(huán)層1:確定運(yùn)算的級(jí)數(shù)，確定運(yùn)算的級(jí)數(shù)，L=1 M (N=2M)；確定一蝶形兩輸入數(shù)據(jù)距離；確定一蝶形兩輸入數(shù)據(jù)距離B=2L-1(3)循環(huán)層循環(huán)層2:確定確定L級(jí)的級(jí)的(B=)2L-1個(gè)旋轉(zhuǎn)因子個(gè)旋轉(zhuǎn)因子；旋轉(zhuǎn)因子指數(shù)；旋轉(zhuǎn)

28、因子指數(shù)p=2M-LJ，J=0 B-1；(4)循環(huán)層循環(huán)層3:對(duì)于同一旋轉(zhuǎn)因子，用于同一對(duì)于同一旋轉(zhuǎn)因子，用于同一級(jí)級(jí)2M-L個(gè)蝶形運(yùn)算中：個(gè)蝶形運(yùn)算中：k的取值從的取值從J到到N-1，步，步長(zhǎng)為長(zhǎng)為2L (使用同一旋轉(zhuǎn)因子的蝶形相距的距離使用同一旋轉(zhuǎn)因子的蝶形相距的距離) (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 14.2.4 DIT-FFT的其他形式流圖W40W40W40W40W40W40W

29、40W40W40W40W40W40X (0)X (1)X (2)X (3)X (4)X (5)X (6)X (7)x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)按時(shí)間抽選，輸入自然序，輸出倒位序的按時(shí)間抽選，輸入自然序，輸出倒位序的FFT流圖流圖DIT-FFT的其他形式流圖按時(shí)間抽選，輸入和輸出都是自然序的按時(shí)間抽選，輸入和輸出都是自然序的FFT流圖流圖W80W81W82W83X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0WN2WN2-1-1-1-1WN0WN0WN0WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)

30、x(7)-1-1-1-1DIT-FFT的其他形式流圖按時(shí)間抽選按時(shí)間抽選,各級(jí)具有相同幾何形狀的各級(jí)具有相同幾何形狀的FFT流圖流圖WN0WN1WN2WN3X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)-1-1-1-1WN0WN0WN2WN2-1-1-1-1WN0WN0WN0WN0 x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)-1-1-1-1 在基在基2快速算法中，頻域抽取法快速算法中，頻域抽取法FFT也是一種常用的快速算法。也是一種常用的快速算法。1、算法思想和運(yùn)算過(guò)程、算法思想和運(yùn)算過(guò)程 設(shè)序列設(shè)序列x(n)長(zhǎng)度為長(zhǎng)度為N=2M，將，將序列序列x(n)

31、前后對(duì)半分為前后對(duì)半分為x1(n)、x2(n)兩組序列，用兩組序列，用2個(gè)個(gè)N/2點(diǎn)點(diǎn)DFT來(lái)完成一個(gè)來(lái)完成一個(gè)N點(diǎn)點(diǎn)DFT的計(jì)算。的計(jì)算。4.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法10/2110/2/21/21(/2)00/21/20()() ()()()()()2()() 2NkNnNNknknNNnnNNNknknNNNnnNkNknNNnXkDFTxnxnWxnWxnWNxnWxnWNxnWxnWn10/2110/2/21/21(/2)00/21/20()() ()()()()()2()() 2NkNnNNknknNNnnNNNknknNNNnnNkNknNNnXkDF

32、TxnxnWxnWxnWNxnWxnWNxnWxnW10/2110/2/21/21(/2)00/21/20()()()()()()()2()()2NkNnNNknknNNnnNNNknknNNNnnNkNknNNnXkDFTxnxnWxnWxnWNxnWxnWNxnWxnW10/2110/2/21/21(/2)00/21/20()() ()()()()()2()() 2NkNnNNknknNNnnNNNknknNNNnnNkNknNNnXkDFTxnxnWxnWxnWNxnWxnWNxnWxnWk=偶數(shù)偶數(shù) /21 ,( 1 )1kNkNkWk ,k=奇數(shù)奇數(shù) 4.2.5 按頻率抽取的基按頻率

33、抽取的基-2FFT算法算法將將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)分別代入上式，可得分別代入上式，可得/ 211/ 20/ 212/ 20( 2)()( 21 )()Nr nNnNr nNnXrxnWXrxnW/ 21( 21 )0/ 21/ 20( 21 )()() 2()() 2NnrNnNnn rNNnNXrxnxnWNxnxnWW/ 21( 21 )0/ 21/ 20( 21)()()2()()2NnrNnNnn rN

34、NnNXrx nx nWNx nx nWW/2 1( 21 )0/2 1/20( 21 ) ()( ) 2()( ) 2NnrNnNnn rNNnNX rx nx nWNx nx nW W x1(n)x2(n)/211/20/212/20( 2)()( 21)()Nr nNnNr nNnXrxnWXrxnW/ 2120/ 212/ 20( 2)()() 2()() 2Nr nNnNr nNnNXrxnxnWNxnxnW/ 2120/ 212/ 20( 2)()() 2()() 2Nr nNnNr nNnNXrxnxnWNxnxnW/2 120/2 12/20(2 ) ( )()2 ( )()2

35、NrnNnNrnNnNX rxnxnWNxnxnW/2 120/2 12/20(2 ) ( )()2 ( )()2NrnNnNrnNnNX rx nx nWNx nx nW表明表明：X(k)按奇偶按奇偶k值分為兩組值分為兩組: 偶數(shù)組偶數(shù)組是是x1(n)的的N/2點(diǎn)點(diǎn)DFT 奇數(shù)組奇數(shù)組是是x2(n)的的N/2點(diǎn)點(diǎn)DFTr=0,1,N/2-1那么對(duì)序列那么對(duì)序列x1(n)、x2(n) 和和x(n)可用蝶形運(yùn)算符號(hào)表示可用蝶形運(yùn)算符號(hào)表示4.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n) x(n+N/2) WNnx(n+N

36、/2)DIF-FFT蝶形運(yùn)算流圖符號(hào)蝶形運(yùn)算流圖符號(hào)WNk-14.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法N=8時(shí)第時(shí)第1次分解的運(yùn)算流圖次分解的運(yùn)算流圖x(0)x(1)x(2)x(3)WN0X (0)WN1X (2)WN2X (4)WN3X (6)N/2點(diǎn)點(diǎn)DFTN/2點(diǎn)點(diǎn)DFTx(4)x(5)x(6)x(7)X (1)-1X (3)-1X (5)-1X (7)-1N=2M，N/2仍是偶數(shù)仍是偶數(shù)，繼續(xù)將繼續(xù)將N/2點(diǎn)進(jìn)行分解點(diǎn)進(jìn)行分解。將輸入序列。將輸入序列x1(n)、x2(n)分別按前、后對(duì)半分解成分別按前、后對(duì)半分解成4個(gè)長(zhǎng)個(gè)長(zhǎng)N/4的子序列的子序列,其其n=0,1,，N

37、/4-14.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法x3(n)= x1(n)+ x1(n+N/4) x4(n) = 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/2nDIFFFT二次分解運(yùn)算流圖二次分解運(yùn)算流圖(N=8) X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0N/4 點(diǎn)點(diǎn)DFTN/4 點(diǎn)點(diǎn)DFTWN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2N/4 點(diǎn)點(diǎn)DFTN/4 點(diǎn)點(diǎn)DFT-1-1-1-1

38、-1-1-1-1DIFFFT運(yùn)算流圖運(yùn)算流圖(N=8)4.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法X(0)X(4)X(2)X(6)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN0WN1WN2WN3X(1)X(5)X(3)X(7)WN2WN0WN2-1-1-1-1-1-1-1-1-1-1-1-1WN0WN0WN0WN02、DIF-FFT運(yùn)算規(guī)律運(yùn)算規(guī)律 DIF-FFT算法也可采用算法也可采用原位原位計(jì)算；計(jì)算；N=2M時(shí)，共有時(shí)，共有M級(jí)運(yùn)算級(jí)運(yùn)算，每級(jí)共有，每級(jí)共有N/2個(gè)蝶形個(gè)蝶形，DIT與與DIF算法的算法的運(yùn)算次數(shù)運(yùn)算次數(shù)相同。相同。DIT與與D

39、IF不同的是不同的是： DIF-FFT算法算法輸入序列為自然序列輸入序列為自然序列，輸出為倒序輸出為倒序序列。因此，在序列。因此，在M級(jí)級(jí)運(yùn)算完成后，需對(duì)輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的運(yùn)算完成后，需對(duì)輸出數(shù)據(jù)進(jìn)行倒序才能得到自然順序的X(k)。 蝶形運(yùn)算符號(hào)不同蝶形運(yùn)算符號(hào)不同：DIT-FFT蝶形是先相乘，后加蝶形是先相乘，后加/減；而減；而DIF-FFT蝶蝶形是先加形是先加/減，后相乘。減，后相乘。4.2.5 按頻率抽取的按頻率抽取的基基-2FFT算法算法x(n)x1(n)=x(n)+x(n+N/2)x2(n)=x(n) x(n+N/2) WNnx(n+N/2)DIF-FFT蝶形運(yùn)算流圖

40、符號(hào)蝶形運(yùn)算流圖符號(hào)WNk-13、其它形式的、其它形式的DIT-FFT運(yùn)算流圖運(yùn)算流圖 通過(guò)改變通過(guò)改變輸入輸入/輸出節(jié)點(diǎn)輸出節(jié)點(diǎn),中間節(jié)點(diǎn)中間節(jié)點(diǎn)的排列順序的排列順序,可以得到不同變形的可以得到不同變形的FFT運(yùn)運(yùn)算流圖。因此，前面介紹的算流圖。因此，前面介紹的DIT-FFT和和DIF-FFT運(yùn)算流圖都不是唯一的運(yùn)算流圖都不是唯一的。 4.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法輸出序列輸出序列輸入序列輸入序列DIT-FFT的一種變形運(yùn)算流圖（輸入順序，輸出倒序）的一種變形運(yùn)算流圖（輸入順序，輸出倒序） X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)X3(0)

41、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)算流圖，的另外一種變形運(yùn)算流圖，輸入輸入和輸出均為順序排列，但不能采用原位計(jì)算。和輸出均為順序排列，但不能采用原位計(jì)算。4.2.5 按頻率抽取的基按頻率抽取的基-2FFT算法算法WN0WN0WN2WN0X(0)X(1)X(2)X(3)X(4)X(5

42、)X(6)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)WN0WN2WN1WN3WN2WN0WN0WN0DITFFT的一種變形運(yùn)算流圖的一種變形運(yùn)算流圖一、一、 IDFT的高效算法的高效算法1 DFT和和IDFT的公式比較的公式比較上述上述FFT算法流圖也可以用于離散傅里葉逆變換算法流圖也可以用于離散傅里葉逆變換IDFT根據(jù)運(yùn)算公式可以看出，只需將根據(jù)運(yùn)算公式可以看出，只需將DFT的的系數(shù)系數(shù)WNkn變?yōu)樽優(yōu)閃N-kn，最后結(jié)果最后結(jié)果乘以乘以1/N，就是，就是IDFT的運(yùn)算公式。的運(yùn)算公式。4.2.6 傅里傅里反反葉變換葉變換（IDFT）的）的快速快速計(jì)算方法計(jì)算方

43、法1010( ) ( )( )1( ) ( )( )NkNnNknNkX kDFT xnxnWxnIDFT xnX kWN1010( ) ( )( )1( ) ( )( )NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WNX(k)1010()() ()1()() ()NkNnNk nNkXkD F TxnxnWxnI D F TxnXkWNn2 用用FFT流圖實(shí)現(xiàn)流圖實(shí)現(xiàn)IDFT快速算法快速算法 將將DIT-FFT或或DIF-FFT蝶形運(yùn)算流圖中蝶形運(yùn)算流圖中旋轉(zhuǎn)因子旋轉(zhuǎn)因子WNp改為改為WN-p 在在IDFT快速算法的最后結(jié)果輸出前，快速算法的最后結(jié)果輸出前，

44、乘以乘以1/N常數(shù)常數(shù)；如要防止；如要防止溢出，可在每一級(jí)運(yùn)算中，輸出支路溢出，可在每一級(jí)運(yùn)算中，輸出支路分別乘以分別乘以1/2，實(shí)現(xiàn)系數(shù)，實(shí)現(xiàn)系數(shù)分級(jí)分擔(dān)。分級(jí)分擔(dān)。 在在IDFT快速算法中，快速算法中，輸入序列為輸入序列為X(k)，而，而輸出序列為輸出序列為x(n)。 節(jié)點(diǎn)對(duì)應(yīng)關(guān)系：節(jié)點(diǎn)對(duì)應(yīng)關(guān)系： DIT-FFT對(duì)應(yīng)對(duì)應(yīng)DIF-IFFT DIF-FFT對(duì)應(yīng)對(duì)應(yīng)DIT-IFFT4.2.6 傅里反葉變換（傅里反葉變換（IDFT）的快速計(jì)算方法）的快速計(jì)算方法4.2.6 傅里反葉變換（傅里反葉變換（IDFT）的快速計(jì)算方法）的快速計(jì)算方法DITIFFT運(yùn)算流圖運(yùn)算流圖 WN0WN1WN2WN3W

45、N0WN0N1x(0)x(4)x(2)x(6)x(4)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)WN2WN2N1N1N1N1N1N1N14.2.6 傅里反葉變換（傅里反葉變換（IDFT）的快速計(jì)算方法）的快速計(jì)算方法WN02121x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)212121WN121WN221WN3212121WN021WN2212121WN021WN22121WN02121WN0212121WN021WN021DITIFFT運(yùn)算流圖運(yùn)算流圖(防止溢防止

46、溢出出) 3、直接調(diào)用、直接調(diào)用FFT程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)IFFT的計(jì)算的計(jì)算 對(duì)對(duì)FFT流程作一些修改后，調(diào)用流程作一些修改后，調(diào)用FFT程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)IFFT的快速計(jì)算。的快速計(jì)算。具體實(shí)現(xiàn)方法：具體實(shí)現(xiàn)方法： 先將先將X(k)取共軛取共軛，得到，得到X*(k) ； 直接調(diào)用直接調(diào)用FFT子程序計(jì)算出子程序計(jì)算出DFTX*(k)的值；的值； 對(duì)輸出序列對(duì)輸出序列取共軛取共軛，并乘以，并乘以1/N常數(shù)。常數(shù)。 雖然雖然2次用了取共軛運(yùn)算，但可以和次用了取共軛運(yùn)算，但可以和FFT共用一個(gè)子程序，實(shí)共用一個(gè)子程序，實(shí)現(xiàn)方便?，F(xiàn)方便。4.2.6 傅里反葉變換（傅里反葉變換（IDFT）的快速計(jì)算方法）

47、的快速計(jì)算方法*)(*1*)(*1(n)*xx(n) :)(*1)(*1)(* :)(1)()( :101010kXDFTNWkXNkXDFTNWkXNnxWkXNkXIDFTnxIDFTNkknNNkknNNkknN 再再取取復(fù)復(fù)共共軛軛取取復(fù)復(fù)共共軛軛公公式式*)(*1*)(*1(n)*xx(n) :)(*1)(*1)(* :)(1)()( :101010kXDFTNWkXNkXDFTNWkXNnxWkXNkXIDFTnxIDFTNkknNNkknNNkknN 再再取取復(fù)復(fù)共共軛軛取取復(fù)復(fù)共共軛軛公公式式*)(*1*)(*1(n)*xx(n) :)(*1)(*1)(* :)(1)()( :

48、101010kXDFTNWkXNkXDFTNWkXNnxWkXNkXIDFTnxIDFTNkknNNkknNNkknN 再再取取復(fù)復(fù)共共軛軛取取復(fù)復(fù)共共軛軛公公式式* )( *1*) ( *1(n)* xx(n) :)( *1) ( *1) ( * :) (1)( ) ( :101010kXDFTNWkXNkXDFTNWkXNnxWk XNk XIDFTn xIDFTNkknNNkknNNkknN 再再取取復(fù)復(fù)共共軛軛取取復(fù)復(fù)共共軛軛公公式式*)( *1*)( *1(n)*xx(n) :)( *1)( *1)( * :)(1)()( :101010kXDFTNWkXNkXDFTNWkXNnxW

49、kXNkXIDFTnxIDFTNkknNNkknNNkknN 再再取取復(fù)復(fù)共共軛軛取取復(fù)復(fù)共共軛軛公公式式* 兩個(gè)長(zhǎng)度相同的實(shí)序列兩個(gè)長(zhǎng)度相同的實(shí)序列 可以將兩個(gè)長(zhǎng)度相同的實(shí)序列組合成一個(gè)復(fù)序列來(lái)進(jìn)可以將兩個(gè)長(zhǎng)度相同的實(shí)序列組合成一個(gè)復(fù)序列來(lái)進(jìn)行行FFT運(yùn)算，從而一次完成這兩個(gè)實(shí)序列的運(yùn)算，從而一次完成這兩個(gè)實(shí)序列的FFT，減少減少了總的計(jì)算量。了總的計(jì)算量。4.2.5 實(shí)序列的實(shí)序列的FFT算法算法 設(shè)設(shè)p(n) 和和g(n) 是兩個(gè)長(zhǎng)度均為是兩個(gè)長(zhǎng)度均為N的實(shí)序列，并設(shè)：的實(shí)序列，并設(shè)： 又設(shè)又設(shè) ， ， 則由則由DFT的線性有：的線性有：)()()(njgnpny)()(k

50、PnpDFT )()(kGngDFT )()(kYnyDFT )()()(kjGkPkY 利用有限長(zhǎng)序列利用有限長(zhǎng)序列DFT的對(duì)稱性，有的對(duì)稱性，有4.2.5 實(shí)序列的實(shí)序列的FFT算法算法)()()(Re)()(*kNYkYnyDFTnpDFTkP 21)()()(Im)()(*kNYkYnyjDFTnjgDFTkjG 21上兩式中上兩式中0kN-1。 一個(gè)一個(gè)2 2N N點(diǎn)的實(shí)序列點(diǎn)的實(shí)序列 將一個(gè)將一個(gè)2 2N N點(diǎn)的實(shí)序列點(diǎn)的實(shí)序列x(n)x(n)按偶數(shù)點(diǎn)和奇數(shù)點(diǎn)按偶數(shù)點(diǎn)和奇數(shù)點(diǎn)分組形成兩個(gè)分組形成兩個(gè)N N點(diǎn)實(shí)序列：點(diǎn)實(shí)序列： 1, 1 , 0 ) 12()()2()(Nnnxngn

51、xnp4.2.5 實(shí)序列的實(shí)序列的FFT算法算法 則有：則有： k=0,1,N-1 k=0,1,N-1 k2 k2 ( )( )( )()( )( )NNX kP kWG kX kNP kWG k 其中：其中： 實(shí)序列實(shí)序列p(n) p(n) 和和g(n) g(n) 的的DFT P(k) DFT P(k) 和和G(k) G(k) 可以采用前述所可以采用前述所說(shuō)的方法作一次說(shuō)的方法作一次N N點(diǎn)復(fù)序列的點(diǎn)復(fù)序列的FFTFFT而同時(shí)得到，然后再按而同時(shí)得到，然后再按（）式進(jìn)行組合便得到了）式進(jìn)行組合便得到了2 2N N點(diǎn)實(shí)序列點(diǎn)實(shí)序列x(n) x(n) 的的DFTDFT

52、。10)()(NnnkNWnpkP1, 1 , 0)()(10NkWngkGNnnkN4.2.5 實(shí)序列的實(shí)序列的FFT算法算法4.9.1 用用DFT求線性卷積求線性卷積 如果循環(huán)卷積的長(zhǎng)度如果循環(huán)卷積的長(zhǎng)度N滿足滿足NN1 + N2 -1（N1、N2分別分別是是x(n) 與與h(n) 的長(zhǎng)度），則此循環(huán)卷積就等于的長(zhǎng)度），則此循環(huán)卷積就等于x(n)與與h(n) 的線性卷積，于是，我們用的線性卷積，于是，我們用DFT求得的循環(huán)卷積就是線性求得的循環(huán)卷積就是線性卷積。卷積。 4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 圖圖4.9.1 用用 DFT 求線性卷積求線性卷積 NN1

53、+N2-1)()()(nhnxny 4.9.2 4.9.2 分段卷積分段卷積 在某些場(chǎng)合下，可能要求將一個(gè)有限長(zhǎng)度的序列與一個(gè)長(zhǎng)在某些場(chǎng)合下，可能要求將一個(gè)有限長(zhǎng)度的序列與一個(gè)長(zhǎng)度不定或相當(dāng)長(zhǎng)的序列進(jìn)行線性卷積。若將整個(gè)序列存儲(chǔ)度不定或相當(dāng)長(zhǎng)的序列進(jìn)行線性卷積。若將整個(gè)序列存儲(chǔ)起來(lái)再作大點(diǎn)數(shù)的運(yùn)算，不但運(yùn)算量太大，而且往往時(shí)延起來(lái)再作大點(diǎn)數(shù)的運(yùn)算，不但運(yùn)算量太大，而且往往時(shí)延也不允許，也不允許，4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 在實(shí)際應(yīng)用中，往往要求隨時(shí)接收隨時(shí)即進(jìn)行處理。在這在實(shí)際應(yīng)用中，往往要求隨時(shí)接收隨時(shí)即進(jìn)行處理。在這些情況下，就要將長(zhǎng)序列分段，每一段分別

54、與短序列進(jìn)行些情況下，就要將長(zhǎng)序列分段，每一段分別與短序列進(jìn)行卷積，這就是所謂分段卷積。分段卷積一般有兩種方法，卷積，這就是所謂分段卷積。分段卷積一般有兩種方法，即重疊相加法和重疊保留法。即重疊相加法和重疊保留法。1. 重疊相加法重疊相加法 設(shè)序列設(shè)序列 h(n) 長(zhǎng)為長(zhǎng)為N，x(n) 是長(zhǎng)序列。這種方法是將是長(zhǎng)序列。這種方法是將x(n) 分段，每段長(zhǎng)設(shè)為分段，每段長(zhǎng)設(shè)為M，將每一段分別與將每一段分別與h(n) 進(jìn)行線性卷進(jìn)行線性卷積，然后再將結(jié)果重迭相加。積，然后再將結(jié)果重迭相加。 設(shè)設(shè)x(n) 分為分為x0(n)、x1(n)、，第第k段段xk(n) 表示為：表示為： 4.9 用用DFT的快

55、速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 其他010MnkMnxnxk)()( 故故 (4.9.1) 其中其中 為第為第k段線性卷積的結(jié)果。段線性卷積的結(jié)果。 0kkkMnxnx)()( 00kkkkkMnynhkMnxnhnxny)()()()()()()()()(nhnxnykk4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 圖圖 4.9.2 重疊相加法的分段以及重疊相加法的分段以及 yk(n) 的重疊情的重疊情況況4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積MMMMNMN1MN1MN1 由于由于xk(n) 長(zhǎng)為長(zhǎng)為M，h(n) 長(zhǎng)為長(zhǎng)為N，故故yk(n)

56、 長(zhǎng)為長(zhǎng)為 N +M-1 即即yk(n)的范圍為：的范圍為： yk(n) 顯然比顯然比xk(n)長(zhǎng)，長(zhǎng)的點(diǎn)數(shù)為：長(zhǎng)，長(zhǎng)的點(diǎn)數(shù)為： 而而yk+1(n) 的范圍是：的范圍是： 212 NMkNMkMnkM)(11121 NMkNMk)()(22211 NMkNMMknMk)()()(4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 因此，由因此，由( (k+1)k+1)M M到到( (k+1)k+1)M M+ +N N-2-2這這N N-1-1個(gè)點(diǎn)上，個(gè)點(diǎn)上，y yk k(n) (n) 的后的后部分與部分與y yk+1k+1(n)(n)的前部分發(fā)生了重疊，所以，的前部分發(fā)生了重疊，所

57、以，(4.9.1)(4.9.1)式中式中的求和并不是將各段線性卷積的結(jié)果簡(jiǎn)單地拼接在一起，的求和并不是將各段線性卷積的結(jié)果簡(jiǎn)單地拼接在一起，在這在這N N-1-1個(gè)點(diǎn)上是需要前后兩段的結(jié)果重疊相加的。個(gè)點(diǎn)上是需要前后兩段的結(jié)果重疊相加的。4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 重疊相加法的深入理解：由于重疊相加法的深入理解：由于x xk k(n)(n)在在x(n)x(n)中時(shí)，其前后中時(shí)，其前后都有序列，而截出來(lái)后，其前后都是都有序列，而截出來(lái)后，其前后都是0 0，所以截出后與，所以截出后與h(n)h(n)線性卷積的結(jié)果線性卷積的結(jié)果y yk k(n)(n)的前面的的前

58、面的N N-1-1個(gè)值和后面的個(gè)值和后面的N N-1-1個(gè)值個(gè)值與與x xk k(n)(n)不截出來(lái)時(shí)與不截出來(lái)時(shí)與h(n)h(n)線性卷積所得到的線性卷積所得到的y(n)y(n)中相應(yīng)中相應(yīng)的值是不同的。的值是不同的。4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 例例4.9.1 設(shè)序列設(shè)序列x(n)的非零區(qū)間為的非零區(qū)間為0n9n9，h(n)h(n)的長(zhǎng)度的長(zhǎng)度M=3M=3。將將x(n)x(n)分段，每段長(zhǎng)度分段，每段長(zhǎng)度N N1 1=3=3，用重疊相加法進(jìn)行分用重疊相加法進(jìn)行分段卷積來(lái)計(jì)算線性卷積段卷積來(lái)計(jì)算線性卷積y(n)=x(n)y(n)=x(n)* *h(n)h(n

59、)。 解：先不分段，直接計(jì)算解：先不分段，直接計(jì)算y(n)，以便與用分段卷積所得結(jié)以便與用分段卷積所得結(jié)果進(jìn)行比較。果進(jìn)行比較。 現(xiàn)在用排序法直接計(jì)算線性卷積現(xiàn)在用排序法直接計(jì)算線性卷積y(n)=x(n)y(n)=x(n)* *h(n)h(n)。 x： 0 1 2 3 4 5 6 7 8 9 h： 2 1 0 4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積 注意，我們并不知道這兩個(gè)序列的各個(gè)具體數(shù)值，但是這注意，我們并不知道這兩個(gè)序列的各個(gè)具體數(shù)值，但是這并不影響我們求解。上面列出的各個(gè)數(shù)字表示的是各個(gè)序并不影響我們求解。上面列出的各個(gè)數(shù)字表示的是各個(gè)序號(hào)，比如第號(hào)，比如第2行

60、的行的2、1、0，實(shí)際上分別代表，實(shí)際上分別代表h(2)、h(1)、h(0)。表表3.13.1中列出的線性卷積的結(jié)果也是用序號(hào)表示的，中列出的線性卷積的結(jié)果也是用序號(hào)表示的，比如第比如第2行行y(n)為為00實(shí)際上表示實(shí)際上表示y(n)=x(0)h(0)，而而y(n)為為01+10實(shí)際上表示實(shí)際上表示y(n)=x(0)h(1)+x(1)h(0)，如此等等。如此等等。4.9 用用DFT的快速算法實(shí)現(xiàn)線性卷積的快速算法實(shí)現(xiàn)線性卷積表表 3.1 3.1 n 0 1 2 3 4 5 y(n) 00 01+10 02+11+20 12+21+30 22+31+40 32+41+50 n 6 7 8 9