fft.cpp

快速傅里叶变换

#include <stdio.h>
#include <iostream.h>
#include <math.h>
#define pi 3.1415926
#define N 4
struct Complex
	{
		double real;
		double image;
	};

struct Complex comadd(struct Complex a,struct Complex b);
struct Complex comsub(struct Complex a,struct Complex b);
struct Complex commul(struct Complex a,struct Complex b);



void main()
{
	double test;
	test=log10(N)/log10(2);
	int M;
	M=int(test);
	if(test!=M)
	{
		cout<<"所设定的数组维数不是2的整数次幂！"<<endl;
		cout<<"请重新设定所要进行变换的数组:"<<endl;
		return;
	}

	int i,j;
	struct Complex x[N],X[N];	
	for (i=0;i<=N-1;i++)
	{
		x[i].real=i+1;
		x[i].image=0;
	}

	//对生成的数组进行输出
	for(i=0;i<=N-1;i++)
	{
		if(x[i].image>=0)
			printf("x[%d]=%f+%fi\n",i,x[i].real,x[i].image);
		else
			printf("x[%d]=%f%fi\n",i,x[i].real,x[i].image);
	}

	int *temp0=new int[M];
	int temp,temp1;
	for(i=0;i<=N-1;i++) 
	{
		temp=0;
		temp1=i;
		for(j=0;j<=M-1;j++)
		{
			temp0[j]=temp1%2;
			temp1=int(temp1/2);			
			temp=temp+int(temp0[j]*pow(2,(M-j-1)));			
		}
		X[i]=x[temp];
		printf("X[%d]=x[%d]  ",temp,i);				
		cout<<endl;
	}
	delete []temp0;

	//对倒位序后的数组进行输出
	for(i=0;i<=N-1;i++)
	{
		if(X[i].image>=0)
			printf("X[%d]=%f+%fi\n",i,X[i].real,X[i].image);
		else
			printf("X[%d]=%f%fi\n",i,X[i].real,X[i].image);
	}

	//开始进行傅里叶变换
	int k,m,B,J,P;
	Complex W,tempX;//tmepXB;
	for(m=1;m<=M;m++)
	{
		B=int(pow(2,(m-1)));

		for(J=0;J<=B-1;J++)
		{
			P=int(J*pow(2,(M-m)));
			W.real=cos(2*pi*P/N);  //计算旋转因子的实部
			W.image=-sin(2*pi*P/N); //计算旋转因子的虚部

			for(k=J;k<=N-1;k=int(k+pow(2,m)))
			{							

	
				tempX=X[k];
				//tmepXB=X[k+B];
				X[k]=comadd(tempX,commul(X[k+B],W));
				X[k+B]=comsub(tempX,commul(X[k+B],W));
				//X[k].real=tempX.real+tmepXB.real*W.real-tmepXB.image*W.image;
				//X[k].image=tempX.image+tmepXB.real*W.image+tmepXB.image*W.real;

				//X[k+B].real=tempX.real-(tmepXB.real*W.real-tmepXB.image*W.image);
				//X[k+B].image=tempX.image-(tmepXB.real*W.image+tmepXB.image*W.real);
			}
		}
	}

	//变换后的数组为：
	cout<<"变换后的数组为："<<endl;
	for(i=0;i<=N-1;i++)
	{
		if(X[i].image>=0)
			printf("X[%d]=%f+%fi\n",i,X[i].real,X[i].image);
		else
			printf("X[%d]=%f%fi\n",i,X[i].real,X[i].image);
	}
}

struct Complex comadd(struct Complex a,struct Complex b)
{
	struct Complex c;
	c.real=a.real+b.real;
	c.image=a.image+b.image;
	return c;
}

struct Complex comsub(struct Complex a,struct Complex b)
{
	struct Complex c;
	c.real=a.real-b.real;
	c.image=a.image-b.image;
	return c;
}
struct Complex commul(struct Complex a,struct Complex b)
{
	struct Complex c;
	c.real=a.real*b.real-a.image*b.image;
	c.image=a.real*b.image+a.image*b.real;
	return c;
}