fft变换.txt

fft变换,经常用到的快速傅立叶算法

/*=====================================================
函数名称：FFT
函数功能：FFT变换，基2DIT
输入参数: x 复数点序列,
		  m FFT的级数
输出参数：无,原址操作
====================================================*/
void FFT(COMPLEX *input, int x)
{
	int n , i , nv2 , j , k , le , l , le1 , ip , nm1 ;
	COMPLEX t , u , w ;

	n = 1;
	for(i=0; i<x; i++)
		n = n*2 ;

	nv2 = n / 2 ;
	nm1 = n - 1 ;
  	j = 1 ;

	for (i = 1 ; i <= nm1 ; i ++)
	{
		if (i < j)
		{
			t.real = input[i - 1].real ;
			t.image = input[i - 1].image ;
			input[i - 1].real = input[j - 1].real ;
			input[i - 1].image = input[j - 1].image ;
			input[j - 1].real = t.real ;
			input[j - 1].image = t.image ;
		}

		k = nv2 ;

		while (k < j)
		{
			j -= k ;
			k /= 2 ;
		}
		j += k ;
	}

	le = 1 ;
	for (l= 1 ; l <= x ; l ++)
	{
		le *= 2 ;
   		le1 = le / 2 ;
		u.real = 1.0f ;
		u.image = 0.0f ;
		w.real = (float) cos(PI / le1) ;
		w.image =(float) -sin(PI / le1) ;

		for (j = 1 ; j <= le1 ; j ++)
		{
			for (i = j ; i <= n ; i += le)
			{
				ip = i + le1 ;
				t.real = input[ip - 1].real * u.real - input[ip - 1].image * u.image ;
				t.image = input[ip - 1].real * u.image + input[ip - 1].image * u.real ;
				input[ip - 1].real = input[i - 1].real - t.real ;
				input[ip - 1].image = input[i - 1].image - t.image ;
				input[i - 1].real = t.real + input[i - 1].real ;
				input[i - 1].image = t.image + input[i - 1].image ;
			}

			t.real = u.real * w.real - u.image * w.image ;
			t.image = u.image * w.real + u.real * w.image ;
			u.real = t.real ;
      		u.image = t.image ;
		}
	}
}