fft.txt

快速傅立叶变换

//***********富丽叶变换*******************
//re ：实部 ；im：虚部；当ll=1，正变换；当ll=-1，反变换；nn:2的幂；
#define PI 3.1415927
     
      void fft(double *re, double *im, int nn, int ll)
{
	int     j, ij, m, l, istep;
	double   sc, actep, bctep, bcarg, aw, bw;
	double   atemp, btemp;

	j = 0;
	sc = sqrt(1.0 / nn);

	for (ij=0; ij<=nn-1; ij++)  
	{
		if (ij <= j) 
		{
			actep = re[j] * sc;
			bctep = im[j] * sc;
			re[j] = re[ij] * sc;
			im[j] = im[ij] * sc;
			re[ij] = actep;
			im[ij] = bctep;
		}
		m = nn/2;
		do  
		{
			if ((j+1)<=m)  
				break;
			j = j - m;
			m = m/2;
		}
		while (m>=1);
		j = j + m;
	 }

	l = 1;
	do 
	{
		istep = 2 * l;
		for (m=1; m<=l; m++) 
		{
			bcarg = -(PI * ll * (m-1)) / l;
			aw = cos(bcarg);  
			bw = sin(bcarg);
			for (ij=m-1; ij<=nn-1; ij=ij+istep) 
			{
				atemp = aw * re[ij+l] - bw * im[ij+l];
				btemp = aw * im[ij+l] + bw * re[ij+l];
				re[ij+l] = re[ij] - atemp;
				im[ij+l] = im[ij] - btemp;
				re[ij] = re[ij] + atemp;
				im[ij] = im[ij] + btemp;
			}
		}
		l = istep;
	} 
	while( l < nn );
}