fft.txt

fft算法c++的实现方法

快速傅里叶变换 要用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 中 

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