ch31基2时间抽取FFT课堂PPT

.1数字信号处理数字信号处理 信号与系统系列课程组信号与系统系列课程组 国家电工电子教学基地国家电工电子教学基地234点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度1,1,0,10NmWkxmXkmNNk10233200000 NNNNWWWWXj12332 1 3210 NNNNWWWWX0233226420 NNNNWWWWXj1233239630 NNNNWWWWX4 一般性11,0;10NmWkxmXkmNNkDFT:直接计算的计算量：复数乘法 N对N个不同Xm:复数加法 N(N-1)复数乘法N2对一固定的m:复数加法 N-1如计算1024点DFT：复数乘法次数：N2=10242=220=1048576 5kmNW946434046444240434241404040404044WWWWWWWWWWWWWWWWDj1j11111j1j111116kmNNmkNmNkNWWW)()(1)周期性(periodicity)(2)复共轭对称性(complex conjugate)kmNmNkNmkNNWWW)()(3)当N是偶数时kmNmkNWW2/)2(2/NmNWmNWkmNW旋转因子 的性质712,1,0 122Nrrxrxkx 122mXmXmX83.1 基2时域抽取FFT算法9kmNNkWkxmX10mrNNrrmNNrWrxWrx)12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122mrNNrmrNNrWrxmXWrxmX2/12/022/12/01 12 2记算法推导:N=2M时域抽取(时域按奇偶分组)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偶分量的DFT，X2m是xk奇分量的DFT.11N=2xk=x0,x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx12x0 x2x1x3X10X11X20X212点DFT2点DFT111104W14W02W02WX 0X 1X 2X 31,0,2241mmXWmXmXm1,0,241mmXWmXmXm132点DFT144点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3,2,1,0,4281mmXWmXmXm3,2,1,0,281mmXWmXmXm154点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W1617NN2log2复乘次数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)输入序列 存储单元存储单元第一级输出第二级输入第二级输出第三级输入X10X11X20X21X30X31X40X41A(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)第三级输出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(6)A(7)A(8)存储单元存储单元x000 x001 x010 x011 x100 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然顺序输入倒序变址变址xk2k1k0210kkkxkxkk 存储单元数据不对换kk 存储单元数据对换23例：已知xk=1,2,3,4，利用基2FFT算法流图计算DFT;DFTmXkxmX13244 62-21022+2j22jDFTxk=10,2+2j,2,22j04W14Wx0 x3x1x2X3X1X2X0111124补零补零,插零序列的插零序列的DFTDFTx1k=1,2,3,4x2k=1,2,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试利用N=4基2时间抽取的FFT流图计算8点序列xk=1,-1,1,-1,2,1,1,2的DFT。解：根据基2时间抽取FFT算法原理，8点序列的DFT Xm可由两个4点序列的DFT X1m和X2m表达。如果按照序列xk序号的奇偶分解为x1k和 x2k，则存在 3,2,1,04281281mmXWmXmXmXWmXmXmm 其中x1k=1,1,2,1，x2k=-1,-1,1,2，X1m和X2m可通过4点的FFT来计算。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.707-3.535j,1-j,-0.293-3.535j试利用N=4基2时间抽取的FFT流图计算8点序列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算法推导:N=4M时域抽取mNrmNNrmNrmNNrmNrmNNrrmNNrWWrxWWrxWWrxWrx34/14/024/14/04/14/04/14/0)34()24()14(429令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(43X433221NmmXWjmXWmXjWmXNmmNmNmN即：jWWjWNNNNNN4/92/34/3,1,其中：33433221mXWmXWmXWmXmXmNmNmN)()1()(4X433221mXWjmXWmXWjmXNmmNmNmN)1()1(42X433221mXWmXWmXWmXNmmNmNmN)()1(43X433221mXWjmXWmXjWmXNmmNmNmN14,.,1,0Nm