快速理解FFT算法
快速福利叶变换C程序包函数简介：此程序包是通用的快速傅里叶变换C语言函数，移植性强，以下部分不依赖硬件。此程序包采用联合体的形式表示一个复数，输入为自然顺序的复数(输入实数是可令复数虚部为0)，输出为经过FFT变换的自然顺序的复数.此程序包可在初始化时调用create_sin_tab()函数创建正弦函数表，以后的可采用查表法计算耗时较多的sin和cos运算，加快可计算速度.与Ver1.1版相比较，Ver1.2版在创建正弦表时只建立了1/4个正弦波的采样值，相比之下节省了FFT_N/4个存储空间使用说明：使用此函数只需更改宏定义FFT_N的值即可实现点数的改变，FFT_N的应该为2的N次方，不满足此条件时应在后面补0。若使用查表法计算sin值和cos值，应在调用FFT函数前调用create_sin_tab()函数创建正弦表函数调用：FFT(s);作 者：吉帅虎时 间：2010-2-20版 本：Ver1.2参考文献：**********************************************************************/#include#include "fft_fp.h"//#define FFT_N 64 //定义福利叶变换的点数//#define PI 3.1415926535897932384626433832795028841971 //定义圆周率值////struct compx {float real,imag;}; //定义一个复数结构struct compx s; //FFT输入和输出：从S开始存放，根据大小自己定义float SIN_TAB; //定义正弦表的存放空间/*******************************************************************函数原型：struct compx EE(struct compx b1,struct compx b2)函数功能：对两个复数进行乘法运算输入参数：两个以联合体定义的复数a,b输出参数：a和b的乘积，以联合体的形式输出*******************************************************************/struct compx EE(struct compx a,struct compx b){struct compx c;c.real=a.real*b.real-a.imag*b.imag;c.imag=a.real*b.imag+a.imag*b.real;return(c);}/******************************************************************函数原型：void create_sin_tab(float *sin_t)函数功能：创建一个正弦采样表，采样点数与福利叶变换点数相同输入参数：*sin_t存放正弦表的数组指针输出参数：无******************************************************************/void create_sin_tab(float *sin_t){int i;for(i=0;i<=FFT_N/4;i++)sin_t[ i]=sin(2*PI*i/FFT_N);}/******************************************************************函数原型：void sin_tab(float pi)函数功能：采用查表的方法计算一个数的正弦值输入参数：pi 所要计算正弦值弧度值，范围0--2*PI，不满足时需要转换输出参数：输入值pi的正弦值******************************************************************/float sin_tab(float pi){int n;float a=0;n=(int)(pi*FFT_N/2/PI);if(n>=0&&n<=FFT_N/4)a=SIN_TAB;else if(n>FFT_N/4&&n{n-=FFT_N/4;a=SIN_TAB;}else if(n>=FFT_N/2&&n<3*FFT_N/4){n-=FFT_N/2;a=-SIN_TAB;}else if(n>=3*FFT_N/4&&n<3*FFT_N){n=FFT_N-n;a=-SIN_TAB;}return a;}/******************************************************************函数原型：void cos_tab(float pi)函数功能：采用查表的方法计算一个数的余弦值输入参数：pi 所要计算余弦值弧度值，范围0--2*PI，不满足时需要转换输出参数：输入值pi的余弦值******************************************************************/float cos_tab(float pi){float a,pi2;pi2=pi+PI/2;if(pi2>2*PI)pi2-=2*PI;a=sin_tab(pi2);return a;}/*****************************************************************函数原型：void FFT(struct compx *xin,int N)函数功能：对输入的复数组进行快速傅里叶变换(FFT)输入参数：*xin复数结构体组的首地址指针，struct型输出参数：无*****************************************************************/void FFT(struct compx *xin){register int f,m,nv2,nm1,i,k,l,j=0;struct compx u,w,t;nv2=FFT_N/2; //变址运算，即把自然顺序变成倒位序，采用雷德算法nm1=FFT_N-1;for(i=0;i{if(i{t=xin;xin=xin[ i];xin[ i]=t;}k=nv2; //求j的下一个倒位序while(k<=j) //如果k<=j,表示j的最高位为1{j=j-k; //把最高位变成0k=k/2; //k/2，比较次高位，依次类推，逐个比较，直到某个位为0}j=j+k; //把0改为1}{int le,lei,ip; //FFT运算核，使用蝶形运算完成FFT运算f=FFT_N;for(l=1;(f=f/2)!=1;l++) //计算l的值，即计算蝶形级数;for(m=1;m<=l;m++) // 控制蝶形结级数{ //m表示第m级蝶形，l为蝶形级总数l=log(2)Nle=2<lei=le/2; //同一蝶形结中参加运算的两点的距离u.real=1.0; //u为蝶形结运算系数，初始值为1u.imag=0.0;//w.real=cos(PI/lei); //不适用查表法计算sin值和cos值// w.imag=-sin(PI/lei);w.real=cos_tab(PI/lei); //w为系数商，即当前系数与前一个系数的商w.imag=-sin_tab(PI/lei);for(j=0;j<=lei-1;j++) //控制计算不同种蝶形结，即计算系数不同的蝶形结{for(i=j;i<=FFT_N-1;i=i+le) //控制同一蝶形结运算，即计算系数相同蝶形结{ip=i+lei; //i，ip分别表示参加蝶形运算的两个节点t=EE(xin,u); //蝶形运算，详见公式xin.real=xin[ i].real-t.real;xin.imag=xin[ i].imag-t.imag;xin[ i].real=xin[ i].real+t.real;xin[ i].imag=xin[ i].imag+t.imag;}u=EE(u,w); //改变系数，进行下一个蝶形运算}}}}/************************************************************函数原型：void main()函数功能：测试FFT变换，演示函数使用方法输入参数：无输出参数：无************************************************************/ 单片机运算fft的效果怎么样 FFT算法比直接算法快速的关键在于它将包含Wi原始矩阵进行分解，分解成每一行中仅仅含有两个非零元素的乘积。 可以实现对音乐频率的控制码 如何理解傅里叶变换公式？ FFT的原理,怎样分析出频率的,越详细越好 在交流信号计量设备中软件就会用到FFT FFT算法在交流信号采集测量应用中基本上都会用上。 FFT算法(fast Fourier transform)，即快速傅里叶变换，是指利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称，简称FFT。 FFT（Fast Fourier Transformation）是离散傅氏变换（DFT）的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。 周期函数的傅里叶级数实质上是将函数分解为无数个不同频率、不同幅值的正、余弦信号，而这些信号的频率都是基频的整数倍（即）。换言之，我们是在用无数个这样不同频率，不同幅值的正、余弦信号来逼近周期函数。分解的过程中，对于每一个，我们都得到了对应的幅值，这是不是就组成了一个函数关系（自变量为，因变量为幅值，即相应频率信号的强度）？我们称之为频谱函数。而对于非周期函数，傅里叶变换则是求频谱密度函数，该函数的自变量是，因变量是信号幅值在频域中的分布密度，即单位频率信号的强度。（如果你学过概率论，可以将频谱函数和频谱密度函数类比为离散概率分布和概率密度函数） FT算法实质上就是DFT算法的改良版，而DFT算法则是傅里叶变换的离散版。按傅里叶变换→DFT→FFT的思路推导，即可理解FFT。 计算离散傅里叶变换的快速方法，有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排，后者是将频域信号序列按偶奇分排。它们都借助于的两个特点:一是周期性;二是对称性，这里符号*代表其共轭。这样，便可以把离散傅里叶变换的计算分成若干步进行，计算效率大为提高。 除了基2的FFT算法之外，还有基4、基8等高基数的FFT算法以及任意数为基数的FFT算法。
页:
[1]