fft2048.c

2048点实序列fft 采用优化地方法节省存储空间和运算时间。包括2048点实序列fft

#include "config.h"

#include <math.h>
#define N 2048

struct compx 
{ float real;
  float imag;
} compx;



struct compx x[N]; /*输入序列,变换核*/
struct compx W[N];

float dis[2048];
//int size_x=2048;
float PI=3.1416;        /*圆周率*/





struct compx EE(struct compx b1,struct compx b2)
{
    struct compx b3;
	b3.real=b1.real*b2.real-b1.imag*b2.imag;
	b3.imag=b1.real*b2.imag+b1.imag*b2.real;
	return(b3);
}

void FFT(struct compx* xin,int n)
{
	int f,m,LH,nm,k,i,j,L,p;
	int le,B,ip;
	struct compx t;
	LH=n/2;  
	f=n;
	m=11;
	for(L=m;L>=1;L--)    /*这里和时域的也有差别*/
	{  
	le=(1<<L);
	B=le/2; /*每一级碟形运算间隔的点数*/
	 for(j=0;j<=B-1;j++)
	  {
	   p=((1<<(m-L))*j);
	   for(i=j;i<=N-1;i=i+le)
	     { 
	      ip=(i+B);   
	      t=xin[i];
	      xin[i].real=xin[i].real+xin[ip].real;
	      xin[i].imag=xin[i].imag+xin[ip].imag;   
	      xin[ip].real=xin[ip].real-t.real;
	      xin[ip].imag=xin[ip].imag-t.imag;      
	      xin[ip]=EE(xin[ip],W[p]);
	     }
	  }
	}
	 
	/*变址运算*/
	
	nm=n-2;    
	j=n/2;
	for(i=1;i<=nm;i++)
	{
	if(i<j) {t=xin[j];xin[j]=xin[i];xin[i]=t;}
	k=LH;
	while(j>=k) {j=j-k;k=k/2;}
	j=j+k;
	}
}