基时域频域FFT算法PPT讲稿.ppt
基时域频域FFT算法第1页，共33页，编辑于2022年，星期六4 4点序列点序列22，3 3，3 3，2 DFT2 DFT的计算复杂度的计算复杂度复数加法复数加法复数加法复数加法N N(N N-1)-1)复数乘法复数乘法复数乘法复数乘法N 2如何提高DFT的运算效率?问题的提出第2页，共33页，编辑于2022年，星期六 一般性DFT:直接计算的计算量：N-1复数乘法 N对N个不同Xm复数加法 N(N-1)复数乘法N2对一固定的m复数加法如计算1024点DFT：复数乘法次数：N2=10242=220=1048576 第3页，共33页，编辑于2022年，星期六解决问题的思路1.将长序列DFT分解为短序列的DFT2.利用旋转因子 的周期性、对称性、可约性。第4页，共33页，编辑于2022年，星期六1)周期性(periodicity)2)复共轭对称性(complex conjugate)3)当N是偶数时的性质的性质第5页，共33页，编辑于2022年，星期六解决问题的方法 将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。基2时间抽取(Decimation in time)FFT算法基2频率抽取(Decimation in frequency)FFT算法第6页，共33页，编辑于2022年，星期六3.1 基2时域抽取FFT算法算法推导:N=2M时域抽取(Decimation in time)a1kx2lx21lxkxa+21lxkxa-1(一)算法原理 基本蝶形(butterfly)第7页，共33页，编辑于2022年，星期六算法推导:N=2M时域抽取第8页，共33页，编辑于2022年，星期六例：0X 1 X-110 x 1 x2点FFT流图N=2基2时域FFT流图的推导第9页，共33页，编辑于2022年，星期六N=4时域基2FFT流图的推导-1X2X3-12点DFT2点DFTx0 x3x1x2X0X12点DFT04W14Wx0 x3x1x2X3X1X2X0-1-1-1-1第10页，共33页，编辑于2022年，星期六N=8基2时域FFT流图的推导08W18W28W38W4点DFT4点DFTX0X3X1X2X4X5X6X7x0 x6x2x4x1x3x5x7-1-1-1-1第11页，共33页，编辑于2022年，星期六08W18W28W38WX0X3X1X2X4X5X6X7x0 x6x4x2x1x5x3x704W14W04W14W-1-1-1-1-1-1-1-1-1-1-1-18点FFT流图第三级第一级第二级第12页，共33页，编辑于2022年，星期六(二)算法工作量a1kx2lx21lxkxa+21lxkxa-1一个蝶形计算量：复数乘法 1，复数加法 2复数乘法:N，NNM2log22=复数加法：N=2M时，分解级数为 M，每级蝶形数 N/2计算1024点复数乘法次数：DFT：N 2=1024 2=220=1048576；FFT：第13页，共33页，编辑于2022年，星期六(三)流图规律1)原位运算(In-place Computations)a1kx2lx21lxkxa+21lxkxa-1优点：节省存储空间第14页，共33页，编辑于2022年，星期六(三)流图规律第二级的蝶形系数为 ，蝶形节点的距离为2。第一级的蝶形系数均为 ，蝶形节点的距离为1。第三级的蝶形系数为 ，蝶形节点的距离为4。第M级的蝶形系数为 ，蝶形节点的距离为N/2。2)FFT算法流图旋转因子 规律第15页，共33页，编辑于2022年，星期六3)倒序规律k0k1k2xk2 k1k0 x000 x100 x0100101112 xk k0 xk2 k101x110 x001x101x010 x11101010101第16页，共33页，编辑于2022年，星期六例：例：试利用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，则存在 其中x1k=1,1,2,1，x2k=-1,-1,1,2，X1m和X2m可通过4点的FFT来计算。第17页，共33页，编辑于2022年，星期六解：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。第18页，共33页，编辑于2022年，星期六3.2 基2频域抽取FFT算法频域奇偶分组第19页，共33页，编辑于2022年，星期六频域奇偶分组当m=2r,或2r+1，得到：第20页，共33页，编辑于2022年，星期六基2频率抽取蝶形运算的信号流图基2频率抽取蝶形运算的信号流图 第21页，共33页，编辑于2022年，星期六x3x7x2x6x1x5x0 x43NW-12NW-11NW-1-10NW4点DFT4点DFTX0X6X2X4X1X3X5X7基2频率抽取8点信号流图第22页，共33页，编辑于2022年，星期六0NW1NW2NW3NW2 点DFT-1-1-1-1x0 x3x1x2x4x5x6x7X0X6X4X2X1X5X3X70NW2NW2NW0NW-1-1-1-12 点DFT2 点DFT2 点DFT基2频率抽取8点信号流图第23页，共33页，编辑于2022年，星期六基2频率抽取8点信号流图第24页，共33页，编辑于2022年，星期六3.3 3.3 实序列的实序列的FFTFFT算法算法(二二)利用利用N N点复序列的点复序列的FFTFFT，计算，计算2N2N点实序列点实序列FFTFFT(一一)利用利用N N点复序列的点复序列的FFTFFT计算两个计算两个N N点实序列点实序列FFTFFT第25页，共33页，编辑于2022年，星期六已知 x k,hk是实序列，构造N点复序列 yk=x k+j hk(一一)利用利用N N点复序列的点复序列的FFTFFT计算两个计算两个N N点实序列点实序列FFTFFT所以所以第26页，共33页，编辑于2022年，星期六(二二)利用利用N N点复序列的点复序列的FFTFFT，计算，计算2N2N点实序列点实序列FFTFFT已知yk是2N点实序列，希望用一个N点FFT计算其DFT 时域抽取FFT 算法：第27页，共33页，编辑于2022年，星期六3.4 IDFT3.4 IDFT的快速算法的快速算法第28页，共33页，编辑于2022年，星期六IDFTIDFT的快速算法步骤的快速算法步骤步骤 (1)将X m取共轭(3)对(2)中结果取共轭并除以N第29页，共33页，编辑于2022年，星期六例：已知xk=1,2,3,4利用频域抽样流图，计算12344-262j10-2-2+2j-2-2jDFTxk=10,-2+2j,-2,-2-2j利用频域基利用频域基2-FFT2-FFT流图计算流图计算DFTDFT第30页，共33页，编辑于2022年，星期六4,8,12,164,16,12,8利用利用FFTFFT流图计算流图计算IFFTIFFT第31页，共33页，编辑于2022年，星期六M=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第32页，共33页，编辑于2022年，星期六第33页，共33页，编辑于2022年，星期六
