打印
[应用笔记]

快速理解FFT算法

[复制链接]
1933|13
手机看帖
扫描二维码
随时随地手机跟帖
跳转到指定楼层
楼主
i1mcu|  楼主 | 2022-10-28 16:03 | 只看该作者 回帖奖励 |倒序浏览 |阅读模式

快速福利叶变换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_N];                                              //FFT输入和输出:从S[0]开始存放,根据大小自己定义

float SIN_TAB[FFT_N/4+1];                                             //定义正弦表的存放空间

/*******************************************************************

函数原型: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[n];

else if(n>FFT_N/4&&n

{

n-=FFT_N/4;

a=SIN_TAB[FFT_N/4-n];

}

else if(n>=FFT_N/2&&n<3*FFT_N/4)

{

n-=FFT_N/2;

a=-SIN_TAB[n];

}

else if(n>=3*FFT_N/4&&n<3*FFT_N)

{

n=FFT_N-n;

a=-SIN_TAB[n];

}

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[j];

xin[j]=xin[ i];

xin[ i]=t;

}

k=nv2;                    //求j的下一个倒位序

while(k<=j)               //如果k<=j,表示j的最高位为1

{

j=j-k;                 //把最高位变成0

k=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)N

le=2<

lei=le/2;                               //同一蝶形结中参加运算的两点的距离

u.real=1.0;                             //u为蝶形结运算系数,初始值为1

u.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[ip],u);                   //蝶形运算,详见公式

xin[ip].real=xin[ i].real-t.real;

xin[ip].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变换,演示函数使用方法

输入参数:无

输出参数:无

************************************************************/

使用特权

评论回复
沙发
i1mcu|  楼主 | 2022-11-1 10:28 | 只看该作者
单片机运算fft的效果怎么样              

使用特权

评论回复
板凳
modesty3jonah| | 2022-11-1 10:43 | 只看该作者
FFT算法比直接算法快速的关键在于它将包含Wi原始矩阵进行分解,分解成每一行中仅仅含有两个非零元素的乘积。

使用特权

评论回复
地板
uptown| | 2022-11-1 11:00 | 只看该作者
可以实现对音乐频率的控制码              

使用特权

评论回复
5
macpherson| | 2022-11-1 11:33 | 只看该作者
如何理解傅里叶变换公式?                 

使用特权

评论回复
6
hudi008| | 2022-11-1 12:08 | 只看该作者
FFT的原理,怎样分析出频率的,越详细越好  

使用特权

评论回复
7
caigang13| | 2022-11-1 18:48 | 只看该作者
在交流信号计量设备中软件就会用到FFT

使用特权

评论回复
8
chenjun89| | 2022-11-7 08:04 | 只看该作者
FFT算法在交流信号采集测量应用中基本上都会用上。

使用特权

评论回复
9
tpgf| | 2022-11-8 11:57 | 只看该作者
FFT算法(fast Fourier transform),即快速傅里叶变换,是指利用计算机计算离散傅里叶变换(DFT)的高效、快速计算方法的统称,简称FFT。

使用特权

评论回复
10
guanjiaer| | 2022-11-8 12:09 | 只看该作者
FFT(Fast Fourier Transformation)是离散傅氏变换(DFT)的快速算法。即为快速傅氏变换。它是根据离散傅氏变换的奇、偶、虚、实等特性,对离散傅立叶变换的算法进行改进获得的。

使用特权

评论回复
11
heimaojingzhang| | 2022-11-8 12:17 | 只看该作者
周期函数的傅里叶级数实质上是将函数  分解为无数个不同频率、不同幅值的正、余弦信号,而这些信号的频率都是基频  的整数倍(即  )。换言之,我们是在用无数个这样不同频率,不同幅值的正、余弦信号来逼近周期函数  。分解的过程中,对于每一个  ,我们都得到了对应的幅值,这是不是就组成了一个函数关系(自变量为  ,因变量为幅值,即相应频率信号的强度)?我们称之为频谱函数。

而对于非周期函数,傅里叶变换则是求频谱密度函数,该函数的自变量是  ,因变量是信号幅值在频域中的分布密度,即单位频率信号的强度。(如果你学过概率论,可以将频谱函数和频谱密度函数类比为离散概率分布和概率密度函数)

使用特权

评论回复
12
keaibukelian| | 2022-11-8 13:14 | 只看该作者
FT算法实质上就是DFT算法的改良版,而DFT算法则是傅里叶变换的离散版。按傅里叶变换→DFT→FFT的思路推导,即可理解FFT。

使用特权

评论回复
13
paotangsan| | 2022-11-8 13:22 | 只看该作者
计算离散傅里叶变换的快速方法,有按时间抽取的FFT算法和按频率抽取的FFT算法。前者是将时域信号序列按偶奇分排,后者是将频域信号序列按偶奇分排。它们都借助于的两个特点:一是周期性;二是对称性,这里符号*代表其共轭。这样,便可以把离散傅里叶变换的计算分成若干步进行,计算效率大为提高。

使用特权

评论回复
14
renzheshengui| | 2022-11-8 13:34 | 只看该作者
除了基2的FFT算法之外,还有基4、基8等高基数的FFT算法以及任意数为基数的FFT算法。

使用特权

评论回复
发新帖 我要提问
您需要登录后才可以回帖 登录 | 注册

本版积分规则

279

主题

8576

帖子

9

粉丝