基二fft的c语言实现（频域）.txt

提供基二FFT(频域)的C语言算法,希望对大家有用

        毕业设计的时候因为用到FFT所以编了基于时域抽取的基二算法，因为好多朋友想要基于频域的程序，由于本人一直忙于学习，最近总算考完试，没什么事情干就把原来的程序改改，给大家提供一个基于频域的算法，希望对大家有所帮助。

         基于时域和基于频域的算法很相似的，只不过时域里是先乘后加减，对输入序列进行倒序，而频域的算法是先加减后乘，输入序列不用倒序，对输出序列进行倒序。

         调试成功之后，发现两者结果相差很小了，呵呵。

/*基二频域算法*/
#include "math.h"
#include "stdio.h"

struct compx 
{ double real;
  double imag;
} compx ;


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,i,k,j,L;
double p , ps ;
int le,B,ip;
float pi;
struct compx v,w,t;
LH=N/2;  
f=N;
for(m=1;(f=f/2)!=1;m++){;}  /*2^m=N*/

{
for(L=m;L>=1;L--)    /*这里和时域的也有差别*/
{  
le=pow(2,L);
B=le/2; /*每一级碟形运算间隔的点数*/
pi=3.14159;
 for(j=0;j<=B-1;j++)
  {
   p=pow(2,m-L)*j;
   ps=2*pi/N*p;
   w.real=cos(ps);
   w.imag=-sin(ps);
   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);
     }
  }
}
} 
/*变址运算*/

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;
}

} 


/*****************main programe********************/

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

float  result[257];
struct  compx s[257];
int   Num=16;
const float pp=3.14159;

main()
{

int i;
for(i=0;i<16;i++)
{
s[i].real=sin(pp*i/32);
s[i].imag=0;
}

FFT(s,Num);

for(i=0;i<16;i++)
{
printf("%.4f",s[i].real);
printf("+%.4fj\n",s[i].imag);
result[i]=sqrt(pow(s[i].real,2)+pow(s[i].imag,2));
}