fft算法以及c语言实现详情解答
为什么需要fft
第一个问题是为什么要创造fft，简单的说，为了速度。我们承认dft很有用，但是我们发现他的速度不是很快，1d的dft原始算法的时间复杂度是o（n^2），这个可以通过公式观察出来，对于2d的dft其时间复杂度是o（n^4），这个速度真的很难接受，也就是说，你计算一幅1024x768的图像时，所以找到一种快速方法的方法计算fft势在必行。
以下为dft公式
如何得到fft 通过观察dft公式，我们发现dft计算每一项x［u］的时候都遍历了完整的x［n］所以，我们的想法就是能不能通过其他的x［u+m］（m为一个整数，可正可负）得到x［u］，也就是充分利用之间的计算结构来构建现在的结果，这种方法就很容易表现成迭代的形式。本文介绍基2的fft，及离散信号x［n］的个数为2的k次方，即如果完整的离散信号中有n个信分量{x1，x2，x3.。。.xn}其中n=1《《k。
fft的数学基础其实就是
用c语言编写fft算法 用simulink建模的方法实现fft的问题特别多，还不如手工编写，也不是很复杂。
以下是512点的单边谱fft算法，在tms320c6713的dsp开发板上调试通过。下面是c语言编写fft算法。
#include “math.h”
#define pi 3.1415926
#define samplenumber 512
void initforfft（）;
void makewave（）;
void fft（）;
int input［samplenumber］，data［samplenumber］;
float fwaver［samplenumber］，fwavei［samplenumber］，w［samplenumber］;
float sin_tab［samplenumber］，cos_tab［samplenumber］;
main（）
{
int i;
initforfft（）;
makewave（）;
for （ i=0;i
{
fwaver［i］=input［i］;
fwavei［i］=0.0f;
w［i］=0.0f;
}
fft（fwaver，fwavei）;
for （ i=0;i
{
data［i］=w［i］;
}
while （ 1 ）; // break point
}
void fft（float datar［samplenumber］，float datai［samplenumber］）
{
int x0，x1，x2，x3，x4，x5，x6，x7，x8，xx;
int i，j，k，b，p，l;
float tr，ti，temp;
for （ i=0;i
{
x0=x1=x2=x3=x4=x5=x6=x7=x8=0;
x0=i&0x01; x1=（i/2）&0x01; x2=（i/4）&0x01; x3=（i/8）&0x01;x4=（i/16）&0x01; x5=（i/32）&0x01; x6=（i/64）&0x01;x7=（i/128）&0x01;x8=（i/256）&0x01;
xx=x0*256+x1*128+x2*64+x3*32+x4*16+x5*8+x6*4+x7*2+x8;
datai［xx］=datar［i］;
}
for （ i=0;i
{
datar［i］=datai［i］; datai［i］=0;
}
for （ l=1;l《=9;l++ ）
{
b=1; i=l-1;
while （ i》0 ）
{
b=b*2; i--;
}
for （ j=0;j《=b-1;j++ ）
{
p=1; i=9-l;
while （ i》0 ）
{
p=p*2; i--;
}
p=p*j;
for （ k=j;k《512;k=k+2*b ）
{
tr=datar［k］; ti=datai［k］; temp=datar［k+b］;
datar［k］=datar［k］+datar［k+b］*cos_tab［p］+datai［k+b］*sin_tab［p］;
datai［k］=datai［k］-datar［k+b］*sin_tab［p］+datai［k+b］*cos_tab［p］;
datar［k+b］=tr-datar［k+b］*cos_tab［p］-datai［k+b］*sin_tab［p］;
datai［k+b］=ti+temp*sin_tab［p］-datai［k+b］*cos_tab［p］;
}
}
}
for （ i=0;i
{
w［i］=sqrt（datar［i］*datar［i］+datai［i］*datai［i］）;
}
}
void initforfft（）
{
int i;
for （ i=0;i
{
sin_tab［i］=sin（pi*2*i/samplenumber）;
cos_tab［i］=cos（pi*2*i/samplenumber）;
}
}
void makewave（）
{
int i;
for （ i=0;i
{
input［i］=sin（pi*2*i/samplenumber*30）*1024;
}
CRC校验码的多种Verilog实现方式
低压灯带PWM调光驱动电源ICSM4A00T成熟应用方案
泰克&交大微纳学院研讨会预告第二弹！电路测试直播培训课程来了！
苹果的自研芯片之路
一文了解2017全球大数据发展趋势
fft算法以及c语言实现详情解答
分析师称苹果服务业务第四季度仍将保持两位数增速
锂离子电池和锂聚合物电池的区别在哪
ICT技术连接城市与乡村 从特岗教师的需求金字塔 重新理解乡村、教育和科技
用于仿生机器人中的机械原理
卓岚信息科技485型4路IO控制模块ZLAN6002介绍
莱迪思推出首款集成USB的小型嵌入式视觉FPGA
惠普星14随身体验 好看又强大
比亚迪助力英国电网成功调度的49MW/49MWh储能项目
RFID气瓶与零售安全管理如何去设计实现
曙光基于水环境数值模型 改善水环境质量提供管理支撑
5G芯片成本大幅增加 手机先行但仍待找寻定位
基于蜂窝 WAN 的智能计量智能电网解决方案
谷歌收缩无人机项目：和星巴克合作送外卖计划泡汤了
专访恩智浦大中华区主席李廷伟：应对气候变化，芯片厂商要提供系统解决方案
以下为dft公式
如何得到fft 通过观察dft公式，我们发现dft计算每一项x［u］的时候都遍历了完整的x［n］所以，我们的想法就是能不能通过其他的x［u+m］（m为一个整数，可正可负）得到x［u］，也就是充分利用之间的计算结构来构建现在的结果，这种方法就很容易表现成迭代的形式。本文介绍基2的fft，及离散信号x［n］的个数为2的k次方，即如果完整的离散信号中有n个信分量{x1，x2，x3.。。.xn}其中n=1《《k。
fft的数学基础其实就是
用c语言编写fft算法 用simulink建模的方法实现fft的问题特别多，还不如手工编写，也不是很复杂。
以下是512点的单边谱fft算法，在tms320c6713的dsp开发板上调试通过。下面是c语言编写fft算法。
#include “math.h”
#define pi 3.1415926
#define samplenumber 512
void initforfft（）;
void makewave（）;
void fft（）;
int input［samplenumber］，data［samplenumber］;
float fwaver［samplenumber］，fwavei［samplenumber］，w［samplenumber］;
float sin_tab［samplenumber］，cos_tab［samplenumber］;
main（）
{
int i;
initforfft（）;
makewave（）;
for （ i=0;i
{
fwaver［i］=input［i］;
fwavei［i］=0.0f;
w［i］=0.0f;
}
fft（fwaver，fwavei）;
for （ i=0;i
{
data［i］=w［i］;
}
while （ 1 ）; // break point
}
void fft（float datar［samplenumber］，float datai［samplenumber］）
{
int x0，x1，x2，x3，x4，x5，x6，x7，x8，xx;
int i，j，k，b，p，l;
float tr，ti，temp;
for （ i=0;i
{
x0=x1=x2=x3=x4=x5=x6=x7=x8=0;
x0=i&0x01; x1=（i/2）&0x01; x2=（i/4）&0x01; x3=（i/8）&0x01;x4=（i/16）&0x01; x5=（i/32）&0x01; x6=（i/64）&0x01;x7=（i/128）&0x01;x8=（i/256）&0x01;
xx=x0*256+x1*128+x2*64+x3*32+x4*16+x5*8+x6*4+x7*2+x8;
datai［xx］=datar［i］;
}
for （ i=0;i
{
datar［i］=datai［i］; datai［i］=0;
}
for （ l=1;l《=9;l++ ）
{
b=1; i=l-1;
while （ i》0 ）
{
b=b*2; i--;
}
for （ j=0;j《=b-1;j++ ）
{
p=1; i=9-l;
while （ i》0 ）
{
p=p*2; i--;
}
p=p*j;
for （ k=j;k《512;k=k+2*b ）
{
tr=datar［k］; ti=datai［k］; temp=datar［k+b］;
datar［k］=datar［k］+datar［k+b］*cos_tab［p］+datai［k+b］*sin_tab［p］;
datai［k］=datai［k］-datar［k+b］*sin_tab［p］+datai［k+b］*cos_tab［p］;
datar［k+b］=tr-datar［k+b］*cos_tab［p］-datai［k+b］*sin_tab［p］;
datai［k+b］=ti+temp*sin_tab［p］-datai［k+b］*cos_tab［p］;
}
}
}
for （ i=0;i
{
w［i］=sqrt（datar［i］*datar［i］+datai［i］*datai［i］）;
}
}
void initforfft（）
{
int i;
for （ i=0;i
{
sin_tab［i］=sin（pi*2*i/samplenumber）;
cos_tab［i］=cos（pi*2*i/samplenumber）;
}
}
void makewave（）
{
int i;
for （ i=0;i
{
input［i］=sin（pi*2*i/samplenumber*30）*1024;
}
CRC校验码的多种Verilog实现方式
低压灯带PWM调光驱动电源ICSM4A00T成熟应用方案
泰克&交大微纳学院研讨会预告第二弹！电路测试直播培训课程来了！
苹果的自研芯片之路
一文了解2017全球大数据发展趋势
fft算法以及c语言实现详情解答
分析师称苹果服务业务第四季度仍将保持两位数增速
锂离子电池和锂聚合物电池的区别在哪
ICT技术连接城市与乡村 从特岗教师的需求金字塔 重新理解乡村、教育和科技
用于仿生机器人中的机械原理
卓岚信息科技485型4路IO控制模块ZLAN6002介绍
莱迪思推出首款集成USB的小型嵌入式视觉FPGA
惠普星14随身体验 好看又强大
比亚迪助力英国电网成功调度的49MW/49MWh储能项目
RFID气瓶与零售安全管理如何去设计实现
曙光基于水环境数值模型 改善水环境质量提供管理支撑
5G芯片成本大幅增加 手机先行但仍待找寻定位
基于蜂窝 WAN 的智能计量智能电网解决方案
谷歌收缩无人机项目：和星巴克合作送外卖计划泡汤了
专访恩智浦大中华区主席李廷伟：应对气候变化，芯片厂商要提供系统解决方案