數(shù)字信號(hào)處理教案第4章ppt課件

1、第四章第四章 快速傅立葉變換快速傅立葉變換（FFT） Fast Fourier Transform 數(shù)字信號(hào)處理 4.1 引言 DFT 是數(shù)字信號(hào)處理的基礎(chǔ)，是 一種重要變換。 快速算法的引出，使數(shù)字信號(hào)處 理技術(shù)得到廣泛應(yīng)用。 各種快速算法不斷被采用T)(txa)( txaDA/)(nx)(nxDFT)()(fXkXa數(shù)字計(jì)算機(jī)N足夠大.1.1 DFT提供了計(jì)算機(jī)處理的可能性 模擬信號(hào)的頻譜分析 4.1.2 DFT的運(yùn)算量 10)()()(NnnkNWnxnxDFTkXk=0,1,2,N1計(jì)算機(jī)運(yùn)算時(shí)： 0k0) 1(0100) 1() 1 () 0() 0(NNNNWNxWxWxX1k 0

2、111(1)1(1)(0)(1)(1)NNNNXxWxWx NW 2k 0212(1) 2(2)(0)(1)(1)NNNNXxWxWx NW 1Nk0111(1)1(1)(0)(1)(1)NNNNNNNX NxWx Wx NW N項(xiàng) N個(gè) 計(jì)算一個(gè) N點(diǎn)DFT ，共需 次復(fù)乘。2N以做一次復(fù)乘1s計(jì)，若N =4096，所需時(shí)間為由于計(jì)算量大，且要求相當(dāng)大的內(nèi)存，難以實(shí)現(xiàn)實(shí)時(shí)處理，限制了DFT的應(yīng)用。s16777216)4096(2s17 長(zhǎng)期以來(lái)，人們一直在尋求一種能提高DFT運(yùn)算速度的方法。FFT便是Cooley&Tukey 在1965 年提出的的快速算法，它可以使運(yùn)算速度提高幾百倍

3、，從而使數(shù)字信號(hào)處理學(xué)科成為一個(gè)新興的應(yīng)用學(xué)科。4.1.3 FFT算法的設(shè)計(jì)思想 1利用nkNW的特點(diǎn)NjNeW2具有 1周期性 kNnNnkNWW)( )(NknNW2共軛性 knNNnkNWW)()(3對(duì)稱(chēng)性 kNNkNWW)2(4恒等性122NNNNWW5可約性nNnNWW22ReImj8N0NW1NW2NW3NW4NW5NW6NW7NW)(kNnNW2把N 點(diǎn)DFT化為幾組點(diǎn)數(shù)較少的DFT運(yùn)算 N點(diǎn)DFT運(yùn)算的復(fù)乘次數(shù)為2N次，若將N點(diǎn)DFT化為2 組，則復(fù)乘次數(shù)約為22222NN次。4.2 基基 2 抽取抽取FFT 算法算法（the Decimation-In-Time Radix-

4、2 FFT Algorithm）FFT分為兩大類(lèi)：分為兩大類(lèi)：時(shí)域抽取時(shí)域抽取FFT（Decimation-In-Time FFT，簡(jiǎn)稱(chēng)，簡(jiǎn)稱(chēng)DIT-FFT）頻域抽取頻域抽取FFT（Decimation-In-Frequency FFT， 簡(jiǎn)稱(chēng)簡(jiǎn)稱(chēng)DIF-FFT） 4.2.1 直接計(jì)算直接計(jì)算DFT的問(wèn)題及改進(jìn)的問(wèn)題及改進(jìn)的途徑的途徑 k=0, 1, , N-110)()(NnknNWnxkX10)(1)(NkknNWkXNnxn=0, 1, , N-1DFT及及IDFT的定義的定義可見(jiàn)，可見(jiàn)，DFT 與與 IDFT 的計(jì)算成本基本相同。的計(jì)算成本基本相同。直接計(jì)算直接計(jì)算N點(diǎn)點(diǎn)DFT 時(shí)：時(shí)

5、：對(duì)應(yīng)一個(gè)對(duì)應(yīng)一個(gè)k需要需要N次復(fù)數(shù)乘和次復(fù)數(shù)乘和N-1次次復(fù)數(shù)加；對(duì)所有復(fù)數(shù)加；對(duì)所有N個(gè)個(gè)k值，則需要值，則需要 N復(fù)數(shù)乘和復(fù)數(shù)乘和N (N-1)次復(fù)數(shù)加次復(fù)數(shù)加 。其中其中:一次復(fù)數(shù)乘需要一次復(fù)數(shù)乘需要4次實(shí)數(shù)乘和次實(shí)數(shù)乘和2次實(shí)數(shù)加方能次實(shí)數(shù)加方能完成。當(dāng)完成。當(dāng)N較大時(shí)，運(yùn)算量很大。較大時(shí)，運(yùn)算量很大。 例如：當(dāng)例如：當(dāng)N=8時(shí)，時(shí)，DFT需要需要64次復(fù)數(shù)乘；次復(fù)數(shù)乘；當(dāng)當(dāng)N=1024時(shí)，時(shí)，DFT所需復(fù)數(shù)乘為所需復(fù)數(shù)乘為1048576次，即一百多萬(wàn)次復(fù)數(shù)乘。次，即一百多萬(wàn)次復(fù)數(shù)乘。為了減少運(yùn)算次數(shù)，改進(jìn)計(jì)算的方法：為了減少運(yùn)算次數(shù)，改進(jìn)計(jì)算的方法：1利用旋轉(zhuǎn)因子的對(duì)稱(chēng)性、周期性和

6、可約性；利用旋轉(zhuǎn)因子的對(duì)稱(chēng)性、周期性和可約性； 旋轉(zhuǎn)因子旋轉(zhuǎn)因子（twiddle factor）2使長(zhǎng)序列變短。使長(zhǎng)序列變短。NjNeW/24.2.2 基基2時(shí)域抽取法原理時(shí)域抽取法原理 （庫(kù)利（庫(kù)利-圖基算法）圖基算法）設(shè)序列設(shè)序列xn的長(zhǎng)度為的長(zhǎng)度為N，且，且M為自然數(shù)為自然數(shù)N-point DFT,N is evenMN2)(log2NM 1,.,1 , 0,)()(10NkWnxkXNnknN將其一分為二，分成偶數(shù)和奇數(shù)序列項(xiàng)將其一分為二，分成偶數(shù)和奇數(shù)序列項(xiàng)（the even-indexed and odd-indexed terms）則則N/2點(diǎn)的序列為：點(diǎn)的序列為： even:

7、x1(r)=x(2r) , r=0, 1, , N/2-1 odd: x2(r)=x(2r+1) , r=0, 1, , N/2-1偶數(shù)序列偶數(shù)序列 the range: 02nN-2 (N is even) 0n(N/2)-1奇數(shù)序列奇數(shù)序列 the range: 12n+1N-1 (N is even) 02nN-2 0n(N/2)-1 奇數(shù)偶數(shù)nknNnknNWnxWnxkX)()()(120)12(120)2() 12()2(NrrkNNrrkNWrxWrx1202212021)()(NrkrNkNNrkrNWrxWWrx則則xn的的DFT：由于由于所以所以krNkrNjkrNjkrN

8、WeeW2/2/2222/2 1/2 112/2/20012( )( )( )( )( )NNkrkkrNNNrrkNX kx r WWx r WX kW Xkk=0,1,N-1n上式說(shuō)明,按n的奇偶性將 分解為兩個(gè)N/2長(zhǎng)的序列 和 ,則N點(diǎn)DFT可分解為兩個(gè)N/2點(diǎn)的DFT來(lái)計(jì)算.)(nx)(1nx)(2nx 其中其中 N/2-point DFT: k=0,1,N/2-1 )()()(112/02/11rxDFTWrxkXNrkrN12/022/22)()()(NrkrNrxDFTWrxkXk=0,1,N/2-1因此，可寫(xiě)出兩個(gè)因此，可寫(xiě)出兩個(gè)N/2點(diǎn)的方程點(diǎn)的方程:)()()(21kXW

9、kXkXkN)2()2()2(2)2(1NkXWNkXNkXNkN12,.,1 ,0Nk 而120)2(2)()2(11NrrNkNWrxNkXkNNkNWW222)()()2(1112021kXWrxNkXNrkrN同理同理而而1222jNNjNNeeW)()2(22kXNkX所以所以)()()2()()()(2121kXWkXNkXkXWkXkXkNkN12,.1 , 0Nk表示上述算法可用蝶形結(jié)（表示上述算法可用蝶形結(jié)（ butterfly）kNW)()(21kXWkXkN)()(21kXWkXkN Example : 如N=4 x(n)=x0, x1, x2, x3 even: x0,

10、 x2 even: x0 odd: x2 odd: x1, x3 even: x1 odd: x3 bit reversal/shuffling process x x0 0 x x2 2x x1 1x x3 3x x0 0 x x2 2x x1 1x x2 2x x0 0 x x1 1x x2 2x x3 3混序或反混序或反序序碼位倒置碼位倒置分成四個(gè)分成四個(gè)1點(diǎn)的序列點(diǎn)的序列 the butterfly蝶形運(yùn)算）04W14W02W02W1點(diǎn)序列的點(diǎn)序列的DFT就是序列本身，即不用計(jì)算就是序列本身，即不用計(jì)算 -1-1-1-1 如N4，那么將將 x1(r) 再按再按r的奇偶進(jìn)一步分解成兩個(gè)的

11、奇偶進(jìn)一步分解成兩個(gè)N/4點(diǎn)長(zhǎng)的子序列：點(diǎn)長(zhǎng)的子序列：) 12()()2()(1413lxlxlxlx14,.,1 , 0Nl14/0)12(2/114/022/11) 12()2()(NllkNNlklNWlxWlxkX12,.,1 , 0Nk)()(42/3kXWkXkN14/04/42/14/04/3)()(NlklNkNNlklNWlxWWlx 其中)()()(314/04/33lxDFTWlxkXNlklN)()()(414/04/44lxDFTWlxkXNlklN14,.,1 , 0Nk由由X3k和和X4k的周期性和的周期性和 的對(duì)稱(chēng)性，得的對(duì)稱(chēng)性，得kNNkNWW2/4/2/)(

12、)()4()()()(42/3142/31kXWkXNkXkXWkXkXkNkN14,.,1 , 0Nk同理，得同理，得)()()4()()()(62/5262/52kXWkXNkXkXWkXkXkNkN14,.,1 , 0Nk 其中) 12()()2()(2625lxlxlxlx)()()(514/04/55lxDFTWlXkXNlklN)()()(614/04/66lxDFTWlXkXNlklN 8點(diǎn)DIT-FFT運(yùn)算流圖x(0)x(0)x(4)x(4)x(2)x(2)x(6)x(6)x(1)x(1)x(5)x(5)x(3)x(3)x(7)x(7)X X3 3(0)(0)X X3 3(1)

13、(1)X X4 4(0)(0)X X4 4(1)(1)X X5 5(0)(0)X X5 5(1)(1)X X6 6(0)(0)X X6 6(1)(1)X X1 1(0)(0)X X1 1(1)(1)X X1 1(2)(2)X X1 1(3)(3)X X2 2(0)(0)X X2 2(1)(1)X X2 2(2)(2)X X2 2(3)(3)X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)02W02W02W02W04W04W14W14W08W28W18W38W 4.2.3 IDFT的高效算法10)(1)()(Nkkn

14、NWkXNkXIDFTnx這樣這樣IFFT可與可與FFT用同一子程序?qū)崿F(xiàn)。用同一子程序?qū)崿F(xiàn)。*10*)(1NkknNWkXN*)(1kXDFTNIDFT的運(yùn)算規(guī)律的運(yùn)算規(guī)律X*(0)X*(0)X*(4)X*(4)X*(2)X*(2)X*(6)X*(6)X*(1)X*(1)X*(5)X*(5)X*(3)X*(3)X*(7)X*(7)x x3 3(0)(0)x x3 3(1)(1)x x4 4(0)(0)x x4 4(1)(1)x x5 5(0)(0)x x5 5(1)(1)x x6 6(0)(0)x x6 6(1)(1)x x1 1(0)(0)x x1 1(1)(1)x x1 1(2)(2)x

15、x1 1(3)(3)x x2 2(0)(0)x x2 2(1)(1)x x2 2(2)(2)x x2 2(3)(3)x(0)*x(0)*x(1)*x(1)*x(2)*x(2)*x(3)*x(3)*x(4)*x(4)*x(5)*x(5)*x(6)*x(6)*x(7)*x(7)*02W02W02W02W04W04W14W14W08W28W18W38W1/N 求求IFFT，也可用，也可用DIT-FFT的流程來(lái)實(shí)現(xiàn)。的流程來(lái)實(shí)現(xiàn)。x(0)x(0)x(4)x(4)x(2)x(2)x(6)x(6)x(1)x(1)x(5)x(5)x(3)x(3)x(7)x(7)X(0)X(0)X(1)X(1)X(2)X(2

16、)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)0NW1NW2NW3NW0NW0NW0NW0NW0NW0NW2NW2NW1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N1/N Example:Determine the x(n) by IDFT.X=5, -1, 1, -1 Solution: n=0,1,2,3*304*)(41)(1)(kknkXWXDFTNnx1)(41)(41)0(3210*3004XXXXXWxkk1)15(41)(41) 1 (*304jjXWxkkk2)(41)2(30*24kkkXWx

17、所以 x(n)=1, 1, 2, 1 1)(41)3(*3034kkkXWx%the program in MATLAB: X=input(Please input X=); N=length(X); x=fft(conj(X),N); x=conj(x/N) Example :用用FFT算法計(jì)算下面信號(hào)的算法計(jì)算下面信號(hào)的 8點(diǎn)點(diǎn)DFT； x(n)=4 3 2 0 1 2 3 1 然后，再用然后，再用 IFFT恢復(fù)原信號(hào)?；謴?fù)原信號(hào)。 solution:4 4-3-32 20 0-1-1-2-23 31 14 42 2-1-13 3-3-30 0-2-21 14 4-1-12 23 3-3-

