做FFT算法时 3天都没有搞定的问题,请大侠指点迷津~!~!救命啊~!~!
这里是小弟做的FFT算法,编译连接没有问题,(环境VS2008)执行时就有错,搞了三天没明白
希望大虾门能出手相助~!~!~!~!(我知道看完这篇,需要很长的时间)
代码分5个部分
1.头文件Complex.h
//定义复数类#ifndef Complex_H#define Complex_H#include <iostream>#include <cmath>class Complex { public: //类的基本成员 float Real; float Image;//类的构造函数,两个Complex();Complex(float real,float imag);//类的可能运算Complex operator+(Complex k);Complex operator-(Complex k);Complex operator*(Complex k);Complex operator/(Complex k);Complex operator+(float k);Complex operator -(float k);Complex operator*(float k);Complex operator /(float k);//实现实数加复数,实数在前面friend Complex operator *(float a,Complex c1){Complex temp;temp.Real=a*c1.Real;temp.Image=a*c1.Image;return temp;}friend Complex operator + (float a,Complex c1){ Complex temp;temp.Real=c1.Real+a;temp.Image=-c1.Image;return temp;} friend Complex operator -(float a,Complex c1) { Complex temp; temp.Real=a-c1.Real; temp.Image=(-1)*c1.Image; return temp; }#include "Complex.h"#include <iostream>#include <cmath>using namespace std; Complex::Complex(){ Real=0; Image=0;}Complex::Complex(float real,float imag){ Real=real; Image=imag;}Complex Complex::operator +(Complex k){Complex temp;temp.Real=Real+k.Real;temp.Image=Image+k.Image;return temp;} Complex Complex::operator -(Complex k){Complex temp;temp.Real=Real-k.Real;temp.Image=Image-k.Image;return temp;} Complex Complex::operator +(float k){ Complex temp;temp.Real=Real+k;temp.Image=Image; return temp;}Complex Complex::operator -(float k){ Complex temp;temp.Real=Real-k;temp.Image=Image;return temp;}Complex Complex::operator *(Complex k){ Complex temp; temp.Real=this->Real*k.Real+this->Image*k.Image; temp.Image=this->Image*k.Real-this->Real*Image; return temp;}Complex Complex::operator *(float k){Complex temp;temp.Real=k*this->Real;temp.Image=k*this->Image;return temp;}Complex Complex::operator /(Complex k){Complex temp;temp.Real=(1/(pow(k.Real,2)+pow(k.Image,2)))*((this->Real*k.Real+this->Image*k.Image));temp.Image=(1/(pow(k.Real,2)+pow(k.Image,2)))*+(this->Image*k.Real-this->Real*k.Image);return temp;}Complex Complex::operator /(float k){Complex temp;temp.Real=Real/k;temp.Image=Image/k;return temp;}void Complex::display(){ if (abs(Image)<1e-8){ cout<<Real; //cout<<Real<<"+"<<Image<<"i";}else{ if (Image<0){ cout<<Real<<"-"<<abs(Image)<<"i";}else cout<<Real<<"+"<<Image<<"i";}}#ifndef _Function_H#define _Function_H#include "Complex.h"void Input(int &UserDateNum,int& NumOfDate);//完成用户数的修正,与自动补0操作void inversion(Complex *StoragePool,int NumOfDate);//完成实数域到位序Complex CoefficientOfWN(int CurrentLevel, int CurrentLineOfGroup);//计算Wn,右上方还有指数void CoreAlgorithm(Complex *StoragePool,int NumOfDate);//FFT核心算法,(好像就是这里出问题了)void ResultDisplay(Complex *StoragePool,int NumOfDate);//FFT的记过显示#endif
#include "Complex.h"#include "Function.h"#include <cmath>#include <iostream>#include "Complex.h"#include <windows.h>using namespace std;#define Pi 3.1415926void Input(int& UserDateNum,int& NumOfDate){ //确定用户输入数,与你要处理的个数,同时注意补零 cout<<"请输入要处理的数据数N...."<<endl; cin>>UserDateNum; if (abs((log((float)UserDateNum)/log((float)2))-(int)(log((float)UserDateNum)/log((float)2)))<1e-6) { NumOfDate=UserDateNum; } else { NumOfDate=(int)pow((float)2,((int)(log((float)UserDateNum)/log((float)2))+1)); }}void inversion(Complex *StoragePool,int NumOfDate){//验证正确2009年4月5日 Complex *B;int Index=0;int Index2=0;int BitdealTemp1=0;int BitdealTemp2=0;int TempIndex=0;int NumOfBit=(int)(log((float)NumOfDate)/log((float)2));B=(Complex*)new Complex[NumOfDate];for(Index=0;Index<NumOfDate;Index++){ B[Index]=StoragePool[Index];}for (Index=1;Index<NumOfDate-1;Index++) { TempIndex=Index; for (Index2=0;Index2<NumOfBit/2;Index2++){BitdealTemp1=Index&(1<<Index2); BitdealTemp2=Index&(1<<(NumOfBit-1-Index2)); TempIndex=(TempIndex&(~(0x1<<Index2)))|(BitdealTemp2>>((NumOfBit-1-Index2))<<Index2); TempIndex=(TempIndex&(~(0x1<<(NumOfBit-1-Index2))))|((BitdealTemp1>>Index2)<<(NumOfBit-1-Index2));} StoragePool[Index]=B[TempIndex];}delete[] B;}Complex CoefficientOfWN(int CurrentLevel, int CurrentLineOfGroup){//验证正确Complex temp; float Exponential=CurrentLineOfGroup/(float)pow((float)2,CurrentLevel); temp.Real=(float)(cos(2*Pi*Exponential)); temp.Image=(float)(sin(2*Pi*Exponential)); return temp;}void CoreAlgorithm(Complex *StoragePool,int NumOfDate) { //验证失败 int Distance; int MaxLevel=0; int CurrentLevel=1; int CurrentGroupOfLevel; int CurrentLineOfGroup=0; int CurrentBaseLine=0; MaxLevel=(int)(log((float)NumOfDate)/log((float)2)); //完成级数的运算 for (CurrentLevel=1;CurrentLevel<=MaxLevel;CurrentLevel++) { Distance=(int)(pow((float)2,CurrentLevel-1)); CurrentBaseLine=0; for (CurrentGroupOfLevel=1;CurrentGroupOfLevel<=NumOfDate/(float)pow((float)2,CurrentLevel);CurrentGroupOfLevel++) { for (CurrentLineOfGroup=CurrentBaseLine;CurrentLineOfGroup<CurrentBaseLine+2*Distance;CurrentLineOfGroup++) { if (CurrentLineOfGroup<(CurrentBaseLine+Distance)) {StoragePool[CurrentLineOfGroup]=StoragePool[CurrentLineOfGroup]+CoefficientOfWN(CurrentLevel,CurrentLineOfGroup)*StoragePool[CurrentLineOfGroup+Distance]; }else {StoragePool[CurrentLineOfGroup]=StoragePool[CurrentLineOfGroup-Distance]+CoefficientOfWN(CurrentLevel,CurrentLineOfGroup-Distance)*StoragePool[CurrentLineOfGroup]; } CurrentBaseLine+=2*Distance; } } }}void ResultDisplay(Complex *StoragePool,int NumOfDate){//验证正确 int i=0; for (;i<NumOfDate;i++) {cout<<"X["<<i<<"]"<<" "; StoragePool[i].display(); cout<<endl;}}
/***************************************这是基于2的FFT算法的实现 创作时间:2009年4月5日****************************************/#include "Complex.h"#include "Function.h"#include <cstdio>#include <iostream>#include <windows.h>using namespace std;int main(){ int UserDateNum=0;//用户定义的运算数目 int NumOfDate=0;//补零后的运算数目 Complex *StoragePool;//时域数据缓冲池 int TempLoopIndex; Input(UserDateNum,NumOfDate);//补零数据个数的修正 StoragePool=(Complex*)new Complex[NumOfDate]; //建立缓冲池让用户去填充 for(TempLoopIndex=0;TempLoopIndex<UserDateNum;TempLoopIndex++) { cout<<"请输入第"<<TempLoopIndex+1<<"个复数"<<endl; cin>>StoragePool[TempLoopIndex].Real;} TempLoopIndex=0; //填充完成进行倒位序排列system("cls");//清屏 cout<<"请稍等,正在进行FFT计算..."<<endl;inversion(StoragePool,NumOfDate);//到位序算法 //核心算法循环 CoreAlgorithm(StoragePool,NumOfDate); //结果显示 ResultDisplay(StoragePool,NumOfDate); return 0; }