fft.rar_C++ FFT_C++实现fft函数_FFT C_MATLAB中fft函数_fft

// 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 中 //引用任何所需的附加头文件，而不是在此文件中引用