《FFT算法设计实现分析.pdf》由会员分享，可在线阅读，更多相关《FFT算法设计实现分析.pdf（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-.-FFT 算法研究报告1、程序设计背景(FFT 算法理解)FFT(fast fourier transformation),快速傅里叶变换。是对 DFT 算法的改良，其利用了 WNnk 的周期性、共轭对称性和可约性，使得DFT中有些项可以合并，大大减小了计算量。按输入序列在时间上的次序是属于偶数还是奇数来分解称为“按时间抽取法(DIT)。另一种是把输出序列 X(k)按顺序的奇偶分解为越来越短的序列，称为按频率抽样的 FFT 算法DIF。DIT 算法是先作复乘后作加减，而 DIF 的复乘只出现在减法之后。本次程序采用 DIT 算法实现 FFT。用 c 语言实现 FFT 的难点在于数据倒位序的
2、处理，以及各级蝶形运算的实现。倒位序的实现可以使用“反向进位加法，即倒位序二进制数的下面一个数是上面一个数在最高位加一并由高位向低位进位而得到的。对于点数为 N=2L 的 FFT 运算，可以分解为 L 阶蝶形图级联，第 M 阶蝶形图又分为 2(L-M)个蝶形组，每个蝶形组包含 2(M-1)个蝶形。而且旋转因子与蝶形阶数和蝶形分组的蝶形个数存在关联。因此我们就可以构造循环来实现蝶形运算。.-可修编-.-2、FFT 算法流程图倒位序流程图：YNi=0n=0?输入数组指针 a，长度 nin?NY i%2=0?N Ytemp(n+i)/2=aiTempi=ai/2i=i+1a=tempn=n/2Y完毕
3、.-可修编-.-3、FFT 程序代码#include#include#include#include#define PI 3.141592653#define SIZE 16#define MAX 10/定义复数构造体typedef struct Complex double real;double imag;comp;/定义复数乘法，加法，减法void Add_(comp*a1,comp*a2,comp*b)b-imag=a1-imag+a2-imag;b-real=a1-real+a2-real;void Sub_(comp*a1,comp*a2,comp*b)b-imag=a1-imag
4、-a2-imag;b-real=a1-real-a2-real;.-可修编-.-void Mul_(comp*a1,comp*a2,comp*b)double r1=0.0,r2=0.0;double i1=0.0,i2=0.0;r1=a1-real;r2=a2-real;i1=a1-imag;i2=a2-imag;b-imag=r1*i2+r2*i1;b-real=r1*r2-i1*i2;/利用 srand()、rand()随机生成一个输入并显示数据void Input(double*data,int n)printf(输入信号为:n);srand(int)time(0);for(int i
5、=0;iimag=-sin(x);b-real=cos(x);.-可修编-.-/处理 FFT 的数据位置，输入倒位序，输出自然顺序正序，用递归构造实现int reverse(double*a,int n)if(n=1)return 0;double*temp=(double*)malloc(sizeof(double)*n);for(int i=0;in;i+)if(i%2=0)tempi/2=ai;else temp(n+i)/2=ai;for(int i=0;in;i+)ai=tempi;free(temp);reverse(a,n/2);reverse(a+n/2,n/2);return
6、 1;/定义 FFT 函数void FFT(double*a,comp*b,int n)reverse(a,n);/对输入信号进展倒位序处理 int k=n;int m=0;while(k/=2)/记录需要蝶形运算的级数 m+;.-可修编-.-k=m;comp*a_comp=(comp*)malloc(sizeof(comp)*n);for(int i=0;in;i+)a_compi.real=ai;a_compi.imag=0;/将输入数据赋值给 a_comp for(int i=0;ik;i+)/依次计算各级蝶形运算 z=0;for(int j=0;jn;j+)if(j/(2(i-1)%2
7、=1)comp wn;WN(z,n,&wn);Mul_(&a_compj,&wn,&a_compj);z+=2(k-i-2);comp temp;int company=j-(2(i-1);temp.real=a_compcompany.real;temp.imag=a_compcompany.imag;Add_(&temp,&a_compj,&a_compcompany);Sub_(&temp,&a_compj,&a_compj);else m=0;printf(nnFFT 处理结果:n);for(int i=0;i=0.0).-可修编-.-printf(%lf+%lfjn,a_compi.
8、real,a_compi.imag);else printf(%lf%lfjn,a_compi.real,a_compi.imag);for(int i=0;in;i+)bi.imag=a_compi.imag;bi.real=a_compi.real;int main()double arraySIZE;comp bSIZE;Input(array,SIZE);/随机生成 16 个输入数据FFT(array,b,SIZE);4、与 MATLAB 自带 FFT 函数运行结果的比拟自编 FFT 结果：.-可修编-.-将输入信号在 matlab 中进展 FFT 运算，结果如下：由以上截图可知，函数
9、成功地完成了对于序列xn 的 FFT 计算，但是可以看出 matlab 的准确度更高，应该是 matlab 计算使用的 pi 值更为准确。为比拟二者的时间，将数据长度重新定义为215Matlab FFT 程序：自编 FFT 程序：.-可修编-.-由于计算 matlab 用时使用的数据与自编 FFT 程序所用数据不同，可能会有不可预料的误差存在，但通过屡次重复看出matlab 的 FFT程序更加高效，值得我们学习和使用。5、心得与体会本次编程的过程让我更加深入的了解 FFT 的计算原理与步骤，也看到了 FFT 与 DFT 运算量与运算时间上的巨大差距，明白FFT 给数据处理带来的高效与便捷。同时这种亲身去体验算法优化的过程给学习带来了更多的思考和乐趣，让我受益良多。.-可修编-