fft.lst

快速傅立叶变化的fft算法的C语言实现。

C51 COMPILER V7.50   FFT                                                                   01/10/2006 18:16:28 PAGE 1   


C51 COMPILER V7.50, COMPILATION OF MODULE FFT
OBJECT MODULE PLACED IN fft.OBJ
COMPILER INVOKED BY: C:\Program Files\Keil\C51\BIN\C51.EXE fft.c LARGE BROWSE DEBUG OBJECTEXTEND

line level    source

   1          #include "fft.h"
   2          
   3          static double cosine[8]=                                /*      cosine[k] = cos(PI/(2^k)) */
   4          {
   5                  -1.0, 0.0, 0.7071068, 0.9238795, 0.9807853, 0.9951847, 0.9987955, 0.9996988
   6          };
   7          
   8          
   9          static  double sine[8]=                                 /*      sine[k] = sin(PI/(2^k))  */
  10          {
  11               0.0, 1.0, 0.7071068, 0.3826834, 0.1950903, 0.0980171, 0.0490677, 0.0245412
  12          };
  13          
  14          /*
  15          此程序是假设一个周期最多采64点的fft变换子程序,如果需要更多点，可以继续添加系数表。
  16          
  17          入口：n－－采样点数
  18                    a－－a是指针，指向采样点构成的数组首地址，采样点存在数组的复数成员的实部。
  19                    
  20          出口：a－－由于a是指针，可以改变其指向的储存单元的数值，实现双向传递。因此fft运算后的
  21                             结果保存在原采样点所在的数组，这也就是原位运算。
  22          */
  23          
  24          
  25          void fft(int n, complex *a) 
  26          {
  27   1              unsigned char le, le1, ip;
  28   1              unsigned char i,j,k;
  29   1              complex t, u, w;        /*用于计算角度*/
  30   1              unsigned char l;        /*矩形窗的长度*/
  31   1              int n1;
  32   1      
  33   1              l = 0;
  34   1              n1 = n;
  35   1              while ( n1 > 1 )           /*求矩形窗的长度*/
  36   1              {
  37   2                      n1 >>= 1;
  38   2                      l ++;
  39   2              }
  40   1      
  41   1              /**********  码位倒置************/
  42   1              /*例：10011变为11001      */
  43   1              for(j = 1, i = 1; i <= n - 1; i++) 
  44   1              {
  45   2                      if(i < j) 
  46   2                      {
  47   3                              t.r = a[j-1].r; 
  48   3                              t.i = a[j-1].i;
  49   3                              a[j-1].r = a[i-1].r; 
  50   3                              a[j-1].i = a[i-1].i;
  51   3                              a[i-1].r = t.r; 
  52   3                              a[i-1].i = t.i;
  53   3                      }
  54   2                      
  55   2                      k = n / 2;
C51 COMPILER V7.50   FFT                                                                   01/10/2006 18:16:28 PAGE 2   

  56   2                      while (k < j) 
  57   2                      {
  58   3                              j -= k;
  59   3                              k >>= 1;
  60   3                      }
  61   2                      j += k;
  62   2              }
  63   1                              
  64   1       
  65   1              for (k = 1; k <= l; k++)
  66   1              { 
  67   2      
  68   2                      le = 1 << k;
  69   2                      le1 = le / 2;
  70   2      
  71   2                      u.r = 1.0; 
  72   2                      u.i = 0.0;
  73   2      
  74   2      
  75   2                      w.r = cosine[k-1]; 
  76   2                      w.i = sine[k-1];
  77   2      
  78   2                      for(j = 1; j <= le1; j++) 
  79   2                      {
  80   3                              for (i = j; i <= n; i += le) 
  81   3                              {
  82   4                                      ip = i + le1;
  83   4                                      t.r = a[ip-1].r * u.r - a[ip-1].i * u.i;
  84   4                                      t.i = a[ip-1].r * u.i + a[ip-1].i * u.r;
  85   4      
  86   4                                      a[ip-1].r = a[i-1].r - t.r; 
  87   4                                      a[ip-1].i = a[i-1].i - t.i;
  88   4               
  89   4                                      a[i-1].r = a[i-1].r + t.r; 
  90   4                                      a[i-1].i = a[i-1].i + t.i;
  91   4                              }
  92   3      
  93   3                              t.r = u.r * w.r + u.i * w.i;
  94   3                              t.i = -u.r * w.i + u.i * w.r;
  95   3      
  96   3                              u.r = t.r; 
  97   3                              u.i = t.i;
  98   3                      }
  99   2              }
 100   1      }


MODULE INFORMATION:   STATIC OVERLAYABLE
   CODE SIZE        =   1463    ----
   CONSTANT SIZE    =   ----    ----
   XDATA SIZE       =     64      36
   PDATA SIZE       =   ----    ----
   DATA SIZE        =   ----    ----
   IDATA SIZE       =   ----    ----
   BIT SIZE         =   ----    ----
END OF MODULE INFORMATION.


C51 COMPILATION COMPLETE.  0 WARNING(S),  0 ERROR(S)