数字信号处理-时间抽取FF.ppt
数字信号处理(Digital Signal Processing),信号与系统系列课程组 国家电工电子教学基地,离散傅里叶变换快速算法(FFT),问题的提出解决问题的思路与方法 基2时间抽取FFT算法基2频率抽取FFT算法FFT算法的实际应用 实序列的DFT计算，IDFT的快速计算方法,时间抽取FFT,问题的提出,4点序列2，3，3，2 DFT的计算复杂度,复数加法,N(N-1),复数乘法,N 2,如何提高DFT的运算效率?,时间抽取FFT,解决问题的思路,1.将长序列DFT分解为短序列的DFT,2.利用旋转因子 的周期性、对称性、可约性。,旋转因子 的性质,(1)周期性,(2)对称性,(3)可约性,时间抽取FFT,解决问题的方法,将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子序列的DFT来实现整个序列的DFT。,基2时间抽取(Decimation in time)FFT算法,基2频率抽取(Decimation in frequency)FFT算法,时间抽取FFT,基2时间抽取FFT算法,基2时间抽取FFT算法推导基2时间抽取FFT算法流图基2时间抽取FFT算法的计算复杂度基2时间抽取FFT算法流图规律,时间抽取FFT,基2时间抽取FFT算法推导,时间抽取FFT,基2时间抽取FFT算法推导,因此有:,由于X1m 和X2m隐含有周期性，可得,时间抽取FFT,基2时间抽取FFT算法推导,基2时间抽取FFT算法的基本关系,时间抽取FFT,基2时间抽取FFT算法流图,N=2,xk=x0,x1,4点基2时间抽取FFT算法流图,X10,X11,X20,X21,-1,-1,-1,-1,X 0,X 1,X 2,X 3,4点基2时间抽取FFT算法流图,8点基2时间抽取FFT算法流图,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,X10,X11,X12,X13,X20,X21,X22,X23,X 0,X 1,X 2,X 3,X 4,X 5,X 6,X 7,-1,-1,-1,-1,8点基2时间抽取FFT算法流图,第一级,第二级,第三级,8点基2时间抽取FFT算法流图,时间抽取FFT,算法的计算复杂度,复乘次数,时间抽取FFT,计算速度的比较,N=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=%.6en,t2);fprintf(FFT/DFT=%.6f%n,t1*100/t2);stem(abs(y1-y2),r.);,基2时间抽取FFT算法流图,第一级,第二级,第三级,FFT算法流图旋转因子 规律,第二级的蝶形系数为，蝶形节点的距离为2。,第一级的蝶形系数均为，蝶形节点的距离为1。,第三级的蝶形系数为，蝶形节点的距离为4。,第M级的蝶形系数为，蝶形节点的距离为N/2。,倒 序运算(Bit-reverse Computations),倒序的实现变址,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8),存储单元,x000 x001 x010 x011 x100 x101 x110 x111,x000 x100 x010 x110 x001x101 x011 x111,自然顺序输入,倒序,变址,xk2k1k0,存储单元数据不对换,存储单元数据对换,原位运算(In-place Computations),原位运算,x0 x4x2x6x1x5x3x7,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8),输入序列,存储单元,第一级输出,第二级输入,第二级输出,第三级输入,X10X11X20X21X30X31X40X41,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8),X50X51X52X53X60X61X62X63,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8),X 0X 1X 2X 3X 4X 5X 6X 7,A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(8),第三级输出,时间抽取FFT,例：已知xk=1,2,3,4，利用基2-FFT算法流图计算,1324,4,6,-2,2 j,10,-2,-2+2j,-2-2j,DFTxk=,10,-2+2j,-2,-2-2j,例：试利用N=4基2时间抽取的FFT流图计算8点序列xk=1,-1,1,-1,2,-1,1,-1的DFT。,解：,根据基2时间抽取FFT算法原理，8点序列的DFT Xm可由两个4点序列的DFT X1m和X2m表达。如果按照序列xk序号的奇偶分解为x1k和 x2k，则存在,其中 x1k=1,1,2,1，x2k=-1,-1,-1,-1X1m和X2m可通过4点的FFT来计算。,例：试利用N=4基2时间抽取的FFT流图计算8点序列xk=1,-1,1,-1,2,-1,1,-1的DFT。,解：,x1k=1,1,2,1,3,-1,2,0,5,1,-1,-1,x10=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,0,X1m=5,-1,1,-1,X0=5+(-4)=1,X1=-1+0=-1,X2=1+0=1,X3=-1+0=-1,X4=5-(-4)=9,X5=-1-0=-1,X6=1-0=1,X7=-1-0=-1,Xm=1-1 1-1 9-1 1-1,时间抽取FFT,序列补零,序列插零的DFT,x1k=1,2,3,4,x2k=1,2,3,4,0,0,0,0,x3k=1,0,2,0,3,0,4,0,DFTx1k=10,-2+2j,-2,-2-2j,DFTx2k=10,-0.4142-7.2426j,-2+2j,2.4142-1.2426j,-2,2.4142+1.2426j,-2-2j,-0.4142-7.2426j,DFTx3k=10,-2+2j,-2,-2-2j,10,-2+2j,-2,-2-2j,基2时间抽取FFT算法的基本关系,基3时间抽取FFT算法的基本关系,基4时间抽取FFT算法的基本关系,任意基时间抽取FFT算法,基4时间抽取FFT算法,时间抽取FFT,基4时间抽取FFT算法推导,时间抽取FFT,基4时间抽取FFT算法推导,时间抽取FFT,基4时间抽取FFT算法流图,时间抽取FFT,算法的计算复杂度,基2时间抽取FFT复乘次数：,基4时间抽取FFT复乘次数：,时间抽取FFT,混合基时间抽取FFT算法,混合基时间抽取FFT算法推导 混合基时间抽取FFT算法流图,时间抽取FFT,混合基时间抽取FFT算法,若序列,的长度可表示为N=pq，将序列,按时间抽取方式分解为p个q点序列,则根据时间抽取FFT算法原理可得基p时间抽取FFT算法基本表示式为,分别为其DFT,时间抽取FFT,混合基时间抽取FFT算法,时间抽取FFT,混合基时间抽取FFT算法,，,时间抽取FFT,混合基时间抽取FFT算法,，,时间抽取FFT,混合基时间抽取FFT流图,，,