18、3-2-20 01 13 35 55 5-1-1-5-5-1-11 1-1-11 1-j-j1 1-j-j8 85+j5+j-2-25-j5-j-4-4-1+j-1+j-6-6-1-j-1-j1 1(1-j)/(1-j)/-j-j-(1+j)/-(1+j)/4 45+j+j5+j+j-2+j6-2+j65-j+j5-j+j12125+j-j5+j-j-2-j6-2-j65-j-j5-j-jshufflingshufflingDFT mergingDFT mergingX X0 0X X1 1X X2 2X X3 3X X4 4X X5 5X X6 6X X7 7 2 2 2 2 2 2 IFF

19、T(X)=1/NFFT(X*)*4 45 5- -j j- -j j- -2 2- -j j6 65 5+ +j j- -j j1 12 25 5- -j j+ +j j- -2 2+ +j j6 65 5+ +j j+ +j js sh hu uf ff fl li in ng gD DF FT T m me er rg gi in ng g4 4- -2 2- -j j6 61 12 2- -2 2+ +j j6 65 5- -j j- -j j5 5+ +j j- -j j5 5- -j j+ +j j5 5+ +j j+ +j j4 41 12 2- -2 2- -j j6 6- -2

20、 2+ +j j6 65 5- -j j- -j j5 5- -j j+ +j j5 5+ +j j- -j j5 5+ +j j+ +j j1 16 6- -8 8- -4 4- -1 12 2j j1 10 0- -j j2 2- -j j2 21 10 0+ +j j2 2- -j j2 21 12 2- -2 20 02 20 04 42 20 0- -2 2 ( (1 1+ +j j) )- -4 4j j2 2 ( (1 1- -j j) )3 32 2- -2 24 41 16 60 0- -8 8- -1 16 62 24 48 8 2 2 2 2 2 2 2 2 2 2 2

