欢迎来到天天文库
浏览记录
ID:58701250
大小:1.01 MB
页数:130页
时间:2020-10-04
《第4章 快速付里叶变换FFTppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第四章快速付里叶变换主要内容1.FFT引入、快速计算思想和方案;2.基2-FFT的原理;3.其它类型FFT:混合基、分裂基和CZT;4.FFT的应用。一、FFT引入及快速计算的思想一、直接计算DFT计算量问题提出:设有限长序列x(n),非零值长度为N,计算对x(n)进行一次DFT运算,共需多大的运算工作量?1.比较DFT与IDFT之间的运算量其中x(n)为复数,也为复数所以DFT与IDFT二者计算量相同。2.以DFT为例,计算DFT复数运算量计算一个X(k)(一个频率成分)值,运算量为例k=1则要进行N次复数乘法+(N-1)次复数加法
2、所以,要完成整个DFT运算,其计算量为:N*N次复数相乘+N*(N-1)次复数加法3.一次复数乘法换算成实数运算量复数运算要比加法运算复杂,需要的运算时间长。一个复数乘法包括4个实数乘法和2个实数相法。(a+jb)(c+jd)=(ac-bd)+j(bc+ad)4次实数乘法2次实数加法4.计算DFT需要的实数运算量每运算一个X(k)的值,需要进行4N次实数相乘和2N+2(N-1)=2(2N-1)次实数相加.整个DFT运算量为:4N2次实数相乘和2N(2N-1)次实数相加.由此看出:直接计算DFT时,乘法次数与加法次数都是和N2成比例的。当N
3、很大时,所需工作量非常可观。例子:例1:当N=1024点时,直接计算DFT需要:N2=220=1048576次,即一百多万次的复乘运算这对实时性很强的信号处理(如雷达信号处理)来讲,它对计算速度有十分苛刻的要求-->迫切需要改进DFT的计算方法,以减少总的运算次数。例2:石油勘探,24道记录,每道波形记录长度5秒,若每秒抽样500点/秒,每道总抽样点数=500*5=2500点24道总抽样点数=24*2500=6万点DFT运算时间=N2=(60000)2=36*108次二、改善DFT运算效率的基本途径利用DFT运算的系数的固有对称性和周期性
4、,改善DFT的运算效率。合并法:合并DFT运算中的某些项。分解法:将长序列DFT利用对称性和周期性,分解为短序列DFT。利用DFT运算的系数的固有对称性和周期性,改善DFT的运算效率的对称性:的周期性:因为:由此可得出:例子例:利用以上特性,得到改进DFT直接算法的方法.(1)合并法:步骤1分解成虚实部合并DFT运算中的有些项对虚实部而言所以带入DFT中:(1)合并法:步骤2代入DFT中展开:(1)合并法:步骤3合并有些项根据:有:(1)合并法:步骤4结论由此找出其它各项的类似归并方法:乘法次数可以减少一半。例:2、将长序更DFT利用对称
5、性和周期性分解为短序列DFT--思路因为DFT的运算量与N2成正比的如果一个大点数N的DFT能分解为若干小点数DFT的组合,则显然可以达到减少运算工作量的效果。2、将长序列DFT利用对称性和周期性分解为短序列DFT--方法把N点数据分成二半:其运算量为:再分二半:+=+++=这样一直分下去,剩下两点的变换。2、将长序列DFT利用对称性和周期性分解为短序列DFT--结论快速付里时变换(FFT)就是在此特性基础上发展起来的,并产生了多种FFT算法,其基本上可分成两大类:按抽取方法分:时间抽取法(DIT);频率抽取法(DIF)按“基数”分:基-
6、2FFT算法;基-4FFT算法;混合基FFT算法;分裂基FFT算法其它方法:线性调频Z变换(CZT法)二、基--2FFT算法时域抽取DIT频域抽取DIFIFFT计算方法(一)基--2按时间抽取的FFT算法(DIT)一、算法原理设输入序列长度为N=2M(M为正整数,将该序列按时间顺序的奇偶分解为越来越短的子序列,称为基2按时间抽取的FFT算法。也称为Coolkey-Tukey算法。其中基数2----N=2M,M为整数.若不满足这个条件,可以人为地加上若干零值(加零补长)使其达到N=2M例子设一序列x(n)的长度为L=9,应加零补长为N=2
7、4=16应补7个零值。0123456789101112131415nx(n)二、算法步骤1.分组,变量置换DFT变换:先将x(n)按n的奇偶分为两组,作变量置换:当n=偶数时,令n=2r;当n=奇数时,令n=2r+1;得到:x(2r)=x1(r);x(2r+1)=x2(r);r=0…N/2-1;则其DFT可化为两部分:前半部分:后半部分:2.代入DFT中生成两个子序列x(0),x(2)…x(2r)奇数点x(1),x(3)…x(2r+1)偶数点代入DFT变换式:3.求出子序列的DFT上式得:4.结论1一个N点的DFT被分解为两个N/2点DF
8、T。X1(k),X2(k)这两个N/2点的DFT按照:再应用W系数的周期性,求出用X1(k),X2(k)表达的后半部的X(k+N/2)的值。5.求出后半部的表示式看出:后半部的k值所对应的X1
此文档下载收益归作者所有