ch3_1时间抽取FFT

1、4点序列点序列2，3，3，2 DFT的计算复杂度的计算复杂度1, 1 , 0,10NmWkxmXkmNNk10233200000NNNNWWWWXjWWWWXNNNN12332 1 32100233226420NNNNWWWWXjWWWWXNNNN1233239630kmNWkmNWkmNNmkNmNkNWWW)()(mkNkmNWWmkNNmkNWW2nmknNmkNWW为整数nNWWnmknNmkN/,/12, 1 , 0 122Nrrxrxkx 122mXmXmXkmNNkWkxmX10mrNNrrmNNrWrxWrx)12(12/0212/0 122rmNNrmNrmNNrWrxWWr

2、x2/12/02/12/0 122mrNNrmrNNrWrxmXWrxmX2/12/022/12/01 12 2记21mXWmXmXmN 2/21mXWmXNmXmN 12/1 , 0 Nm因此有因此有:N=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWxx0 x2x1x3X10X11X20X212点DFT2点DFT111104W14W02W02WX 0X 1X 2X 31 , 0,2241mmXWmXmXm1 , 0,241mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13

3、X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38W3 , 2 , 1 , 0,4281mmXWmXmXm3 , 2 , 1 , 0,281mmXWmXmXm4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7111108W18W28W38WNN2log2复乘次数NN 2NN2log2PNW4/0,NNNWW0NW8/38/28/0,NNNNNNNWWWW) 12/(10,NNNNWWWk0k1k2xk2 k1k0 x000 x100 x0100

4、 01 10 01 1112 xk k0 xk2 k10 01 1x110 x001x101x011x1110 01 10 01 10 01 10 01 1试利用试利用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来计算。来计算。试利用试利用N=4基基2时间抽取的时间抽取的FFT流图计算流图计算8点序列点序列xk=1, -1, 1, -1, 2, 1, 1, 2的的DFT。-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为为X