基于C语言的快速傅里叶变换FFT算法含详细注释

简单易懂的程序，对于处理数据的具体要求可以根据注释修改。

/*这个程序最多512个点，如果需要处理更多的数据，可以改动R的值*/
#include   
#include   
#define   R   512
#define   PI   3.141592653
typedef struct//定义一个复数结构
     {
      double   real;//由于三角运算结果是double型，所以不能用float定义
      double   img;
      }complex;
complex   x[R] W[R];//FFT输入和输出的存储空间
void   fft（）; //快速傅里叶变换算法实现
void   change（）;

int   N=0;//定义并初始化序列的长度，必须是2的自然数次幂，不能超过N
int   L=0;
void   add（complex   acomplex   bcomplex   *c）   //复数加法
           {   
             c->real=a.real+b.real;   
             c->img=a.img+b.img;   
            }   
    
 void   mul（complex   acomplex   bcomplex   *c）   //复数乘法
             {   
               c->real=a.real*b.real   -   a.img*b.img;   
               c->img=a.real*b.img   +   a.img*b.real;   
              }   
 void   sub（complex   acomplex   bcomplex   *c）   //复数减法
              {   
                c->real=a.real-b.real;   
                c->img=a.img-b.img;   
               }   
int   main（）
        {
         int   i;
         printf（“序列长度为2的L次方，请输入L的值（1~9）:\n“）;//输入指数值（1~9）确定序列的长度
         scanf（“%d“&L）;
		 N=（int） pow（2L）;
			 if（L<1）
				 printf（“L值输入错误“）;
			 else if（N>R）
				 printf（“L值过大“）;
			 else												//只有在L值合法情况才执行主程序
				{
				printf（“请依次输入X（n）的复数序列值（实部 虚部）:\n“）;                        
				for（i=0;i					{
						scanf（“%lf %lf“&x[i].real&x[i].img）;
              
					}
				fft（）;  
				printf（“结果如下\n“）;   
            for（i=0;i               {   
                 printf（“%.4f“x[i].real）;   
                 if（x[i].img>=0.0001）   
                 printf（“+%.4fj\n“x[i].img）;   
                 else   if（fabs（x[i].img）<0.0001）   
                 printf（“\n“）;   
                 else     
                 printf（“%.4fj\n“x[i].img）;   
               }   
		        return   0;
				} 
		}
            void   fft（）   
                {   
                  int   ai=0j=0k=0l=0;   
                  complex   HILOOU;   //定义奇偶两部分和结果的复数结构
                  change（）;   //倒序列 
					for（a=0;a					{   
						W[a].real=cos（2*PI/N*a）;   //指数从0到N-1的所有旋转因子
						W[a].img=-1*sin（2*PI/N*a）;   
					}   
				  for（i=0;i                       {       
                         l=1<                         for（j=0;j                           {                           
                             for（k=0;k                                {                 
                                  mul（x[j+k+l]W[N*k/2/l]&OU）;  //一次蝶形运算的过程 
                                  add（x[j+k]OU&HI）;   
                                  sub（x[j+k]OU&LO）; 
                                  x[j+k]=HI;   x[j+k+l]=LO;   
                                   }   
                              }   
                         }   
                    } 

void   change（）   //序列的倒序
    

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2013-06-22 21:56  1\
     文件        4280  2013-06-22 21:56  1\1.dsp
     文件         510  2013-06-18 21:30  1\1.dsw
     文件       50176  2013-06-22 21:56  1\1.ncb
     文件       48640  2013-06-22 21:56  1\1.opt
     文件        1564  2013-06-22 20:45  1\1.plg
     目录           0  2013-06-22 20:45  1\Debug\
     文件       50176  2013-06-22 20:45  1\Debug\1.bsc
     文件      225371  2013-06-22 20:45  1\Debug\1.exe
     文件      223736  2013-06-22 20:45  1\Debug\1.ilk
     文件      181740  2013-06-22 19:03  1\Debug\1.pch
     文件      484352  2013-06-22 20:45  1\Debug\1.pdb
     文件       10171  2013-06-22 20:45  1\Debug\Text1.obj
     文件           0  2013-06-22 20:45  1\Debug\Text1.sbr
     文件       33792  2013-06-22 20:47  1\Debug\vc60.idb
     文件       53248  2013-06-22 20:45  1\Debug\vc60.pdb
     文件        3868  2013-06-22 20:45  1\Text1.c