ch3_1基2時(shí)間抽取FFT（課堂PPT）

1、.1數(shù)字信號(hào)處理數(shù)字信號(hào)處理 信號(hào)與系統(tǒng)系列課程組信號(hào)與系統(tǒng)系列課程組 國(guó)家電工電子教學(xué)基地國(guó)家電工電子教學(xué)基地234點(diǎn)序列點(diǎn)序列2，3，3，2 DFT的計(jì)算復(fù)雜度的計(jì)算復(fù)雜度1, 1 , 0,10NmWkxmXkmNNk10233200000 NNNNWWWWXj12332 1 3210 NNNNWWWWX0233226420 NNNNWWWWXj1233239630 NNNNWWWWX4 一般性11 , 0;10NmWkxmXkmNNkDFT:直接計(jì)算的計(jì)算量：復(fù)數(shù)乘法 N對(duì)N個(gè)不同Xm:復(fù)數(shù)加法 N(N-1) 復(fù)數(shù)乘法N2對(duì)一固定的m:復(fù)數(shù)加法 N-1如計(jì)算1024點(diǎn)DFT： 復(fù)數(shù)乘法次

2、數(shù)： N2 =10242 = 220 = 1048576 5kmNW946434046444240434241404040404044WWWWWWWWWWWWWWWWDj1j11111j1j111116kmNNmkNmNkNWWW)()(1)周期性(periodicity)(2)復(fù)共軛對(duì)稱性(complex conjugate)kmNmNkNmkNNWWW)()(3)當(dāng)N是偶數(shù)時(shí)kmNmkNWW2/)2(2/NmNWmNWkmNW旋轉(zhuǎn)因子 的性質(zhì)712, 1 , 0 122Nrrxrxkx 122mXmXmX83.1 基2時(shí)域抽取FFT算法9kmNNkWkxmX10mrNNrrmNNrWrxW

3、rx)12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122mrNNrmrNNrWrxmXWrxmX2/12/022/12/01 12 2記算法推導(dǎo): N=2M時(shí)域抽取(時(shí)域按奇偶分組)1021mXWmXmXmN+212+2 =+2 +2/ / / m NNX mNX mNWX mN121 , 0Nm因此有因此有:21mXWmXmXmN 2/21mXWmXNmXmN 121 , 0 Nm21mXWmXmN由于X1m 和X2m隱含有周期性，可得rmNNrrmNNrWrxmXWrxmX2/12/022/12/01 122其中可見X1m是xk偶分量的D

4、FT，X2m是xk奇分量的DFT.11N=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx12x0 x2x1x3X10X11X20X212點(diǎn)DFT2點(diǎn)DFT111104W14W02W02WX 0X 1X 2X 31 , 0,2241mmXWmXmXm1 , 0,241mmXWmXmXm132點(diǎn)DFT144點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3 , 2 , 1 , 0,4281mm

5、XWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm154點(diǎn)DFT4點(diǎn)DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W1617NN2log2復(fù)乘次數(shù)NN 2NN2log21819PNW4/0,NNNWW0NW8/38/28/0,NNNNNNNWWWW) 12/(10,NNNNWWW20 x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)輸入序列 存儲(chǔ)單元存儲(chǔ)單元第一級(jí)輸出第二級(jí)輸入第二級(jí)輸出第三級(jí)輸入X10X11X

6、20X21X30X31X40X41A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X50X51X52X53X60X61X62X63A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)X 0X 1X 2X 3X 4X 5X 6X 7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)第三級(jí)輸出21k0k1k2xk2 k1k0 x000 x100 x0100 01 10 01 1112 xk k0 xk2 k10 01 1x110 x001x101x011x1110 01 10 01 10 01 10 01 122A(1)A(2)A(3)A(4)A(5)A(

7、6)A(7)A(8)存儲(chǔ)單元存儲(chǔ)單元x000 x001 x010 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然順序輸入倒序變址變址xk2k1k0210kkkxkxkk 存儲(chǔ)單元數(shù)據(jù)不對(duì)換kk 存儲(chǔ)單元數(shù)據(jù)對(duì)換23例：已知xk=1,2,3,4，利用基2FFT算法流圖計(jì)算DFT;DFTmXkxmX13244 62-21022+2j22jDFTxk= 10, 2+2j,2,22j04W14Wx0 x3x1x2X3X1X2X0111124補(bǔ)零補(bǔ)零, ,插零序列的插零序列的DFTDFTx1k=1,2,3,4x2k=1,2

8、,3,4,0,0,0,0 x3k=1,0,2,0,3,0,4,0DFTx1k=10, 2+2j, 2, 22jDFTx2k=10, 0.41427.2426j, 2+2j, 2.41421.2426j, 2, 2.41421.2426j , 22j, 0.41427.2426jDFTx3k=10, 2+2j, 2, 22j, 10, 2+2j, 2, 22j25試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。解： 根據(jù)基2時(shí)間抽取FFT算法原理，8點(diǎn)序列的DFT Xm可由兩個(gè)4點(diǎn)序列的DFT X1m和X2m表達(dá)。如果按照序列xk序

9、號(hào)的奇偶分解為x1k和 x2k，則存在 3 , 2 , 1 , 04281281mmXWmXmXmXWmXmXmm 其中x1k=1, 1, 2, 1，x2k=-1, -1, 1, 2，X1m和X2m可通過4點(diǎn)的FFT來計(jì)算。26解：-1-1-1-j12115-11-13-120-1-1-1-1-j-11-121-2+3j1-2-3j0-21-3-1 X1m=5, -1, 1, -1, X2m=1, -2+3j, 1, -2-3j利用上述公式，可得序列利用上述公式，可得序列xk的的DFT Xm為為Xm=6, -0.293+3.535j, 1+j, -1.707 + 3.535j, 4, -1.7

10、07-3.535j, 1-j, -0.293-3.535j試?yán)肗=4基2時(shí)間抽取的FFT流圖計(jì)算8點(diǎn)序列xk=1, -1, 1, -1, 2, 1, 1, 2的DFT。2714/, 1 , 0, 3424 144Nrrxrxrxrxkx28kmNNkWkxmX10mrNNrmrNNrmrNNrrmNNrWrxWrxWrxWrx)34(14/0)24(14/0)14(14/0414/0 3424 144算法推導(dǎo): N=4M時(shí)域抽取mNrmNNrmNrmNNrmNrmNNrrmNNrWWrxWWrxWWrxWrx34/14/024/14/04/14/04/14/0)34()24() 14(429

11、令14,.,1 , 0,44/14/01NmWrxmXrmNNr14,.,1 , 0, 144/14/02NmWrxmXrmNNr14,.,1 , 0,244/14/03NmWrxmXrmNNr14,.,1 , 0,344/14/04NmWrxmXrmNNr14,.,1 , 0,433221NmmXWmXWmXWmXmXmNmNmN則有:3014,.,1 , 0,444444)4(33)4(2241NmNmXWNmXWNmXWNmXNmXNmNNmNNmN14,.,1 , 0,)() 1()(4X433221NmmXWjmXWmXWjmXNmmNmNmN即：jWWjWNNNNNN4/32/4/, 1,其中：3114,.,1 , 0,42424242424)42(33)42(22421NmNmXWNmXWNmXWNmXNmXNmNNmNNmN14,.,1 , 0,) 1() 1(42X433221NmmXWmXWmXWmXNmmNmNmN即：12/32/NNNNWW其中：3214,.,1 , 0,43434343434)43(33)43(22431NmNmXWNmXWNmXWNmXNmXNmNNmNNmN14,.,1 , 0,)() 1(43X433221NmmXWjmXWmXjWm