ch3_1时间抽取FFT-北京交通大学陈后金教授信号处理课件

1、近代数字信号处理近代数字信号处理(Advanced Digital Signal Processing) 电子信息工程学院电子信息工程学院信号与图像处理研究室4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度1, 1 , 0,10NmWkxmXkmNNk10233200000 NNNNWWWWXj12332 1 3210 NNNNWWWWX0233226420 NNNNWWWWXj1233239630 NNNNWWWWXkmNW946434046444240434241404040404044WWWWWWWWWWWWWWWWDj1j11111j1j11111kmNWkmNNmkNmN

2、kNWWW)()(mkNkmNWWmkNNmkNWW2nmknNmkNWW为整数nNWWnmknNmkN/,/12, 1 , 0 122Nrrxrxkx 122mXmXmXkmNNkWkxmX10mrNNrrmNNrWrxWrx)12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122mrNNrmrNNrWrxmXWrxmX2/12/022/12/01 12 2记21mXWmXmXmN2/22/1NmXWNmXNmXNmN121 , 0Nm因此有因此有:21mXWmXmN由于X1m 和X2m隐含有周期性，可得mNNWmXWmXNmXmX11112/

3、2011j-1-j21mXWmXmXmN2/21mXWmXNmXmN 121 , 0 NmN=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx 1 01111 1 0 xxXXx0 x2x1x3X10X11X20X212点DFT2点DFT111104W14W02W02WX 0X 1X 2X 31 , 0,2241mmXWmXmXm1 , 0,241mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 71111

4、08W18W28W38W3 , 2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38WNN2log2复乘次数NN 2NN2log2N=1024*4;x = rand(N,1);tic; y1=fft(x); t1=toc; fprintf(nFFT time =%.6en,t1) ;tic; y2=dftmtx(N)*x; t2=toc;fprintf(DFT time

5、=%.6en,t2);fprintf(FFT/DFT =%.6f%n,t1*100/t2);stem(abs(y1-y2), r. ) ; PNW4/0,NNNWW0NW8/38/28/0,NNNNNNNWWWW) 12/(10,NNNNWWWx0 x4x2x6X0X2X1X3111108W08W08Wx1x5x3x7X4X6X5X7111108W08W08W18W08W38W28W28W28W1111倒倒 序运算序运算(Bit-reverse Computations)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)存储单元存储单元x000 x001 x010 x011 x1

6、00 x101 x110 x111x000 x100 x010 x110 x001x101 x011 x111自然顺序输入倒序变址变址xk2k1k0210kkkxkxkk 存储单元数据不对换kk 存储单元数据对换x0 x4x2x6X0X2X1X3111108W08W08Wx1x5x3x7X4X6X5X7111108W08W08W18W08W38W28W28W28W1111原位运算原位运算(In-place Computations)x0 x4x2x6x1x5x3x7A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8)输入序列 存储单元存储单元第一级输出第二级输入第二级输出第三级输入

7、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)第三级输出例：已知xk=1,2,3,4，利用基2-FFT算法流图计算DFTkxmX13244 622 j1022+2j22jDFTxk= 10, 2+2j,2,22j04W14Wx0 x3x1x2X3X1X2X01111试利用试利用N=4基基2时间抽取的时间抽取的

8、FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的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,-1X1m和和X2m可通过可通过4点的点的FFT来计算。来计算。-1-1j-1-1试利用试利用

9、N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 x1k=1, 1, 2, 13-12051-1-1x10=1x12=2x11=1x13=1 X1m=5,- 1, 1,- 1例：试利用例：试利用N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, -1, 1,-1的的DFT。 x2k=-1, -1, -1, -1 X2m=-4, 0,0,03, 2, 1 , 04281281 mmXWmXmXmXWmXmXmm X1m=5,- 1, 1,- 1X0=5+

10、(-4)=1X1= -1+0=-1X2= 1+0=1X3= -1+0=-1X4=5-(-4)=9X5=-1-0= -1X6=1-0= 1X7=-1-0= -1Xm= 1 -1 1 -1 9 -1 1 -1序列补零序列补零,序列插零的序列插零的DFTx1k=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,

11、 22j, 10, 2+2j, 2, 22j基基2时间抽取时间抽取FFT算法的基本关系算法的基本关系21mXWmXmXmN基基3时间抽取时间抽取FFT算法的基本关系算法的基本关系3221mXWmXWmXmXmNmN基基4时间抽取时间抽取FFT算法的基本关系算法的基本关系433221mXWmXWmXWmXmXmNmNmN任意基时间抽取FFT算法433221mXWmXWmXWmXmXmNmNmN jj4/3 4/2jj4/ 433221433221433221mXWmXWmXWmXNmXmXWmXWmXWmXNmXmXWmXWmXWmXNmXmNmNmNmNmNmNmNmNmNmNmNmNNWmX

12、WmXWmXWmXNmXNmXNmXmX3423201j1j11111j1j111114/34/24/1j-1-jmNmNmNNWmXWmXWmXWmXNmXNmXNmXmX3423201j1j11111j1j111114/34/24/ 32 1 0j1j11111j1j11111 32 1 0iiiiiiiixxxxXXXX0NWmNW2mNW3mNW 4 /1NmXmX2mX3mX4mXmX 4 / 2NmX 4 / 3NmX111111111111jjjjx0 x8x12x1x5x9x13x2x4x6x10 x14x3x7x11x15360246X0X2X3X4X5X6X7X8X1X9X10X11X12X13X14X15901230X4mX3mX1mX2m0000NN2log2NNNNMN24log83) 1(log43) 1(43kx,21kxkxkxp) 1(3221mXW