21、2 2 2 2 204W04W14W14W08W18W28W38W乘以1/N=1/8得原序列 4.2.4 FFT的計(jì)算成本最簡(jiǎn)單的最簡(jiǎn)單的FFT 是是Cooley-Tukey法法由于由于NMNM2log2N點(diǎn)點(diǎn)DFT有有M級(jí)蝶形運(yùn)算，每一級(jí)都有級(jí)蝶形運(yùn)算，每一級(jí)都有N/2個(gè)個(gè)蝶形運(yùn)算結(jié)構(gòu)；蝶形運(yùn)算結(jié)構(gòu)；每個(gè)蝶形運(yùn)算結(jié)構(gòu)都有每個(gè)蝶形運(yùn)算結(jié)構(gòu)都有1次復(fù)數(shù)乘和次復(fù)數(shù)乘和2次復(fù)數(shù)次復(fù)數(shù)加；加； 8442222111111118-DFT8-DFT4-DFT4-DFT2-DFT2-DFT1-DFT1-DFTstage 1stage 1stage 2stage 2stage 3stage 3所以，所以，M級(jí)

22、蝶形運(yùn)算有復(fù)數(shù)乘級(jí)蝶形運(yùn)算有復(fù)數(shù)乘M級(jí)蝶形運(yùn)算有復(fù)數(shù)加級(jí)蝶形運(yùn)算有復(fù)數(shù)加NNMNCM2log22)2(NNMNCA2log)2(直接直接DFT的復(fù)數(shù)乘和復(fù)數(shù)加均近似為的復(fù)數(shù)乘和復(fù)數(shù)加均近似為 。當(dāng)。當(dāng)N1時(shí)，時(shí)，所以所以DIT-FFT大大減少了運(yùn)算次數(shù)。大大減少了運(yùn)算次數(shù)。NNN22log)2(2N Example : for N=8 Solution : M= =3 stages三級(jí)）三級(jí)） for FFT, the total cost is （FFT的總計(jì)算成本是）的總計(jì)算成本是） MN/2=38/2=12 complex multiplications （復(fù)數(shù)乘）（復(fù)數(shù)乘）8log2

23、for directly DFT, the total cost is（直接計(jì)算DFT的成本是） N=8=64 (complex multiplications) The ratio is: （比值是） 實(shí)際上，當(dāng)N=2048時(shí)，直接運(yùn)算與 FFT算法的計(jì)算量之比為372.433. 51264 4.2.5 DIT-FFT的運(yùn)算規(guī)律及編程思想1、原位運(yùn)算：、原位運(yùn)算：利用同一單元存儲(chǔ)蝶形計(jì)算的輸入、輸出利用同一單元存儲(chǔ)蝶形計(jì)算的輸入、輸出數(shù)據(jù)。數(shù)據(jù)。每個(gè)蝶形的輸入和輸出均為相同位數(shù)。每個(gè)蝶形的輸入和輸出均為相同位數(shù)。原位運(yùn)算可節(jié)省大量?jī)?nèi)存，因而硬件成本低。原位運(yùn)算可節(jié)省大量?jī)?nèi)存，因而硬件成本低。

