dsp數(shù)字信號(hào)處理-第4章

1、123nDFTDFT是信號(hào)分析與處理中的一種重要變換。但直是信號(hào)分析與處理中的一種重要變換。但直接計(jì)算接計(jì)算DFTDFT的計(jì)算量與變換區(qū)間長(zhǎng)度的計(jì)算量與變換區(qū)間長(zhǎng)度N N的平方成正的平方成正比，當(dāng)比，當(dāng)N N較大時(shí)，計(jì)算量太大，直接用較大時(shí)，計(jì)算量太大，直接用DFTDFT算法進(jìn)算法進(jìn)行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。行譜分析和信號(hào)的實(shí)時(shí)處理是不切實(shí)際的。n19651965年年庫里庫里和和圖基圖基發(fā)現(xiàn)了發(fā)現(xiàn)了DFTDFT的一種快速算法，的一種快速算法，使使DFTDFT的運(yùn)算效率提高的運(yùn)算效率提高1 12 2個(gè)數(shù)量級(jí)，為數(shù)字信個(gè)數(shù)量級(jí)，為數(shù)字信號(hào)處理技術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條號(hào)處理技

2、術(shù)應(yīng)用于各種信號(hào)的實(shí)時(shí)處理創(chuàng)造了條件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。件，推動(dòng)了數(shù)字處理技術(shù)的發(fā)展。n19841984年，提出了分裂基快速算法，使運(yùn)算效率進(jìn)年，提出了分裂基快速算法，使運(yùn)算效率進(jìn)一步提高；一步提高；4DFTDFT的定義的定義兩者形式類似，差別只在于的指數(shù)符號(hào)不同，及常數(shù)兩者形式類似，差別只在于的指數(shù)符號(hào)不同，及常數(shù)因子因子運(yùn)算量是相同的運(yùn)算量是相同的10 ,)(1)(10 ,)()(1010NnWkXNnxNkWnxkXNknkNNnnkN567nkNWkNnNjkNnNnkNeWW)(2)(mnkmNnkNnmkmNnkNWWWW/,nkNnkNWW)(89二、二、按時(shí)間抽取按時(shí)間

3、抽取(DIT)(DIT)的基的基-2 FFT-2 FFT算法算法 設(shè)設(shè)MN2M M為自然數(shù)為自然數(shù)將長(zhǎng)度為將長(zhǎng)度為N N的序列的序列x(n)x(n)按按n n的的奇偶奇偶分成兩組分成兩組) 12/(, 1 , 0),12()() 12/(, 1 , 0),2()(21 NrrxrxNrrxrx1、算法原理、算法原理10則x(n)的DFT為 12/02212/02112/0)12(12/02)()() 12()2()()()(NrkrNkNNrkrNNrrkNNrkrNnnknNknNWrxWWrxWrxWrxWnxWnxkX偶數(shù)奇數(shù))()(21kXWkXkN=12/0Nk =12/2/212/

4、2/1)()(NkrNkNNkrNWrxWWrxr=0r=011其中12/02/12/02/11)2()()(NrkrNNrkrNWrxWrxkX12/02/12/02/22) 12()()(NrkrNNrkrNWrxWrxkX是x(2r)與x(2r+1)的N/2點(diǎn)DFT。12由于)()2()()()2(22112/0)2(2/11kXNkXkXWrxNkXNrNkrN得)()(22221221kXWkXNkXWNkXNkXkNNkN12, 1 , 0Nk13bWabWa144點(diǎn)基2時(shí)間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT04W14W02W02WX

5、0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm158點(diǎn)基2FFT算法N/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)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)1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kX kW XkkNNX kX kW Xkk1212( )( )( )0,1,12()( )( )0,1,122kNkNNX

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

