// 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> >&); //手工輸入數(shù)據(jù) 

void FFT(unsigned long &, vector<complex<double> >&); //FFT變換 

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

bool readDataFromFile(unsigned long &, vector<complex<double> >&); //從文件中讀取數(shù)據(jù) 

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 = ' '; //功能選擇 

//功能循環(huán) 

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': //手工輸入數(shù)據(jù) 

case 'M': 

if(inputData(ulN, vecList)) 

{ 

FFT(ulN, vecList); 

display(ulN, vecList); 

saveResultToFile(ulN, vecList); 

} 

break; 

case 'f': //從文檔讀取數(shù)據(jù) 

case 'F': 

if(readDataFromFile(ulN, vecList)) 

{ 

FFT(ulN, vecList); 

display(ulN, vecList); 

saveResultToFile(ulN, vecList); 

} 

break; 

} 

} 

return 0; 

} 



bool Is2Power(unsigned long ul) //判斷是否是2的整數(shù)次冪 

{ 

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) //從文件中讀取數(shù)據(jù) 

{ 

//題目 

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) 

{ 

//得到冪數(shù) 

unsigned long ulPower = 0; //冪數(shù) 

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; //段的數(shù)量 

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; 

} 

}