fusu.cpp

傅立叶变换和逆变换

// fusu.cpp: implementation of the Cfusu class.
//
//////////////////////////////////////////////////////////////////////

#include "stdafx.h"
#include "fusu.h"

//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////

Cfusu::Cfusu()
{

}

Cfusu::~Cfusu()
{

}

Fs Cfusu::jia(Fs A, Fs B)
{
	C.a=A.a+B.a;
	C.b=A.b+B.b;
	return C;
}

Fs Cfusu::jian(Fs A, Fs B)
{
	C.a=A.a-B.a;
	C.b=A.b-B.b;
	return C;
}

Fs Cfusu::ceng(Fs A, Fs B)
{
	C.a=(A.a*B.a)-(A.b*B.b);
	C.b=(A.a*B.b)+(A.b*B.a);
	return C;
}

void Cfusu::FFT(Fs* TD, Fs* FD,int r)
{
	int count;
	Fs* X;
	Fs* W;
	Fs* X1;
	Fs* X2;

	count = 1 << r;         // 计算付立叶变换点数
	W  = new Fs[count / 2]; // 分配运算所需存储器
	X1 = new Fs[count];
	X2 = new Fs[count];

	int i,j,k;     // 循环变量
	int	bfsize,p;  // 中间变量

	double angle;  // 角度
	for(i = 0; i < count / 2; i++)
	{
		angle = -i * PI * 2 / count;
		W[i].a=cos(angle);
		W[i].b=sin(angle);
	}

	for(k=0;k<count;k++)// 将时域点写入X1
	{
		X1[k]=TD[k];
	}
	// 采用蝶形算法进行快速付立叶变换
	for(k = 0; k < r; k++)
	{
		for(j = 0; j < 1 << k; j++)
		{
			bfsize = 1 << (r-k);
			for(i = 0; i < bfsize / 2; i++)
			{
				p = j * bfsize;

				X2[i + p] =jia(X1[i + p] , X1[i + p + bfsize / 2]);
				X2[i + p + bfsize / 2] = ceng(jian(X1[i + p] , X1[i + p + bfsize / 2]) , W[i * (1<<k)]);
			}
		}
		X  = X1;
		X1 = X2;
		X2 = X;
	}
	
	for(j = 0; j < count; j++) // 重新排序
	{
		p = 0;
		for(i = 0; i < r; i++)
		{
			if (j&(1<<i))
			{
				p+=1<<(r-i-1);
			}
		}
		FD[j]=X1[p];
	}

	delete []W;   // 释放内存
	delete []X1;
	delete []X2;
}

void Cfusu::IFFT(Fs* FD, Fs* TD,int r)
{
	int count;
	Fs* X1;

	count = 1 << r;         // 计算付立叶变换点数
	X1 = new Fs[count];

	int	i;     // 循环变量
	for(i=0;i<count;i++)// 将频域点写入X
	{
		X1[i]=FD[i];
	}
	
	for(i=0;i<count;i++) // 求共轭
	{
		X1[i].b=-X1[i].b;
	}
	
	FFT(X1,TD,r);               // 调用快速付立叶变换

	for(i = 0; i < count; i++) // 求时域点的共轭
	{
		TD[i].a= TD[i].a/count;
		TD[i].b=-TD[i].b/count;
	}

	delete []X1;   // 释放内存
}