24、2、旋轉(zhuǎn)因子的變化規(guī)律：、旋轉(zhuǎn)因子的變化規(guī)律： N點(diǎn)點(diǎn)DFT，共有，共有M級(jí)蝶形運(yùn)算，每級(jí)有級(jí)蝶形運(yùn)算，每級(jí)有N/2個(gè)蝶形。個(gè)蝶形。 稱(chēng)為旋轉(zhuǎn)因子，p稱(chēng)為旋轉(zhuǎn)因子的指數(shù)。 為了編寫(xiě)程序，應(yīng)找出旋轉(zhuǎn)因子 與運(yùn)算 級(jí)數(shù)的關(guān)系。 設(shè)L=1，2，M，表示從左到右的運(yùn)算 級(jí)數(shù)，第L級(jí)有 個(gè)不同的旋轉(zhuǎn)因子，pNW12LpNW對(duì)于對(duì)于 ，各級(jí)的旋轉(zhuǎn)因子表示為，各級(jí)的旋轉(zhuǎn)因子表示為L(zhǎng)=1時(shí)，時(shí)，L=2時(shí)，時(shí)，L=3時(shí)，時(shí)，823N0,24/JWWWJJNpNL1 , 0,22/JWWWJJNpNL3 , 2 , 1 , 0,2JWWWJJNpNL對(duì)于對(duì)于 的一般情況，第的一般情況，第L級(jí)的旋轉(zhuǎn)因子為級(jí)的旋轉(zhuǎn)因

