《快速傅里叶(FFT)算法设计ppt课件.pptx》由会员分享，可在线阅读，更多相关《快速傅里叶(FFT)算法设计ppt课件.pptx（36页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、快速傅里叶快速傅里叶(FFT)算法设计算法设计(含程序设计含程序设计).ppt严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v傅立叶变换将信号从时域转换为频域，可以进行傅立叶变换将信号从时域转换为频域，可以进行模拟信号的频率分析模拟信号的频率分析v离散傅立叶变换离散傅立叶变换(DFT)将信号从频域转换为数字将信号从频域转换为数字(频频)域，可以进行数字信号（模拟信号数字化）域，可以进行数字信号（模拟信号数字化）的频率分析的频率分析v为了实现为了实现DFT在计算机上的快速实现，提出了快在计算机上的快速实现，提出了快速离散傅立叶变换
2、速离散傅立叶变换(FFT)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。如何有傅氏变换如何有傅氏变换-DFT-FFT?v欧拉公式：欧拉公式：v=v令令 ,称为旋转因子称为旋转因子v=v上式中，上式中，k对应数字域，对应数字域，n对应时域对应时域严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v另有推导时需用到的公式：另有推导时需用到的公式：1）,l N为为l个周期个周期 2）,N-m为加上一个周期为加上一个周期3),其中其中4）周期性周期性对对称性称性可可约约性性周
3、期性周期性严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。推导分析推导分析v若序列若序列x(n)的长度为的长度为N，且满足，且满足N=2M,(M为自然数为自然数)按按n的奇偶性把的奇偶性把x(n)分解为两个分解为两个N/2的子序列：的子序列：x1(r)=x(2r),r=0,1,N/2 1x2(r)=x(2r+1),r=0,1,N/2 1则则x(n)的的DFT为：为：严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v=，k=0,1,N/2-1 其中其中X1(k)和和X2
4、(k)均以均以N/2为周期为周期 =，k=0,1,N/2 1其中公式其中公式 称称为为蝶形运算蝶形运算严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v同理，可推出：同理，可推出：，k=0,1,N/4-1 ，k=0,1,N/4 1 分到最后，分到最后，k=0，进行蝶形运算的两个输入就是最初输入序，进行蝶形运算的两个输入就是最初输入序列列x(n)的其中两个。的其中两个。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。蝶形分解图示蝶形分解图示严格执行突发事件上报制度、校外
5、活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。N=8点点FFT运算图示运算图示严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。N=16点点FFT运算图示运算图示严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。蝶形运算规律蝶形运算规律 设序列设序列x(n)已经经过时域抽选已经经过时域抽选(倒序倒序)后，存入数组后，存入数组X中。如中。如果蝶形运算的两个输入相距果蝶形运算的两个输入相距B个点，用原位计算（即计算结果个点，用原位计算（即计
6、算结果还放在数组的原来位置），则蝶形运算可表示成如下形式：还放在数组的原来位置），则蝶形运算可表示成如下形式：=(3)(4)(5)(6)(7)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。=公式公式(7)(8)(9)主要用于主要用于FFT的软件编程的软件编程由由(1)(6)式推式推导导得出得出由由(4)式推式推导导得出得出由由(2)(6)式推式推导导得出得出由由(4)式得出式得出(9)(8)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。公式中的公式中的J就是流程就
7、是流程图图中公式的中公式的变变量量k，流程流程图图中：中：N表示表示阶阶数，数，M表示表示总级总级数，数，L表示当前表示当前级级数，数，B表示每个蝶形的两个表示每个蝶形的两个输输入数据的入数据的间间隔，隔，P表示旋表示旋转转因子指数因子指数严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v可以看出，流程图总共有可以看出，流程图总共有3个循环个循环v外循环：次数为级数外循环：次数为级数L的变换范围的变换范围v中循环：为根据当前中循环：为根据当前L求出各个不同的求出各个不同的p，循环次，循环次 数为数为p的个数的个数2L-1v内循环：
8、为每级中每个内循环：为每级中每个p对应的蝶形运算个数，循对应的蝶形运算个数，循环次数为环次数为2M-L 内循环中内循环中k值每次变换范围值每次变换范围(增量增量)为为2L,这这是同一级中每个相同的是同一级中每个相同的p对应不同蝶形运算的间对应不同蝶形运算的间隔。隔。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。看图推导软件编程规则：方法一看图推导软件编程规则：方法一目的是求出旋目的是求出旋转转因子指数因子指数p的的变变化化规规律律严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为
9、或突发事件。1.当当N=8时，第时，第L级共有级共有2L-1个不同的旋转因子。个不同的旋转因子。因为因为N=2M，所以有，所以有L=1,2,M，即，即L的最大值为的最大值为M 当当L=1时时,p=0;(p称为旋转因子指数称为旋转因子指数)当当L=2时时,p=0,2;k=2 (k为为p的增量的增量)当当L=3时时,p=0,1,2,3;k=1 当当N=16时时 当当L=1时时,p=0;当当L=2时时,p=0,4;k=4 当当L=3时时,p=0,2,4,6;k=2 当当L=4时时,p=0,1,2,3,4,5,6,7;k=1严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、
10、汇报并处理各类违纪行为或突发事件。2.(j=0,1,2,3,)(归纳得出：归纳得出：N/k=2L)(L=1,2,3,表当前级数表当前级数)(M表总级数表总级数)(j=0,1,22L-1-1)=p=j*2M-L (变量为变量为j,L)严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。3.每个每个p对应每级中的运算个数为：对应每级中的运算个数为：第第L级中，每个蝶形的两个输入数据相距级中，每个蝶形的两个输入数据相距B=2L-1点点 同一旋转因子对应着间隔为同一旋转因子对应着间隔为2L点的点的2M-L个蝶形个蝶形严格执行突发事件上报制度、
11、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。看图推导方法二：看图推导方法二：L=1L=2L=3L=4=M有有1个蝶形个蝶形块块，pi=1有有2个蝶形个蝶形块块pi=24个蝶形个蝶形块块pi=48个个块块pi=8pi定定义为义为p的增量的增量严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。反推反推=pi=2M-L令令p=J*pi=J*2M-L (其中其中J=0,1,2,3,)，这样这样写是写是为为了利于了利于软软件件 的循的循环编环编程。此程。此时时只要求出每只要求出每级级J的个数的个数JT
12、otal即可即可=JTotal=2L-1得：得：p=J*2M-L (J=0,1,2,2L-1-1)J的的总总个数个数JTotal为为2L-1，每一每一级级p的的总总个数也个数也为为2L-1严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v外循环次数为级数外循环次数为级数Lv中循环为根据当前中循环为根据当前L求出各个不同的求出各个不同的p，循环次，循环次 数为数为p的个的个数数2L-1v内循环为每级中每个内循环为每级中每个p对应的蝶形运算个数对应的蝶形运算个数(记为记为VTotal)，循，循环次数为环次数为2M-L =VTotal=
13、2M-L严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。每个蝶形的两个每个蝶形的两个输输入数据入数据间间隔（隔（记为记为INd）：）：=INd=2L-1同一同一级级中每个相同的中每个相同的p对应对应蝶形运算的蝶形运算的间间隔（隔（记为记为Vd）：）：=Vd=2L可以看出，可以看出，为为了利于了利于编编程，所有的公式推程，所有的公式推导导都往都往L上靠上靠严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。输入序列倒序的算法设计输入序列倒序的算法设计顺序倒序十进制数I二进制
14、数二进制数十进制数J0000000010011004201001023011110641000011510110156110011371111117顺顺序与倒序二序与倒序二进进制数制数对对照表照表严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。倒序倒序规规律律对对于于N=2M，M位二位二进进制数最高位制数最高位的的权值为权值为N/2，且从左向右二，且从左向右二进进制制位的位的权值权值依次依次为为N/4,N/8,2,1。因此，最高位加因此，最高位加1相当于十相当于十进进制运制运算算J+N/2。如果最高位是。如果最高位是0(JN/2)
15、,则则直接由直接由J+N/2得下一个倒序得下一个倒序值值；如果最高位是如果最高位是1(JN/2),则则要将最高位要将最高位变变成成0(J=J-N/2)，次高位，次高位加加1(J+N/4)。但次高位加。但次高位加1时时同同样样要判断要判断0、1值值，如果，如果为为0(JN/4),则则直接加直接加1(J=J+N/4)，否，否则则先将次高位先将次高位变变成成0(J=J-N/4)，再判，再判断下一位，依次断下一位，依次类类推，直到完成高位加推，直到完成高位加1，适，适2(1+1=10b)向右向右进进位位的运算。的运算。严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并
16、处理各类违纪行为或突发事件。I 可以从可以从1变换变换到到(N/2-1)，即后半部不用考即后半部不用考虑虑只需前半部和后半部交只需前半部和后半部交换换后半部不要再重复交后半部不要再重复交换换判判读读各个高位是否各个高位是否为为1如果如果该该高位高位为为1，则则先先减去减去N/2或或N/4、N/8再判断下个次高位再判断下个次高位严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v/输入序列倒序软件程序输入序列倒序软件程序vj=N/2;v/第第0个数个数(二进制数都为二进制数都为0)和最后一个第和最后一个第N-1个数个数(二进制数都为二
17、进制数都为1)不需倒序不需倒序vfor(i=1;i N-2;i+)vvif(i j)vtemp=dataRi;vdataRi=dataRj;vdataRj=temp;vvk=N/2;vwhile(1)vvif(j k)vj=j+k;vbreak;vvelse vj=j-k;vk=k/2;vvv严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。输入序列倒序的算法设计方法二输入序列倒序的算法设计方法二顺序倒序十进制数I二进制数 二进制数十进制数J0000000010011004201001023011110641000011510110
18、156110011371111117顺顺序与倒序二序与倒序二进进制数制数对对照表照表从表格可以看出，所从表格可以看出，所谓谓倒序只是把数倒序只是把数组组下下标标的的-最高位与最低位互最高位与最低位互换换次高位与次低位互次高位与次低位互换换.严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。方法二方法二软软件分析：已一个字件分析：已一个字节节(N=256)的倒序的倒序为为例例A0,A1,.,A255 (下下标标从从0000_0000变变化到化到1111_1111)/*定定义义两个两个标标志位志位F0，F1*/for(i=0;i(255
19、/2);i+)/除除2是因是因为为只要判断前半部只要判断前半部 j=0;F0=i&0 x01;/取最低位取最低位 F1=i&0 x80;/取最高位取最高位 if(F0)j=j|0 x80;/最低位最低位换换到最高位到最高位 if(F1)j=j|0 x01;/最高位最高位换换到最低位到最低位 F0=i&0 x02;/取次低位取次低位 F1=i&0 x40;/取次高位取次高位 if(F0)j=j|0 x40;/最次位最次位换换到次高位到次高位 if(F1)j=j|0 x02;/最次位最次位换换到次低位到次低位严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各
20、类违纪行为或突发事件。F0=i&0 x04;F1=i&0 x20;if(F0)j=j|0 x20;if(F1)j=j|0 x04;F0=i&0 x08;F1=i&0 x10;if(F0)j=j|0 x10;if(F1)j=j|0 x08;if(ij)/前半部与后半部交前半部与后半部交换换，相等，相等时时无需交无需交换换 Ai Aj;只需只需单层单层循循环环即可，共需要循即可，共需要循环环（128-2）次）次严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。算法改算法改进进一：一：前面的算法可以前面的算法可以进进一步一步优优化化为为：
21、for(i=0;i(255/2);i+)j=0;for(k=0;k4;k+)F0=i&(0 x01k);/取最高位取最高位 if(F0)j=j|(0 x80k);/最低位最低位换换到最高位到最高位 if(F1)j=j|(0 x01k);/最高位最高位换换到最低位到最低位 if(ij)/前半部与后半部交前半部与后半部交换换，相等，相等时时无需交无需交换换 Ai Aj;这这个算法只是个算法只是针对针对8位的，如果是任意位的，如果是任意N位的位的应该应该如何做？如何做？这这里的里的N必必须满须满足足N=2M严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违
22、纪行为或突发事件。算法改算法改进进二：二：针对针对任意任意N=2M的情况的情况for(i=0;i(N/2);i+)/或者或者for(i=0;i(N-1)/2);i+)j=0;for(k=0;k(M/2);k+)/当当N=256时时，M=8 m=0 x01k;F0=i&m;F1=i&n;if(F0)j=j|n;if(F1)j=j|m;if(ij)/前半部与后半部交前半部与后半部交换换，相等，相等时时无需交无需交换换 Ai Aj;严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。FFT软软件示例件示例v#include v#define
23、 PI 3.1415926v#define N 128v#define M 7v#define A0 255.0/定定义输义输入波形的幅入波形的幅值值v vvoid main(void)vvint i,j,k;vint p,J,L,B;vfloat SinInN;vfloat dataRN,dataIN;vfloat dataAN;vfloat Tr,Ti,temp;v/输输入波形入波形vfor(i=0;i N;i+)vvSinIni=A0*(sin(2*PI*i/25)+sin(2*PI*i*0.4);vdataRi=SinIni;/输输入波形的入波形的实实数部分数部分vdataIi=0;/
24、输输入波形的虚数部分入波形的虚数部分vdataAi=0;/输输出波形的幅度出波形的幅度谱为谱为0v严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。v/输输入序列倒序入序列倒序vj=N/2;v/第第0个数个数(二二进进制数都制数都为为0)和最后一个第和最后一个第N-1个数个数(二二进进制数都制数都为为1)不需倒序不需倒序vfor(i=1;i N-2;i+)vif(i j)vtemp=dataRi;vdataRi=dataRj;vdataRj=temp;v/因因为为波形虚数部分都波形虚数部分都为为0,所以不用交所以不用交换换v/tem
25、p=dataIi;v/dataIi=dataIj;v/dataIj=temp;vvk=N/2;vwhile(1)vif(j k)vj=j+k;vbreak;vvelse vj=j-k;vk=k/2;vvv严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。/进进行行FFT/XrJ=Xr(J)+Tr/XiJ=Xi(J)+Ti/XrJ+B=Xr(J)-Tr/XiJ+B=Xi(J)-Ti/(其中其中 Xr为为上一上一级级的的Xr,Xi为为上一上一级级的的Xi)/其中其中Tr=Xr(J+B)cos(2.0*PI*p/N)+Xi(J+B)sin
26、(2.0*PI*p/N)/Ti=Xi(J+B)cos(2.0*PI*p/N)-Xr(J+B)sin(2.0*PI*p/N)for(L=1;L=M;L+)/FFT蝶形蝶形级级数数L从从1-M/计计算每个蝶形的两个算每个蝶形的两个输输入数据相距入数据相距 B=2(L-1);B=1;i=L-1;while(i)B=B*2;i-;/或采用运算或采用运算,即即B=2(L-1);B=(int)pow(2,L-1);严格执行突发事件上报制度、校外活动报批制度等相关规章制度。做到及时发现、制止、汇报并处理各类违纪行为或突发事件。/第第L级级蝶形有蝶形有pow(2,L-1),即即2的的L-1次方个蝶形运算和次方
27、个蝶形运算和pow(2,L-1)个旋个旋转转因子因子pfor(J=0;J=B-1;J+)/J=0,1,2,.,2(L-1)-1/计计算算p=J*2(M-L)p=1;i=M-L;while(i)p=p*2;i-;p=J*p;/第第L级级蝶形中同一个旋蝶形中同一个旋转转因子包含多少个蝶形运算因子包含多少个蝶形运算/每个蝶形的两个每个蝶形的两个输输入数据相距入数据相距B=2(L-1)个点个点/同一旋同一旋转转因子因子对应对应着着间间隔隔为为2L点的点的2(M-L)个蝶形个蝶形 (2L=2*B)for(k=J;k=N-1;k=k+2*B)Tr=dataRk;Ti=dataIk;temp=dataRk+B;dataRk=dataRk+dataRk+B*cos(2.0*PI*p/N)+dataIk+B*sin(2.0*PI*p/N);dataIk=dataIk+dataIk+B*cos(2.0*PI*p/N)-dataRk+B*sin(2.0*PI*p/N);dataRk+B=Tr-dataRk+B*cos(2.0*PI*p/N)-dataIk+B*sin(2.0*PI*p/N);dataIk+B=Ti-dataIk+B*cos(2.0*PI*p/N)+temp*sin(2.0*PI*p/N);