求FFT的c语言程序

Question

追20分

Answer 1

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

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

输入文件：8.TXT 或手动输入

8 //N

1

2

3

4

5

6

7

8

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

8

(36,0)

(-4,9.65685)

(-4,4)

(-4,1.65685)

(-4,0)

(-4,-1.65685)

(-4,-4)

(-4,-9.65685)

下面为FFT.CPP文件：

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

#include "stdafx.h"

#include <iostream>

#include <complex>

#include <bitset>

#include <vector>

#include <conio.h>

#include <string>

#include <fstream>

using namespace std;

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> >&); //保存结果至文件中

const double PI = 3.1415926;

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

{

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

unsigned long ulN = 0; //N

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;

cout << "Please chose:";

//输入选择

chChoose = getch();

//判断

switch(chChoose)

{

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

case 'M':

if(inputData(ulN, vecList))

{

FFT(ulN, vecList);

display(ulN, vecList);

saveResultToFile(ulN, vecList);

}

break;

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

case 'F':

if(readDataFromFile(ulN, vecList))

{

FFT(ulN, vecList);

display(ulN, vecList);

saveResultToFile(ulN, vecList);

}

break;

}

}

return 0;

}

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

{

if(ul < 2)

return false;

while( ul > 1 )

{

if( ul % 2 )

return false;

ul /= 2;

}

return true;

}

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

{

//题目

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

//输入N

cout<< "\nInput N:";

cin>>ulN;

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

{

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

return false;

}

//输入各元素

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

complex<double> c;

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

{

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

cin >> c;

vecList.push_back(c);

}

return true;

}

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

{

//题目

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

//输入文件名

string strfilename;

cout << "Input filename:" ;

cin >> strfilename;

//打开文件

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

ifstream loadfile;

loadfile.open(strfilename.c_str());

if(!loadfile)

{

cout << "\tfailed" << endl;

return false;

}

else

{

cout << "\tsucceed" << endl;

}

vecList.clear();

//读取N

loadfile >> ulN;

if(!loadfile)

{

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

return false;

}

else

{

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

}

//读取元素

complex<double> c;

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

{

loadfile >> c;

if(!loadfile)

{

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

return false;

}

else

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

vecList.push_back(c);

}

//关闭文件

loadfile.close();

return true;

}

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

{

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

char chChoose = ' ';

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

chChoose = _getch();

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

{

return true;

}

//输入文件名

string strfilename;

cout << "\nInput file name:" ;

cin >> strfilename;

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

//打开文件

ofstream savefile(strfilename.c_str());

if(!savefile)

{

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

return false;

}

//写入N

savefile << ulN << endl;

//写入元素

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

{

savefile << *i << endl;

}

//写入完毕

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

//关闭文件

savefile.close();

return true;

}

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

{

//得到幂数

unsigned long ulPower = 0; //幂数

unsigned long ulN1 = ulN - 1;

while(ulN1 > 0)

{

ulPower++;

ulN1 /= 2;

}

//反序

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

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

unsigned long ulK;

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

{

ulIndex = 0;

ulK = 1;

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

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

{

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

ulK *= 2;

}

if(ulIndex > p)

{

complex<double> c = vecList[p];

vecList[p] = vecList[ulIndex];

vecList[ulIndex] = c;

}

}

//计算旋转因子

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

}

//计算FFT

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++)

{

ulHalfLength = ulGroupLength;

ulGroupLength *= 2;

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

c1 = vecList[j + k] + cw;

c2 = vecList[j + k] - cw;

vecList[j + k] = c1;

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文件：

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

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

#pragma once

#include <iostream>

#include <tchar.h>

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

下面为STDAFX.CPP文件：

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

// FFT.pch 将成为预编译头

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

#include "stdafx.h"

// TODO: 在 STDAFX.H 中

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

Answer 2

#include<stdio.h> //计算给定v[NN]的NN点FFT
#include<math.h>
#define pi 3.1415
#define NN 12 //12点FFT
struct plural
{
float real;
float image;
};
int g[NN/2],h[NN/2];
void main()
{
void dft(struct plural *X,int x[NN/2],int N);
void chaikai(int v[],int l);
struct plural chengji(struct plural a,struct plural b);
struct plural w,m,V[NN];
struct plural G[NN/2],H[NN/2];

int v[NN]={3,9,1,0,2,1,4,3,5,2,6,7}; //给出v[NN]
int i,N,k,t;

for(t=0;t<NN/2;t++)
{
G[t].real=0; G[t].image=0; //初始化G[K],H[K]
H[t].real=0; H[t].image=0;
}

N=NN/2;
chaikai(v,NN);
dft(G,g,N);
dft(H,h,N);

for(k=0;k<2*N;k++)
{
w.real=cos(2*pi*k/(2*N));
w.image=-sin(2*pi*k/(2*N));
m=chengji(w,H[k%N]);
V[k].real=G[k%N].real+m.real;
V[k].image=G[k%N].image+m.image;
}

printf("FFT results:\n");
for(i=0;i<2*N;i++)
printf("%.4f+(%.4f*j) ",V[i].real,V[i].image); //结果输出
printf("\n");

}

void dft(struct plural *X,int x[], int N) //求x[n]的N-DFT
{
int k,n;
for(k=0;k<N;k++)
{
for(n=0;n<N;n++)
{

X[k].real+=x[n]*cos(2*pi*k*n/N);
X[k].image+=-x[n]*sin(2*pi*k*n/N);
}

}

}

struct plural chengji(struct plural a,struct plural b) //计算两个复数a,b的乘积返回复数c
{
struct plural c;
c.real=a.real*b.real-a.image*b.image;
c.image=a.real*b.image+a.image*b.real;
return(c);
}

void chaikai(int v[],int l) //将v[n]拆成g[n]和k[n]
{
int i,k=0,m=0;
for(i=0;i<l;i++)
{
if(i%2==1)
h[k++]=v[i];
if(i%2==0)
g[m++]=v[i];

}
}