《数字信号处理-时间抽取FFT算法》由会员分享，可在线阅读，更多相关《数字信号处理-时间抽取FFT算法（39页珍藏版）》请在金锄头文库上搜索。
1、离散傅里叶变换快速算法(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,解决问题的方法,将时域序列逐次分解为一组子序列，利用旋转因子的特性，由子
2、序列的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算法流图,
3、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算法流
4、图,时间抽取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。
5、,第一级的蝶形系数均为 ，蝶形节点的距离为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 x001 x101 x011 x111,自然顺序输入,倒序,变址,xk2k1k0,存储单元 数据不对换,存储单元 数据对换,原位运算(In-place Computat
6、ions),原位运算,x0 x4 x2 x6 x1 x5 x3 x7,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),输入序列,存储单元,第一级输出,第二级输入,第二级输出,第三级输入,X10 X11 X20 X21 X30 X31 X40 X41,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),X50 X51 X52 X53 X60 X61 X62 X63,A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8),X 0 X 1 X 2 X 3 X 4 X 5 X 6 X 7,A(1) A(2) A(3)
7、A(4) A(5) A(6) A(7) A(8),第三级输出,时间抽取FFT,例：已知xk=1,2,3,4，利用基2-FFT算法流图计算,1 3 2 4,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,
8、-1, -1,-1 X1m和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=1 x12=2 x11=1 x13=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=
9、-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=1
10、0, -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算法,，,
