怎样用C语言实现FFT算法啊

一、怎样用C语言实现FFT算法啊

1、二维FFT相当于对行和列分别进行一维FFT运算。具体的实现办法如下：

先对各行逐一进行一维FFT，然后再对变换后的新矩阵的各列逐一进行一维FFT。相应的伪代码如下所示：

其中，ROW[i]表示矩阵的第i行。注意这只是一个简单的记法，并不能完全照抄。还需要通过一些语句来生成各行的数据。同理，COL[i]是对矩阵的第i列的一种简单表示方法。

所以，关键是一维FFT算法的实现。

complexx[N],*W;/*输入序列,变换核*/

intsize_x=0;/*输入序列的大小，在本程序中仅限2的次幂*/

voidadd(complex,complex,complex*);/*复数加法*/

voidmul(complex,complex,complex*);/*复数乘法*/

voidsub(complex,complex,complex*);/*复数减法*/

printf("Pleaseinputthesizeofx:\n");

printf("Pleaseinputthedatainx[N]:\n");

scanf("%lf%lf",&x[i].real,&x[i].img);

for(i=0;i<log(size_x)/log(2);i++){/*一级蝶形运算*/

for(j=0;j<size_x;j+=2*l){/*一组蝶形运算*/

for(k=0;k<l;k++){/*一个蝶形运算*/

mul(x[j+k+l],W[size_x*k/2/l],&product);

sub(x[j+k],product,&down);

W=(complex*)malloc(sizeof(complex)*size_x);

W[i].img=-1*sin(2*PI/size_x*i);

printf("Theresultareasfollows\n");

if(x[i].img>=0.0001)printf("+%.4fj\n",x[i].img);

elseif(fabs(x[i].img)<0.0001)printf("\n");

elseprintf("%.4fj\n",x[i].img);

voidadd(complexa,complexb,complex*c){

voidmul(complexa,complexb,complex*c){

c->real=a.real*b.real-a.img*b.img;

c->img=a.real*b.img+a.img*b.real;

voidsub(complexa,complexb,complex*c){

二、求FFT的c语言程序

快速傅里叶变换要用C++才行吧你可以用MATLAB来实现更方便点啊

此FFT是用VC6.0编写，由FFT.CPP；STDAFX.H和STDAFX.CPP三个文件组成，编译成功。程序可以用文件输入和输出为文件。文件格式为TXT文件。测试结果如下：

输出结果为：或保存为TXT文件。（8OUT.TXT）

// FFT.cpp:定义控制台应用程序的入口点。

bool inputData(unsigned long&, vector<complex<double>>&);//手工输入数据

void FFT(unsigned long&, vector<complex<double>>&);//FFT变换

void display(unsigned long&, vector<complex<double>>&);//显示结果

bool readDataFromFile(unsigned long&, vector<complex<double>>&);//从文件中读取数据

bool saveResultToFile(unsigned long&, vector<complex<double>>&);//保存结果至文件中

int _tmain(int argc, _TCHAR* argv[])

vector<complex<double>> vecList;//有限长序列

char chChoose='';//功能选择

while(chChoose!='Q'&& chChoose!='q')

cout<<"\nPlease chose a function"<< endl;

cout<<"\t1.Input data manually, press'M':"<< endl;

cout<<"\t2.Read data from file, press'F':"<< endl;

cout<<"\t3.Quit, press'Q'"<< endl;

case'm'://手工输入数据

saveResultToFile(ulN, vecList);

case'f'://从文档读取数据

if(readDataFromFile(ulN, vecList))

saveResultToFile(ulN, vecList);

bool Is2Power(unsigned long ul)//判断是否是2的整数次幂

bool inputData(unsigned long& ulN, vector<complex<double>>& vecList)

cout<<"\n\n\n==============================Input Data==============================="<< endl;

cout<<"\nInput N:";

if(!Is2Power(ulN))//验证N的有效性

cout<<"N is invalid(N must like 2, 4, 8,.....), please retry."<< endl;

vecList.clear();//清空原有序列

for(unsigned long i= 0; i< ulN; i++)

cout<<"Input x("<< i<<"):";

bool readDataFromFile(unsigned long& ulN, vector<complex<double>>& vecList)//从文件中读取数据

cout<<"\n\n\n===============Read Data From File=============="<< endl;

cout<<"Input filename:";

cout<<"open file"<< strfilename<<"......."<<endl;

loadfile.open(strfilename.c_str());

cout<<"\tfailed"<< endl;

cout<<"\tsucceed"<< endl;

cout<<"can't get N"<< endl;

cout<<"N="<< ulN<< endl;

for(unsigned long i= 0; i< ulN; i++)

cout<<"can't get enough infomation"<< endl;

cout<<"x("<< i<<")="<< c<< endl;

bool saveResultToFile(unsigned long& ulN, vector<complex<double>>& vecList)//保存结果至文件中

//询问是否需要将结果保存至文件

cout<<"Do you want to save the result to file?(y/n):";

if(chChoose!='y'&& chChoose!='Y')

cout<<"\nInput file name:";

cout<<"Save result to file"<< strfilename<<"......"<< endl;

ofstream savefile(strfilename.c_str());

cout<<"can't open file"<< endl;

savefile<< ulN<< endl;

for(vector<complex<double>>::iterator i= vecList.begin(); i< vecList.end(); i++)

savefile<<*i<< endl;

cout<<"save succeed."<< endl;

void FFT(unsigned long& ulN, vector<complex<double>>& vecList)

unsigned long ulPower= 0;//幂数

bitset<sizeof(unsigned long)* 8> bsIndex;//二进制容器

unsigned long ulIndex;//反转后的序号

for(unsigned long p= 0; p< ulN; p++)

bsIndex= bitset<sizeof(unsigned long)* 8>(p);

for(unsigned long j= 0; j< ulPower; j++)

ulIndex+= bsIndex.test(ulPower- j- 1)? ulK: 0;

complex<double> c= vecList[p];

vecList[p]= vecList[ulIndex];

vector<complex<double>> vecW;

for(unsigned long i= 0; i< ulN/ 2; i++)

vecW.push_back(complex<double>(cos(2* i* PI/ ulN),-1* sin(2* i* PI/ ulN)));

for(unsigned long m= 0; m< ulN/ 2; m++)

cout<<"\nvW["<< m<<"]="<< vecW[m];

unsigned long ulGroupLength= 1;//段的长度

unsigned long ulHalfLength= 0;//段长度的一半

unsigned long ulGroupCount= 0;//段的数量

complex<double> cw;//WH(x)

complex<double> c1;//G(x)+ WH(x)

complex<double> c2;//G(x)- WH(x)

for(unsigned long b= 0; b< ulPower; b++)

for(unsigned long j= 0; j< ulN; j+= ulGroupLength)

for(unsigned long k= 0; k< ulHalfLength; k++)

cw= vecW[k* ulN/ ulGroupLength]* vecList[j+ k+ ulHalfLength];

vecList[j+ k+ ulHalfLength]= c2;

void display(unsigned long& ulN, vector<complex<double>>& vecList)

cout<<"\n\n===========================Display The Result========================="<< endl;

for(unsigned long d= 0; d< ulN;d++)

cout<<"X("<< d<<")\t\t\t="<< vecList[d]<< endl;

// stdafx.h:标准系统包含文件的包含文件，

//或是常用但不常更改的项目特定的包含文件

// TODO:在此处引用程序要求的附加头文件

// stdafx.cpp:只包括标准包含文件的源文件

// stdafx.obj将包含预编译类型信息

//引用任何所需的附加头文件，而不是在此文件中引用