全国电子设计大赛一等奖作品中:FFT算法的源码

第八届全国大学生电子设计大赛终于落下帷幕了.经过半年的努力,总算有了回报,拿了个全国一等奖.经过这段时间的历练,懂得了很多事和某些人,我觉得这是远远超过技术本身的收获. 我们做的是A题音频信号分析仪.主要核心是快速傅立叶算法(FFT)的实现.以下是我们写的实现1,2,4,8,16,32,64,128,256,512,1024,2048点的浮点FFT计算代码,利用查表的方法：

/////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Writed by levension @SCUT

//
//Date:2007.09.04

//

//////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include"table.h"
#includemath.h>


intcount[]={1,2,4,8,16,32,64,128,256,512,1024,2048};

/******************************************************
**基2碟形算法
**dataR--采样点的实部的指针
**dataI--采样点的虚部的指针
**n--点数的幂指数
**0,1,2,3,4,5,6,7,8,9,10,11分别对应者点数
**1,2,4,8,16,32,64,128,256,512,1024,2048
******************************************************/

void FFT(float *dataR,float *dataI,int n)
{
int i,L,j,k,b,p,xx,qq;
int x[11]={0};
float TR,TI,temp;


/********** following code invert sequence************/
for(i=0;icount[n];i++)
{ xx=0;

for(j=0;jn;j++)

x[j]=0;


for(j=0;jn;j++)

{x[j]=(i/count[j])0x01;}


for(j=0;jn;j++)

{xx=xx+x[j]*count[n-j-1];}

dataI[xx]=dataR;
}

for(i=0;icount[n];i++)
{

dataR=dataI;

dataI=0;
}


/************** following code FFT*******************/
for(L=1;L=n;L++)
{

/* for(1) */
b=1; i=L-1;
while(i>0)
{ b=b*2;

i--;
}
/* b= 2^(L-1) */
for(j=0;j=b-1;j++)
/* for (2)*/
{ p=1; i=n-L;

while(i>0)
/* p=pow(2,7-L)*j; */
{ p=p*2; i--;}

p=p*j;

for(k=j;kcount[n];k=k+2*b)
/* for (3) */
{
TR=dataR[k];
TI=dataI[k];
temp=dataR[k+b];


//QQ=2*pi*p/count[n];
qq=p*count[11-n];

//////////////////////////////查表/////////////////////////////////////
dataR[k]=dataR[k]+dataR[k+b]*cos_tab[qq]+dataI[k+b]*sin_tab[qq];

dataI[k]=dataI[k]-dataR[k+b]*sin_tab[qq]+dataI[k+b]*cos_tab[qq];

dataR[k+b]=TR-dataR[k+b]*cos_tab[qq]-dataI[k+b]*sin_tab[qq];

dataI[k+b]=TI+temp*sin_tab[qq]-dataI[k+b]*cos_tab[qq];

////////////////////////////////////////////////////////////////
}
/* END for (3) */
}

/* END for (2) */
}



for(i=0;icount[n];i++)
{

dataR=sqrt(dataR*dataR+dataI*dataI);
dataR=dataR/count[n-1];
}
dataR[0]=dataR[0]/2;
}

下面附上TABLE.C文件