數(shù)字信號處理-第4章

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

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

3、抽取(DIT)(DIT)的基的基-2 FFT-2 FFT算法算法 設(shè)設(shè)MN2M M為自然數(shù)為自然數(shù)將長度為將長度為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時間抽取FFT算法流圖x0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT04W14W02W02WX

5、0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm151) 1 ()0() 1 (1) 1 ()0()0(12120202WxWxXWxWxX02W168點(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 ,122kNkNNXkXkWXkkNNXkXkW

6、Xkk 1212()()()0 , 1 ,12()()()0 , 1 ,122kNkNNXkXkWXkkNNXkXkWXkk N=8點(diǎn)的DIT-2FFT(時域抽取圖)一次分解圖17 (3)第二次分解：n 將x1(r)按r取奇、偶可分解成2個長度為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個長N/4的子序列 x5(l)= x2(2l) ， l=0,1,，N/4 x6(l) = x2(2l+1) ； 同理得l=0,1,，N/4-1；

7、X1 (k+N/2)=X3(k)WN/2kX4(k)， k=0,1,N/4-1；X1 (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；18N / 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

8、 點(diǎn)DFTN / 4 點(diǎn)DFTN / 4 點(diǎn)DFTX3(0)X3(1)X4(0)X4(1)X5(0)X5(1)X6(0)X6(1)WN/20WN/21WN/21WN/20N=8點(diǎn)DFT的二次時域抽取分解圖 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 ；19再次分解，對N=8點(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)

9、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級L=2L=3X (7)X3(0)X1(0)20) 1 ()0() 1 ()0() 1 () 1 ()0() 1 ()0()0(1202xWxxWxXxWxxWxXoNoN0NW218點(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)WN0WN1WN

10、2WN3X (0)X (1)X (2)X (3)X (4)X (5)X (6)WN0WN2WN0WN0WN0WN0 x(7)WN2WN0L=1級L=2L=3X (7)22基2 DIT-FFT算法n 由于這種方法每一步分解都是按輸入時間序列是屬于偶數(shù)還是奇數(shù)來抽取的，所以稱為“按時間抽取法”或“時間抽取法”。23整個運(yùn)算流圖中有M級蝶形，每一級運(yùn)算流圖中有N/2個蝶形，每個蝶形需一次復(fù)乘和兩次復(fù)數(shù)加運(yùn)算。2425（1）蝶形運(yùn)算）蝶形運(yùn)算（2）原位計(jì)算）原位計(jì)算 （3）序數(shù)重排）序數(shù)重排（4）蝶形類型隨迭代次數(shù)成倍增加）蝶形類型隨迭代次數(shù)成倍增加26（1）蝶形運(yùn)算）蝶形運(yùn)算對于對于N=2M，總是可

11、以通過，總是可以通過M次分解最后成為次分解最后成為2點(diǎn)的點(diǎn)的DFT運(yùn)算。這樣構(gòu)成從運(yùn)算。這樣構(gòu)成從x(n)到到X(k)的的M級運(yùn)算過程。級運(yùn)算過程。從上面的流圖可看到，每一級運(yùn)算都由從上面的流圖可看到，每一級運(yùn)算都由N/2個蝶形運(yùn)個蝶形運(yùn)算構(gòu)成。因此每一級運(yùn)算都需要算構(gòu)成。因此每一級運(yùn)算都需要N/2次復(fù)乘和次復(fù)乘和N次復(fù)次復(fù)加，這樣經(jīng)過時間抽取后加，這樣經(jīng)過時間抽取后M級運(yùn)算總共需要的運(yùn)算：級運(yùn)算總共需要的運(yùn)算： 復(fù)乘復(fù)乘 復(fù)加復(fù)加 而直接運(yùn)算時則與而直接運(yùn)算時則與N2 成正比。成正比。NNMN2log22NNMN2log27（2）原位計(jì)算）原位計(jì)算 n當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運(yùn)算的結(jié)

12、當(dāng)數(shù)據(jù)輸入到存儲器中以后，每一級運(yùn)算的結(jié)果仍然儲存在同一組存儲器中，直到最后輸出，果仍然儲存在同一組存儲器中，直到最后輸出，中間無需其它存儲器，這叫原位計(jì)算。中間無需其它存儲器，這叫原位計(jì)算。n每一級運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)每一級運(yùn)算均可在原位進(jìn)行，這種原位運(yùn)算結(jié)構(gòu)可節(jié)省存儲單元，降低設(shè)備成本，還可節(jié)省構(gòu)可節(jié)省存儲單元，降低設(shè)備成本，還可節(jié)省尋址的時間。尋址的時間。28（3 3）序數(shù)重排）序數(shù)重排n對按時間抽取對按時間抽取FFTFFT的原位運(yùn)算結(jié)構(gòu)，當(dāng)運(yùn)算完畢時，的原位運(yùn)算結(jié)構(gòu)，當(dāng)運(yùn)算完畢時，正好順序存放著正好順序存放著 x(0)x(0)， x(1)x(1)， x(2)x(2)， x

13、(7) x(7)，因此可直接按順序輸出，因此可直接按順序輸出，n但這種原位運(yùn)算的輸入但這種原位運(yùn)算的輸入 x x（n n）卻不能按這種自然順）卻不能按這種自然順序存入存儲單元中，而是按序存入存儲單元中，而是按x(0)x(0)，x(4)x(4)，x(2)x(2)，x(6)x(6)，x(7)x(7)的順序存入存儲單元，這種順序看起的順序存入存儲單元，這種順序看起來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示來相當(dāng)雜亂，然而它也是有規(guī)律的。當(dāng)用二進(jìn)制表示這個順序時，它正好是這個順序時，它正好是“碼位倒置碼位倒置”的順序。的順序。n例如，原來的自然順序應(yīng)是例如，原來的自然順序應(yīng)是 x(1)x(1)的地

14、方，現(xiàn)在放著的地方，現(xiàn)在放著 x(4)x(4)，用二進(jìn)制碼表示這一規(guī)律時，用二進(jìn)制碼表示這一規(guī)律時， 則是在則是在 x x（0 0 10 0 1）處放著）處放著 x x（1 0 01 0 0），）， x x（0 1 10 1 1）處放著）處放著 x x（1 1 01 1 0）。）。2930 x(000)x(100)x(010)x(110)010101x(001)x(101)x(011)x(111)01010101x(n2n1n0)n2n1n031323210,310,20,1222/24/，時，時，時，JWWWLJWWWLJWWWLJJNpNJJNpNJJNpNLLLpNWpNW12L33對

15、的一般情況，第L級的旋轉(zhuǎn)因子為MN212 , 2 , 1 , 0,222212 , 2 , 1 , 0,12J212MLJNNpNMLMLMLLJpNJWWWNJWWLMLLLMJp2從而可以確定第L級運(yùn)算的旋轉(zhuǎn)因子。34FFT算法流圖35363738JN/2？JN/4輸入當(dāng)前倒序數(shù)十進(jìn)制數(shù)值JNYNY2NJ 22NJ JN/2MNYMNJ2 結(jié)束J=J-N/2倒序數(shù)的十進(jìn)制運(yùn)算規(guī)律39存儲單元自然順序輸入變址倒位序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(

16、3)x(7)N=8 倒位序的變址處理 分析上圖N=8點(diǎn)倒序規(guī)律，順序數(shù)I與倒序數(shù)J 存在關(guān)系： I = J時，不交換； I J時，不交換，直接更新序數(shù)值；40LH=N/2J=LHN1=N-2I=1,N1I JT=A(I)A(I)=A(J)A(J)=TK=LHJKJ=J+KJ=J-KK=K/2NN YY計(jì)算倒序值的程序流圖4142仍設(shè)序列點(diǎn)數(shù)為N=2M，M為正整數(shù)。將X(k)按k的奇偶分組之前，先將輸入序列按前一半、后一半分開。nkNNnNkNkNnNNnnkNNnNNnnkNNnnkNNnnkNWWNnxnxWNnxWnxWnxWnxWnxkX1202/212012012101202)(2)(

17、)()()()(k=0, 1, , N-1 43nkNNnkWNnxnxkX1202) 1()()( k=0, 1, , N-1 按k的奇偶可將X(k)分為兩部分: 12, 1 , 0NrXrx nx nNWx nx nNWnNNrnnNNrn() ( )(/ )( )(/ )/22202 1202 12rnNnNNnnrNNnWWNnxnxWNnxnxrX2/12/0)12(12/0)2/()()2/()() 12(44nNWNnxnxnxNnxnxnx2)()(2)()(2112, 1 , 0Nr12/02/212/02/1)() 12()()2(NnnrNNnnrNWnxrXWnxrX令

18、則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)算流圖符號45X (3)N/2點(diǎn)DFTN/2點(diǎn)DFTx(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 (2)X (4)X (6)X (1)X (5)X (7)N=8時第1次分解的運(yùn)算流圖4647x(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)WN0WN2WN0WN2WN0WN0WN0WN04849