fft.c

FFT源程序

//******************************************************************************//
#define  FFT_GLOBALS
#include "FFT.h"
//******************************************************************************//
void FFT(double dataR[SAMPLE_LEN])
{
    unsigned int x0,x1,x2,x3,x4,x5,x6,x7,x8,x9,xx;
	unsigned int i,j,k,b,p,L;
	double dataI[SAMPLE_LEN]={0};
	double TR,TI,temp;
	
	/*字节倒序*/
	for ( i=0;i<SAMPLE_LEN;i++ )
	{
		x0=x1=x2=x3=x4=x5=x6=x7=x8=x9=0;
		
		x0=i&0x0001;
		x1=(i>>1)&0x0001;
		x2=(i>>2)&0x0001;
		x3=(i>>3)&0x0001;
		x4=(i>>4)&0x0001;
		x5=(i>>5)&0x0001;
		x6=(i>>6)&0x0001;
		x7=(i>>7)&0x0001;
		x8=(i>>8)&0x0001;
		x9=(i>>9)&0x0001;
		xx=x0*512+x1*256+x2*128+x3*64+x4*32+x5*16+x6*8+x7*4+x8*2+x9;
		dataI[xx]=dataR[i];
	}
	for ( i=0;i<SAMPLE_LEN;i++ )
	{
		dataR[i]=dataI[i]; dataI[i]=0; 
	}

	//开始蝶形运算
	for ( L=1;L<=LEVEL;L++ )
	{ /* for(1) */
		b=1; i=L-1;
		while ( i>0 ) 
		{				
			b=b*2; i--;
		} /* b= 2^(L-1) */
		for ( j=0;j<=b-1;j++ ) /* for (2) */
		{
			p=1; i=LEVEL-L;
			while ( i>0 ) /* p=pow(2,7-L)*j; */
			{
				p=p*2; i--;
			}
			p=p*j;
			for ( k=j;k<SAMPLE_LEN;k=k+2*b ) /* for (3) */
			{
				TR=dataR[k]; TI=dataI[k]; temp=dataR[k+b];
				dataR[k]=dataR[k]+dataR[k+b]*cos_tab[p]+dataI[k+b]*sin_tab[p];
				dataI[k]=dataI[k]-dataR[k+b]*sin_tab[p]+dataI[k+b]*cos_tab[p];
				dataR[k+b]=TR-dataR[k+b]*cos_tab[p]-dataI[k+b]*sin_tab[p];
				dataI[k+b]=TI+temp*sin_tab[p]-dataI[k+b]*cos_tab[p];
			} /* END for (3) */
		} /* END for (2) */
	} /* END for (1) */

	for ( i=0;i<SAMPLE_LEN/2;i++ )
	{ 
		dataR[i]=sqrt(dataR[i]*dataR[i]+dataI[i]*dataI[i]);
	}
} /* END FFT */

//******************************************************************************//
void InitForFFT(void)
{
	int i;	
	for ( i=0;i<SAMPLE_LEN;i++ )
	{
		sin_tab[i]=sin(PI*2*i/SAMPLE_LEN);
		cos_tab[i]=cos(PI*2*i/SAMPLE_LEN);
	}
}
//******************************************************************************//