快速傅里叶变换的详细源代码C++

快速傅里叶变换的C++源代码。用matlab自带的fft进行了测试，结果数据非常吻合。最后用FFT处理了一幅位图。

#pragma pack（1）
#include
#include
#include“BMPStruct.h“
#define Double_PI 6.283185307//2*PI
#define NUM_ZERO 1e-10//浮点数0
using namespace std;
class complex
{
public:
	complex（）{real=0;imag=0;}
	complex（double rdouble i）:real（r）imag（i）{}
	complex（double x）{real=x;imag=0.0;}
	friend complex operator +（complex xcomplex y）;
	friend complex operator -（complex xcomplex y）;
	friend complex operator *（complex xcomplex y）;
	friend complex operator /（complex xcomplex y）;
	friend ostream& operator <<（ostream &outcomplex &x）;
	void operator=（complex x）{real=x.real;imag=x.imag;}
	inline double length（）{return sqrt（real*real+imag*imag）;}//复数的模长
	//friend istream& operator >>（istream &incomplex x）;
public:
	double real;//复数的实部
	double imag;//复数的虚部
};
complex operator+（complex xcomplex y）
{
	return complex（x.real+y.realx.imag+y.imag）;
}
complex operator-（complex xcomplex y）
{
	return complex（x.real-y.realx.imag-y.imag）;
}
complex operator*（complex xcomplex y）
{
	return complex（x.real*y.real-x.imag*y.imagx.real*y.imag+x.imag*y.real）;
}
complex operator/（complex xcomplex y）
{
	return complex（（x.real*y.real+x.imag*y.imag）/（y.real*y.real+y.imag*y.imag）
		（x.imag*y.real-x.real*y.imag）/（y.real*y.real+y.imag*y.imag））;
}
ostream& operator<<（ostream &outcomplex &x）
{
	out<	if（x.imag>0）
		out<<“+“<	else if（abs（x.imag）<=NUM_ZERO）
	     return out;
	else
		out<	return out;
}
void bitReverse（complex *aint r）
{//码位倒置函数，将输入的序号直接按照二进制码为倒置
	int len=1<	int ijkt;
	complex b;//作为交换源数据的中间变量
	for（i=0;i	{
		k=i;//存放当前序号
		t=0;//存放当前序号的二进制逆序数
		for（j=0;j		{
			t<<=1;
			t|=（k&1）;
			k>>=1;
		}
		if（i		{
			b=a[i];
			a[i]=a[t];
			a[t]=b;
		}
	}
}
void FFT（complex *resultcomplex *xint r）
{
	//参数说明：result存放傅里叶变换后的结果，x是源数据，r是源数据的长度以2为底的对数
	int N=1<	int wLen=N>>1;//加权系数的长度
	complex *w=new complex[wLen];//w是加权系数
	int ik;
	double angle;
	for（i=0;i	{
		angle=-i*Double_PI/N;
		w[i].real=cos（angle）;
		w[i].imag=sin（angle）;
	}
	memcpy_s（resultN*sizeof（complex）xN*sizeof（complex））;//将时域信号复制到频域信号里
	bitReverse（resultr）;//先进行码位倒置，保证输出按照顺序输出
	complex x1x2;//取上一次的计算结果
	int level;//蝶形算法当前的级数
	int groups;//当前级上的蝶形组数
	int count;//当前组上的相邻蝶形数目
	int p;//指示当前计算的组的首行
	for（level=0;level	{
		groups=1<<（r-level-1）;
		for（i=0;i		{
			count=1<			p=（i<<1）*（1<			for（k=0;k			{
				x1=result[p+k];
				x2=result[p+k+count];//count=1<				result[p+k]=x1+x2*w[k*（1<<（r-level-1））];
				result[p+k+count]=x1-x2*w[k*（1<<（r-level-1））];
			}
		}
	}
	delete []w;
}
void AnalyzeBmpWithFFT（const char *bmpfilenamechar*resultfile）//用离散傅里叶变换分析一幅位图
{
	FILE *fin;
	if（fopen_s（&finbmpfilename“r“）!=0）
	{
		cout<<“Cannot open t

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        789  2013-10-08 14:44  FFT\BMPStruct.h

     文件      66718  2013-10-08 19:48  FFT\效果图.bmp

     文件       6182  2013-10-08 19:48  FFT\源.cpp

     文件     143478  2013-10-08 19:14  FFT\源图像.bmp

     目录          0  2013-10-08 20:00  FFT

----------- ---------  ---------- -----  ----

               217167                    5