基2时域频域FFT算法课件.ppt
4 4点序列点序列22，3 3，3 3，2 DFT2 DFT的计算复杂度的计算复杂度1, 1 , 0,10NmWkxmXkmNNk10233200000NNNNWWWWXjWWWWXNNNN12332 1 32100233226420NNNNWWWWXjWWWWXNNNN1233239630如何提高DFT的运算效率?问题的提出 一般性11 , 0;10NmWkxmXkmNNkDFT:直接计算的计算量：N-1复数乘法 N对N个不同Xm复数加法 N(N-1)复数乘法N2对一固定的m复数加法如计算1024点DFT： 复数乘法次数： N2 =10242 = 220 = 1048576 解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性、对称性、可约性。kmNWkmNNmkNmNkNWWW)()(1)周期性(periodicity)2)复共轭对称性(complex conjugate)kmNmNkNmkNNWWW)()(3)当N是偶数时kmNmkNWW2/)2(2/NmNWmNWkmNW的性质的性质解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法12, 1 , 0 122Nrrxrxkx基2频率抽取(Decimation in frequency)FFT算法 122mXmXmX3.1 基2时域抽取FFT算法算法推导: N=2M时域抽取(Decimation in time)kmNNkWkxmX1012/, 1 , 0; 1 , 0;2Nrllrka1kx2lx21lxkxa+21lxkxa-1(一)算法原理 基本蝶形(butterfly)mrNNrrmNNrWrxWrxmX) 12(12/0212/0 122rmNNrmNrmNNrWrxWWrx2/12/02/12/0 122rmNNrrmNNrWrxmXWrxmX2/12/022/12/01 122记2/2/2/22/1NmXWNmXNmXNmN21mXWmXmN算法推导: N=2M时域抽取21mXWmXmXmN2/21mXWmXNmXmN12/1 , 0Nm例： 1 0,00, 0, 221xXxXmN 1 00 xxX 1 0 1 xxX0X 1 X-110 x 1 x2点FFT流图N=2基2时域FFT流图的推导N=4时域基2FFT流图的推导-1X2X3-12点DFT2点DFTx0 x3x1x2X004WX114W01X 1 1X02X 1 2X21mXWmXmXmN 2/21mXWmXNmXmN2点DFT04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1N=8基2时域FFT流图的推导08W18W28W38W4点DFT4点DFTX0X3X1X2X4X5X6X7x0 x6x2x4x1x3x5x7-1-1-1-121mXWmXmXmN 2/21mXWmXNmXmN12/1 , 0Nm08W18W28W38WX0X3X1X2X4X5X6X7x0 x6x4x2x1x5x3x704W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18点FFT流图第三级第一级第二级(二 ) 算法工作量a1kx2lx21lxkxa21lxkxa-1一个蝶形计算量： 复数乘法 1，复数加法 2复数乘法:N，NNM2log22复数加法：NNNM2log22N=2M时，分解级数为 M，每级蝶形数 N/2计算1024点复数乘法次数： DFT： N 2 =1024 2 = 220 = 1048576 ；FFT：5120log22NN(三) 流图规律1) 原位运算(In-place Computations)a1kx2lx21lxkxa21lxkxa-1优点：节省存储空间(三) 流图规律PNW第二级的蝶形系数为 ，蝶形节点的距离为2。4/0,NNNWW第一级的蝶形系数均为 ，蝶形节点的距离为1。0NW第三级的蝶形系数为 ，蝶形节点的距离为4。8/38/28/0,NNNNNNNWWWW第M级的蝶形系数为 ，蝶形节点的距离为N/2。) 12/(10,NNNNWWW2)FFT算法流图旋转因子 规律3)倒序规律k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x010 x11101010101试利用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来计算。解：-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。3.2 基2频域抽取FFT算法mkNNNkmkNNkWkxWkxmX12/12/0)2/(12/012/02/NkmNNkmkNNkWNkxWkxmkNmNkWNkxkx2/) 1(12/0频域奇偶分组rkNNkWNkxkxrX2/12/02/2rkNkNNkWWNkxkxrX2/12/02/ 1212/1 , 0Nr频域奇偶分组mkNmNkWNkxkxmX2/) 1(12/0当m=2r,或2r+1，得到：rkNNkWNkxkxrX2/12/02/2rkNkNNkWWNkxkxrX2/12/02/ 1212/1 , 0Nr基2频率抽取蝶形运算的信号流图kxk+N/2xk+N/2xkx-1kNWk+N/2xkxkNW基2频率抽取蝶形运算的信号流图 1kx2kxx3x7x2x6x1x5x0 x43NW-12NW-11NW-1-10NW4点DFT4点DFTX0X6X2X4X1X3X5X7基2频率抽取8点信号流图0NW1NW2NW3NW2 点DFT-1-1-1-1x0 x3x1x2x4x5x6x7X0X6X4X2X1X5X3X70NW2NW2NW0NW-1-1-1-12 点DFT2 点DFT2 点DFT基2频率抽取8点信号流图0NW1NW2NW3NW-1-1-1-1x0 x3x1x2x4x5x6x70NW2NW2NW0NWX0X6X4X2X1X5X3X70NW0NW0NW0NW-1-1-1-1-1-1-1-1基2频率抽取8点信号流图3.3 3.3 实序列的实序列的FFTFFT算法算法( (二二) )利用利用N N点复序列的点复序列的FFTFFT，计算，计算2N2N点实序列点实序列FFTFFT( (一一) )利用利用N N点复序列的点复序列的FFTFFT计算两个计算两个N N点实序列点实序列FFTFFT已知 x k, hk是实序列，构造N点复序列 yk= x k+j hk ?: kxDFT求 ? khDFT)(mYkjhkxky NmYkjhkxky)(* ( (一一) )利用利用N N点复序列的点复序列的FFTFFT计算两个计算两个N N点实序列点实序列FFTFFT )(21NmYmYmXkx )(21NmYmYmHkh j所以所以( (二二) )利用利用N N点复序列的点复序列的FFTFFT，计算，计算2N2N点实序列点实序列FFTFFT已知yk是2N点实序列，希望用一个N点FFT计算其DFT 时域抽取FFT 算法：2mHWmXmYmN 2mHWmXNmYmN 11 , 0Nm10,2Nkkykx10,12Nkkykh 3.4 IDFT3.4 IDFT的快速算法的快速算法mkNNkWkxkxDFTmX10mkNNmWmXNmXIDFTkx110 1110mXDFTNWmXNkxmkNNmIDFTIDFT的快速算法步骤的快速算法步骤mkNNmWmXNkx110步骤 (1) 将X m取共轭)2(mXDFTFFT流图计算用(3)对(2)中结果取共轭并除以NFFTkxmXmX N1 104WjW14x0 x3x1x2X3X1X2X0-1-1-1-1例：已知xk=1,2,3,4利用频域抽样流图， 计算)();(mXDFTkxDFTmX12344262j1022+2j22jDFTxk=10, 2+2j,2,22j利用频域基利用频域基2-FFT2-FFT流图计算流图计算DFTDFT22, 2,22,10jjmXmXDFTmXDFT4, 8, 12, 164, 16, 12, 8104WjW14x0 x3x1x2X3X1X2X0-1-1-1-1kxDFTDFT)(NkNx 利用利用FFTFFT流图计算流图计算IFFTIFFT22, 2,22,10jjmXM=4;N=51;n=-(N-1)/2:(N-1)/2;x=ones(1,M+1),zeros(1,N-2*M-1),ones(1,M);X=fft(x,N);subplot(2,1,1);stem(n,fftshift(x);ylabel(xn);xlabel(Time n);omega=2*pi/N*n;subplot(2,1,2);stem(omega,real(fftshift(X);ylabel(Xk);xlabel(Frequency(rad);hold;Matlab计算离散序列的频谱FFT Xm精品课件精品课件！精品课件精品课件！-25-20-15-10-5051015202500.20.40.60.81xnTime n-4-3-2-101234-50510XkFrequency(rad)