7、1 (k)=X3(k)+WN/2kX4(k)， k=0,1,N/4-1；X2(k) = X5(k)+ WN/2kX6(k)， k=0,1,N/4-1 ；X2(k+N/2) = X5(k) WN/2kX6(k), k=0,1,N/4-1；17N / 4 點(diǎn)DFTx(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)X1(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 / 4 點(diǎn)DFTN / 4 點(diǎn)DFTN / 4 點(diǎn)DFTX3(0)X3(1)X4(0)X

8、4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/21WN/20N=8點(diǎn)DFT的二次時(shí)域抽取分解圖 X1 (k+N/2)=X3(k)WN/2kX4(k)X1 (k)=X3(k)+WN/2kX4(k)X2(k) = X5(k)+ WN/2kX6(k)X2(k+N/2) = X5(k) WN/2kX6(k)k=0,1,N/4-1 ；18) 1 ()0() 1 ()0() 1 () 1 ()0() 1 ()0()0(1202xWxxWxXxWxxWxXoNoN19再次分解，對(duì)N=8點(diǎn)，可分解三次。X (5)N=8點(diǎn)DIT-FFT運(yùn)算流圖x(0)x(4)x(2)x(6)x(1)

9、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/40WN/40WN/40 x(7)WN/21WN/40L=1級(jí)L=2L=3X (7)X3(0)X1(0)208點(diǎn)基2DIT-FFT算法N=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)WN0WN

10、2WN0WN0WN0WN0 x(7)WN2WN0L=1級(jí)L=2L=3X (7)21整個(gè)運(yùn)算流圖中有M級(jí)蝶形，每一級(jí)運(yùn)算流圖中有N/2個(gè)蝶形，每個(gè)蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運(yùn)算。2223（1）蝶形運(yùn)算）蝶形運(yùn)算（2）原位計(jì)算）原位計(jì)算 （3）序數(shù)重排）序數(shù)重排（4）蝶形類型隨迭代次數(shù)成倍增加）蝶形類型隨迭代次數(shù)成倍增加24（1）蝶形運(yùn)算）蝶形運(yùn)算對(duì)于對(duì)于N=2M，總是可以通過，總是可以通過M次分解最后成為次分解最后成為2點(diǎn)的點(diǎn)的DFT運(yùn)算。這樣構(gòu)成從運(yùn)算。這樣構(gòu)成從x(n)到到X(k)的的M級(jí)運(yùn)算過程。級(jí)運(yùn)算過程。從上面的流圖可看到，每一級(jí)運(yùn)算都由從上面的流圖可看到，每一級(jí)運(yùn)算都由N/2個(gè)蝶形運(yùn)

11、個(gè)蝶形運(yùn)算構(gòu)成。因此每一級(jí)運(yùn)算都需要算構(gòu)成。因此每一級(jí)運(yùn)算都需要N/2次復(fù)乘和次復(fù)乘和N次復(fù)次復(fù)加，這樣經(jīng)過時(shí)間抽取后加，這樣經(jīng)過時(shí)間抽取后M級(jí)運(yùn)算總共需要的運(yùn)算：級(jí)運(yùn)算總共需要的運(yùn)算： 復(fù)乘復(fù)乘 復(fù)加復(fù)加 而直接運(yùn)算時(shí)則與而直接運(yùn)算時(shí)則與N2 成正比。成正比。NNMN2log22NNMN2log25（2）原位計(jì)算）原位計(jì)算 n當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)當(dāng)數(shù)據(jù)輸入到存儲(chǔ)器中以后，每一級(jí)運(yùn)算的結(jié)果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最后輸出，果仍然儲(chǔ)存在同一組存儲(chǔ)器中，直到最后輸出，中間無需其它存儲(chǔ)器，這叫原位計(jì)算。中間無需其它存儲(chǔ)器，這叫原位計(jì)算。n每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)

