第4章快速计算离散傅里叶变换.ppt
《第4章快速计算离散傅里叶变换.ppt》由会员分享,可在线阅读,更多相关《第4章快速计算离散傅里叶变换.ppt(56页珍藏版)》请在三一文库上搜索。
1、第4章 快速计算离散傅里叶变换,4.1 引言 4.2 基2FFT算法 4.3 进一步减少运算量的措施 4.4 分裂基FFT算法 4.5 离散哈特莱变换(DHT),4.1 引言,与序列的傅里叶变换相比,离散傅里叶变换有实用价值。但是按定义直接计算DFT有实用价值吗?只有一些。因为这种算法的计算数度太慢了。特别是与后人发明的算法相比,它的慢更显突出。 1965年,J. W. Cooley 和 J. W. Tukey在Mathematics of Computation上发表了An algorithm for the machine calculation of complex Fourier se
2、ries。它极大的提高了计算离散傅里叶变换的速度。,从定义来看N点长的DFT的运算量。 1 直接计算DFT需:复乘N2次,复加(N-1)N次。因为 1个k需复乘N次,复加(N-1)次。 对于复乘1次需50s,复加1次需10s的计算机,用直接法做N=1024点长的DFT共需多少时间? 1024250 10-6 102310241010-6=63(s) 2 Cooley和Tukey发明的方法计算DFT需:复乘(N/2)log2N次,复加Nlog2N次。用来计算上面的DFT共需多少时间? 51210 50 10-6 1024101010-6=0.36(s),4.2 基2(radix2)FFT算法,4
3、.2.1 直接计算DFT的特点及减少运算量的方法 直接计算N个采样值的DFT 需要有N2次复数乘法和N(N-1)次复数加法。 如果把N分成几小段,降低DFT的规模,是不是可以大幅度地减少乘法和加法的运算次数? 还有,WNkn具有对称性和周期性,是不是可以巧妙地利用?,例如,当N=8时,从形式上看,W8kn共有64个值。但从图来看, Wkn实际上只有W0W7这8个值是独立的;而且,其中有一半是对称的。 科学家Cooley和Tukey正是巧妙地利用这些特性加快了DFT的运算速度。 周期性: 对称性:,4.2.2 时域抽取法基2FFT基本原理 设序列x(n)的长度N=2M,M为自然数。 (1) 缩短
4、DFT,把x(n)按n的奇偶顺序分成两半。 则x(n)的DFT为,(2) 重组DFT,按DFT的定义重新组合变短的DFT。变短后的DFT中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,周期为N/2;对称性WNk+N/2 = WNk。X(k)又可表示为 经过这两步骤处理后,1个N点的DFT就变成了2个N/2点的DFT。运算量变成: 复乘(N/2)22+(N/2)N2/2次, 复加(N/2) (N/2-1) 2 +(N/2) 2=N2/2次。 比原来多了还是少了?,(4.2.7),(4.2.8),将式(4.2.7)和式(4.2.8)用流图符号表示,称为蝶形运算符号。 采用蝶形
5、符号可以表示N=8 点的DFT运算,下面是经过1次分解的DFT的示意图。 注意:上半部份有4点,用“”的公式做; 下半部份有4点,用“”的公式做。,图4.2.2 8点DFT的一次时域抽取分解图,2次分解x(n)的DFT: (1) 缩短x1(r)和x2(r)的DFT,与第一次分解相同,将x1(r)按奇偶分解成两个N/22长的子序列x3(l)和x4(l),即 则x1(r)的DFT为,(4.2.9),(2)重组DFT,按DFT的定义重新组合变短的DFT。变短后的DFT中X3(k)和X4(k)分别为x3(l)和x4(l)的N/4点DFT,周期为N/22;对称性WN/2k+N/4 = WN/2k。X1(
6、k)也可表示为 用同样的方法可以计算出 如果是8点的DFT,经两次分解,DFT的长度是多少?有几个这种长度的DFT?,图4.2.3 8点DFT的第二次时域抽取分解图,3次分解DFT, ,长度为N/23, 8点DITFFT运算流图 需要几次分解DFT,才会使DFT变为1点的DFT?,4.2.3 时域抽取法快速傅里叶变换的运算量 从分解的级来看 每级需复乘N/2次,?复加N次;? M=log2N级需复乘N/2M次,?复加NM次。? 对于复乘1次需50s,复加1次需10s的计算机,现在做N=1024点的DFT运算。 按定义直接运算需要 1024250 10-6 102310241010-6=63(s
7、) 按DIT-FFT运算需要 51210 50 10-6 1024101010-6=0.36(s) 它们的速度相差630.36=175 (倍)!,例如:分析序列x(n)=sin(1.8n)+cos(1.8n)的频谱。 clear,close all %用两种方法计算DFT n=0:1023;w=1.8; x=sin(w*n)+cos(w*n); subplot(2,1,1),stem(n,x,.); %axis(250,350,-1.5,1.5) w=linspace(0,2*pi,1024); tic;X1=x*exp(-j*n*w);toc;%时间约1.36秒,复加0.2微秒 tic;X2
8、=fft(x);toc;%时间约0秒 subplot(2,1,2),plot(n,abs(X1),.,n,abs(X2),r); %axis(250,350,0,800);%算出角频率1.798弧度,4.2.4 DITFFT的运算规律及编程思想 1. 运算规律 原位计算从蝶形来看这种运算的好处; 有M级从每次分解DFT次数和DFT变短的规律来看; 旋转因子 ,L指第几级,J是序号,从后往前看; 各级蝶形的点距 ,从后往前看。,2. 编程思想 循环1 一级一级地计算蝶形,给出每个蝶的两点距离2L-1; 循环2 一种一种蝶形地计算,给出旋转因子 的指数J,每级有2L-1种不同的蝶; 循环3 同一种
9、蝶里一个一个蝶形地计算,给出同一种蝶形里各蝶形的间隔距离2L。 看图说明,3. 程序框图,图4.2.6 DITFFT运算程序框图,4. 倒序的意思 因为DIT-FFT是对x(n)的序列按偶奇不断地分解,使得N=2M的序号按2倍不断地变短;造成了在蝶形运算时的输入信号排列顺序与原来的顺序不一样。 所以倒序就是从序号的2进制的低位向高位不断地把0(代表偶数)和1(代表奇数)分开。,图4.2.7 N=23时的倒序图,表4.2.1 顺序和倒序二进制数对照表,图4.2.8 倒序规律,图4.2.9 倒序程序框图,习题1和2的解,clear; N=1024; A=N2,N*(N-1); N/2*log2(N
10、),N*log2(N); N*log2(N)+N,2*N*log2(N) b=5e-6,1e-6; T=A*b f=N/T(3)/2,4.2.5 频域抽取法基2FFT基本原理 设序列x(n)的长度为N=2M,M为自然数。 (1) 缩短DFT,将x(n)按前后对半分开。其DFT可表示为如下形式:,(2)重组DFT,按DFT的定义重新组合变短的DFT。将X(k)分解成偶数组与奇数组,变成N/2点的DFT。 当k取偶数时 当k取奇数时 该运算结构中方括号部份可以用蝶形图表示,图4.2.10 DIFFFT蝶形运算流图符号 采用蝶形符号可以表示N=8 点的DFT运算,下面是经过1次分解的DFT的示意图。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 快速 计算 离散 傅里叶变换
链接地址:https://www.31doc.com/p-2498701.html