fft.c

在LPC2368上实现的FFT程序

//---------------------------------------------------------------------------


#include <stdio.h>
#include <math.h>
#define PI ((double)3.1415926)
#define N 	1024
#define r 	10
#define FS 	40000
#define F1  5000
#define F2  4900

float x[N];
float fftm[N];

void Fft()
{
	float Real,Ideal=0;
	unsigned int p=0;
	unsigned short i,j,k=0;
	unsigned short b=0;
	//float *fft_ideal;
	//fft_ideal=(float *)malloc(N*sizeof(float));	
   	float fft_ideal[N];
	for(i=0;i<N;i++)
	{
		fft_ideal[i]=0;
	}

	//蝶形运算
	for(k=0;k<r;k++)
	{
		for(j=0;j<(1<<k);j++)
		{
			b=(1<<(r-k));
			for(i=0;i<(b>>1);i++)
			{
				p=j*b;

				Real=fftm[i+p]-fftm[i+p+(b>>1)];
				Ideal=fft_ideal[i+p]-fft_ideal[i+p+(b>>1)];

				fftm[i+p]=fftm[i+p]+fftm[i+p+(b>>1)];
				fft_ideal[i+p]=fft_ideal[i+p]+fft_ideal[i+p+(b>>1)];
				fftm[i+p+(b>>1)]=(Real*cos(-(i*(1<<k))*PI*2/N))-(Ideal*sin(-(i*(1<<k))*PI*2/N));
				fft_ideal[i+p+(b>>1)]=(Ideal*cos(-(i*(1<<k))*PI*2/N))+(Real*sin(-(i*(1<<k))*PI*2/N));

			}
		}
	}

	for(j=0;j<N;j++)
	{											  
		p=0;
		for(i=0;i<r;i++)
		{
			if(j&(1<<i))
			{
				p+=(1<<(r-i-1));
			}
		}
		if(j<p)
		{
			Real=fftm[j];
			fftm[j]=fftm[p];
			fftm[p]=Real;

			Ideal=fft_ideal[j];
			fft_ideal[j]=fft_ideal[p];
			fft_ideal[p]=Ideal;
		}
		fftm[j]=sqrt((fftm[j]*fftm[j])+(fft_ideal[j]*fft_ideal[j]));
	}
	//free(fft_ideal);
}
int main(int argc, char* argv[])
{

    unsigned short i=0,k1=0,k2=0;
    float x1=0,x2=0;
	for(i=0;i<N;i++)
	{
		x[i]=5.0*sin(2.0*PI*i*F1/FS)+2.0*sin(2.0*PI*i*F2/FS);
		fftm[i]=x[i];
	}
	Fft();
    for (i=0;i<512;i++)
    {       
		if(fftm[i]>x1)
		{
            x2=x1;
            x1=fftm[i];
            k2=k1;
            k1=i;
        }
            //printf("%f\t%d\t",fftm[i],i);
            //if(i%3==0) printf("\r\n");
    }
        //printf("%d\t%d\r\n",k1,k2);
       // getchar();
        //return 0;
}