12、算結(jié)每一級(jí)運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可節(jié)省構(gòu)可節(jié)省存儲(chǔ)單元，降低設(shè)備成本，還可節(jié)省尋址的時(shí)間。尋址的時(shí)間。26（3 3）序數(shù)重排）序數(shù)重排n對(duì)按時(shí)間抽取對(duì)按時(shí)間抽取FFTFFT的原位運(yùn)算結(jié)構(gòu)，當(dāng)運(yùn)算完畢時(shí)，的原位運(yùn)算結(jié)構(gòu)，當(dāng)運(yùn)算完畢時(shí)，正好順序存放著正好順序存放著 x(0)x(0)， x(1)x(1)， x(2)x(2)， x(7) x(7)，因此可直接按順序輸出，因此可直接按順序輸出，n但這種原位運(yùn)算的輸入但這種原位運(yùn)算的輸入 x x（n n）卻不能按這種自然順）卻不能按這種自然順序存入存儲(chǔ)單元中，而是按序存入存儲(chǔ)單元中，而是按x(0)x(0)，x(

13、4)x(4)，x(2)x(2)，x(6)x(6)，x(7)x(7)的順序存入存儲(chǔ)單元，這種順序看起的順序存入存儲(chǔ)單元，這種順序看起來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示這個(gè)順序時(shí)，它正好是這個(gè)順序時(shí)，它正好是“碼位倒置碼位倒置”的順序。的順序。n例如，原來的自然順序應(yīng)是例如，原來的自然順序應(yīng)是 x(1)x(1)的地方，現(xiàn)在放著的地方，現(xiàn)在放著 x(4)x(4)，用二進(jìn)制碼表示這一規(guī)律時(shí)，用二進(jìn)制碼表示這一規(guī)律時(shí)， 則是在則是在 x x（0 0 10 0 1）處放著）處放著 x x（1 0 01 0 0），）， x x（0 1 10 1 1）

14、處放著）處放著 x x（1 1 01 1 0）。）。2728x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n029303210,310,20,1222/24/，時(shí)，時(shí)，時(shí)，JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLLpNWpNW12L31對(duì) 的一般情況，第L級(jí)的旋轉(zhuǎn)因子為MN212 , 2 , 1 , 0,222212 , 2 , 1 , 0,12J212MLJNNpNMLMLMLLJpNJWWWNJWWLMLLLMJp2從而可以確定第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。32FFT算法

15、流圖33343536JN/2？JN/4輸入當(dāng)前倒序數(shù)十進(jìn)制數(shù)值JNYNY2NJ 22NJ JN/2MNYMNJ2 結(jié)束J=J-N/2倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律37存儲(chǔ)單元自然順序輸入變址倒位序A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)x(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)N=8 倒位序的變址處理 分析上圖N=8點(diǎn)倒序規(guī)律，順序數(shù)I與倒序數(shù)J 存在關(guān)系： I = J時(shí)，不交換； I J時(shí)，不交換，直接更新序數(shù)值；38LH=N/2J=LHN1=N-2I=1,N1I JT=A(I)A(I)=A

16、(J)A(J)=TK=LHJKJ=J+KJ=J-KK=K/2NN YY計(jì)算倒序值的程序流圖3940仍設(shè)序列點(diǎn)數(shù)為N=2M，M為正整數(shù)。將X(k)按k的奇偶分組之前，先將輸入序列按前一半、后一半分開。nkNNnNkNkNnNNnnkNNnNNnnkNNnnkNNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX1202/212012012101202)(2)()()()()(k=0, 1, , N-1 41nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 按k的奇偶可將X(k)分為兩部分: 12, 1 , 0NrXrx nx nNWx nx nNWnNNr

17、nnNNrn() ( )(/ )( )(/ )/22202 1202 12rnNnNNnnrNNnWWNnxnxWNnxnxrX2/12/0)12(12/0)2/()()2/()() 12(42nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr12/02/212/02/1)() 12()()2(NnnrNNnnrNWnxrXWnxrX令則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)算流圖符號(hào)43X (3)N/2點(diǎn)DFTN/2點(diǎn)DFTx(0)x(1)x(2)x(3)x(4)x(5)

18、x(6)x(7)x1(0)x1(1)x1(2)x1(3)x2(0)x2(1)x2(2)x2(3)WN0WN1WN2WN3X (0)X (2)X (4)X (6)X (1)X (5)X (7)N=8時(shí)第1次分解的運(yùn)算流圖4445x(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)WN0WN2WN0WN2WN0WN0WN0WN04647FFT的變形運(yùn)算流圖4849jWNN410