25、子為MN2JpNLWW212,.,2 , 1 , 01LJ，由于由于MLMLMLN2222所以所以通過(guò)上式，可以計(jì)算第通過(guò)上式，可以計(jì)算第L級(jí)運(yùn)算的旋轉(zhuǎn)因子。級(jí)運(yùn)算的旋轉(zhuǎn)因子。LMMLJNJNpNWWW2212,.,1 , 01LJLMJp2 3、蝶形運(yùn)算規(guī)律設(shè)序列設(shè)序列xn經(jīng)過(guò)時(shí)域倒序存入數(shù)組經(jīng)過(guò)時(shí)域倒序存入數(shù)組X如蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距如蝶形運(yùn)算的兩個(gè)輸入數(shù)據(jù)相距B個(gè)點(diǎn)，個(gè)點(diǎn)，應(yīng)用原位運(yùn)算，可得：應(yīng)用原位運(yùn)算，可得：pNLLLpNLLLWBJXJXBJXWBJXJXJX)()()()()()(1111MLJJpLLM,.,1; 12,.,1 , 0;21 4、編程思想及程序框圖其它運(yùn)算

26、規(guī)律：其它運(yùn)算規(guī)律：第第L級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距級(jí)中，每個(gè)蝶形的兩個(gè)輸入數(shù)據(jù)相距 個(gè)點(diǎn)；個(gè)點(diǎn)；同一旋轉(zhuǎn)因子對(duì)應(yīng)著間隔為同一旋轉(zhuǎn)因子對(duì)應(yīng)著間隔為 點(diǎn)的點(diǎn)的 個(gè)蝶形對(duì)應(yīng)第幾組蝶形）個(gè)蝶形對(duì)應(yīng)第幾組蝶形）12LBLM2L2 8點(diǎn)DIT-FFT運(yùn)算流圖x(0)x(0)x(4)x(4)x(2)x(2)x(6)x(6)x(1)x(1)x(5)x(5)x(3)x(3)x(7)x(7)X X3 3(0)(0)X X3 3(1)(1)X X4 4(0)(0)X X4 4(1)(1)X X5 5(0)(0)X X5 5(1)(1)X X6 6(0)(0)X X6 6(1)(1)X X1 1(0)(0)X

27、 X1 1(1)(1)X X1 1(2)(2)X X1 1(3)(3)X X2 2(0)(0)X X2 2(1)(1)X X2 2(2)(2)X X2 2(3)(3)X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)02W02W02W02W04W04W14W14W08W28W18W38W編程的運(yùn)算方法：編程的運(yùn)算方法：從輸入端第從輸入端第1級(jí)開(kāi)場(chǎng)，逐級(jí)進(jìn)行，共級(jí)開(kāi)場(chǎng)，逐級(jí)進(jìn)行，共進(jìn)行進(jìn)行M級(jí)運(yùn)算。級(jí)運(yùn)算。在進(jìn)行第在進(jìn)行第L級(jí)運(yùn)算時(shí)，依次求出級(jí)運(yùn)算時(shí)，依次求出 個(gè)不同的個(gè)不同的旋轉(zhuǎn)因子，然后計(jì)算其對(duì)應(yīng)相同的旋轉(zhuǎn)因子的旋

