资源描述：
《第6章快速傅立叶变换(FFT)ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第6章快速傅立叶变换(FFT)虽然频谱分析和DFT运算很重要，但在很长一段时间里，由于DFT运算复杂，并没有得到真正的运用，而频谱分析仍大多采用模拟信号滤波的方法解决，直到1965年首次提出DFT运算的一种快速算法以后，情况才发生了根本变化，人们开始认识到DFT运算的一些内在规律，从而很快地发展和完善了一套高速有效的运算方法——快速付里变换（FFT）算法。FFT的出现，使DFT的运算大大简化，运算时间缩短一～二个数量级，使DFT的运算在实际中得到广泛应用。6.1引言一.DFT的计算工作量两者的差别仅在指数的符号和因子1/N.通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘
2、法运算,和次复数加法运算.那么,计算全部N点的X(k)就要N2次复数乘法运算,N(N-1)次复数加法运算.一般来说,乘法运算要比相加运算复杂,为讨论简单起见,我们以复数乘法运算次数近似作为运算工作量的衡量标准.当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算.这样,难以做到实时处理.一个X(k)的值的工作量,如X(1)二.改进的途径1.的对称性和周期性得:对称性:周期性:利用上述特性,可以将有些项合并把N点数据分成两半：其运算量为：再分两半：+=+++=这样一直分下去，剩下两点的变换。2.把长度为N点的大点数的DFT运算依次分解为若干个小点数的D
3、FT。因为DFT的计算量正比于N2，N小，计算量也就小。FFT算法正是基于这样的基本思想发展起来的。1965年,库利(cooley)和图基(Tukey)首先提出FFT算法.对于N点DFT,仅需(N/2)log2N次复数乘法运算.例如N=1024=210时，需要(1024/2)log2210=512*10=5120次。5120/1048576=4.88%,速度提高20倍.应用第三代数字信号处理器TMS320C30-40，具有50ns的单周期执行时间，每秒20000次浮点运算，完成乘法、加法及运算控制、数据存取共需约1s左右，而采用FFT算法，计算时间可缩减为2.366ms。FFT有多种形
4、式，但基本上可分为两类：时间抽取法和频率抽取法。按“基数”分：基-2FFT算法；基-4FFT算法；混合基FFT算法；分裂基FFT算法其它方法：线性调频Z变换(CZT法)1.设输入序列长度为N=2L(L为正整数，将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。2.其中基数2----N=2L，L为整数.若不满足这个条件，可以人为地加上若干零值（加零补长）使其达到N=2L6.2按时间抽取(DIT)的FFT算法 —库利-图基算法算法原理(1).N/2点DFT1.先将按n的奇偶分为两组作DFT,这样有:n为偶数时:n为奇数时:
5、因此，由于:所以,上式可表示为:(n为偶数)(n为奇数)其中,2.两点结论:(1)X(k),X(k)均为N/2点的DFT。(2)X(k)=X(k)+WX(k)只能确定出X(k)的k=个；即前一半的结果。1212kN同理,这就是说,X1(k),X2(k)的后一半,分别等于其前一半的值。3.X(k)的后一半的确定由于（周期性）,所以:可见,X(k)的后一半，也完全由X1(k),X2(k)的前一半所确定。*N点的DFT可由两个N/2点的DFT来计算。又由于,所以实现上式运算的流图称作蝶形运算前一半4.蝶形运算后一半（N/2个蝶形)(前一半)(后一半)1111-1由X1(k)、X2(k)表示X
6、(k)的运算是一种特殊的运算-碟形运算X1(k)X2(k)作图要素：(1)左边两路为输入(2)右边两路为输出(3)中间以一个小圆表示加、减运算（右上路为相加输出、右下路为相减输出)(4)如果在某一支路上信号需要进行相乘运算，则在该支路上标以箭头，将相乘的系数标在箭头旁。(5)当支路上没有箭头及系数时，则该支路的传输比为1。(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:复乘次数:复加次数:(3)N/2个蝶形运算的运算量:复乘次数:复加次数:5.计算工作量分析复乘:复加:总共运算量:按奇、偶分组后的计算量：但是,N点DFT的复乘为N2;复加N(N-1)
7、;与分解后相比可知,计算工作点差不多减少一半。例如N=8时的DFT,可以分解为两个N/2=4点的DFT.具体方法如下:(1)n为偶数时,即分别记作:(2)n为奇数时,分别记作:x1(0)=x(0)x1(1)=x(2)N/2点x1(2)=x(4)DFTx1(3)=x(6)x2(0)=x(1)x2(1)=x(3)N/2点x2(2)=x(5)DFTx2(3)=x(7)~~X1(0)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)