28、轉(zhuǎn)因子，然后計(jì)算其對(duì)應(yīng)相同的旋轉(zhuǎn)因子的 個(gè)蝶形。個(gè)蝶形?？捎萌匮h(huán)程序?qū)崿F(xiàn)可用三重循環(huán)程序?qū)崿F(xiàn)DIT-FFT運(yùn)算。運(yùn)算。12LLM2(3)5、序列的倒置、序列的倒置bit reversal）倒序是有規(guī)律的。倒序是有規(guī)律的。由于由于 ，所以順序數(shù)可用，所以順序數(shù)可用M位二進(jìn)制位二進(jìn)制數(shù)（數(shù)（ ）表示。）表示。MN20121. nnnnMM用硬件電路和匯編語(yǔ)言程序產(chǎn)生倒序很容易，用硬件電路和匯編語(yǔ)言程序產(chǎn)生倒序很容易，用高級(jí)語(yǔ)言倒序的規(guī)律為：用高級(jí)語(yǔ)言倒序的規(guī)律為：倒序數(shù)是在倒序數(shù)是在M位二進(jìn)制數(shù)最高位加位二進(jìn)制數(shù)最高位加1，逢逢2向右進(jìn)位。向右進(jìn)位。4.2.6 頻率抽取法頻率抽取法FFT(DI

29、F-FFT)設(shè)序列設(shè)序列xn長(zhǎng)度為長(zhǎng)度為 ，將其前后，將其前后對(duì)半分開(kāi)，得：對(duì)半分開(kāi)，得：MN212/12/010)()()()()(NNnknNNnknNNnknNWnxWnxWnxnxDFTkX式中12/0)2/(12/0)2()(NnNnkNNnknNWNnxWnx奇數(shù)，偶數(shù)kkWkkNN1, 1) 1(2/knNkNNNnWNnxWnx)2()(2/12/0再將再將Xk分解成偶數(shù)組和奇數(shù)組分解成偶數(shù)組和奇數(shù)組 k為偶數(shù)時(shí)：為偶數(shù)時(shí)：/2 120/2 1/20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nWk為奇數(shù)時(shí)：為奇數(shù)時(shí)：rnNnNNnn

30、rNNnWWNnxnxWNnxnxrX2/12/0)12(12/0)2()()2()() 12(令令12,.,1 , 0,)2()()()2()()(21NnWNnxnxnxNnxnxnxnN得得12/02/212/02/1)() 12()()2(NnrnNNnrnNWnxrXWnxrX12,.,1 , 0Nr DIF-FFT蝶形運(yùn)算流圖x x(n)(n)x x(n+N/2)(n+N/2)x x1 1(n)=x(n)+x(N/2)(n)=x(n)+x(N/2)x x2 2(n)=x(n)-x(n+N/2)(n)=x(n)-x(n+N/2)nNWnNW-+N=8時(shí)，時(shí)，DIF-FFT蝶形運(yùn)算流圖蝶形運(yùn)算流圖x(0)x(0)x(4)x(4)x(2)x(2)x(6)x(6)x(1)x(1)x(5)x(5)x(3)x(3)x(7)x(7)X(0)X(0)X(1)X(1)X(2)X(2)X(3)X(3)X(4)X(4)X(5)X(5)X(6)X(6)X(7)X(7)0NW1NW2NW2NW2NW3NW0NW0NW0NW0NW0NW0NW留意：留意：DIT-FFT和和DIF-FFT的算法流圖不的算法流圖不 是唯一的。是唯一的。