如何实现定点FFT算法

只看该作者 · 2007-10-4 20:59

如何实现定点FFT算法

请高人们讲解一下！

computer00，你是高人，我知道～！

4万 · 2007-10-4 21:03

只看该作者 · 2007-10-4 21:07

那是浮点FFT

定点好像还要防止溢出，具体过程我就不清楚了。

要是有个程序那就谢天谢地谢高人了！

4万 · 2007-10-4 21:09

4万 · 2007-10-4 21:09

只看该作者 · 2007-10-4 21:13

ARM，应该可以

传我邮箱，高人

rockzone@163.com

4万 · 2007-10-4 21:14

只看该作者 · 2007-10-4 21:16

对于正常的FFT算法，我们都是将数据存储到单精度或双精度数组里。

这对于ARM或者单片机处理起来就太慢了。

所以要把数据存到整型数组里，这样计算速度更快，当然好像还要考虑溢出问题，

具体啊我就不清楚了。所以请高人指点

还是需要指点～～～～～～～～～～～～～都往这看啊！！！！

4万 · 2007-10-4 21:18

4万 · 2007-10-4 21:20

http://topic.csdn.net/t/20051214/15/4459205.html

傅立叶变换的程序贴出如下:

  #include   <stdio.h>
  #include   <math.h>
  #define   N     64
  #define   m     6     //2^m=N
  /*
  float   twiddle[N/2]={1.0,0.707,0.0,-0.707,};
  float   x_r[N]={1,1,1,1,0,0,0,0,};
  float   x_i[N];                         //N=8
  */
  float   twiddle[N/2]={1,0.9951,0.9808,0.9570,0.9239,0.8820,0.8317,0.7733,
                                      0.7075,0.6349,0.5561,0.4721,0.3835,0.2912,0.1961,0.0991,
                                      0.0000,-0.0991,-0.1961,-0.2912,-0.3835,-0.4721,-0.5561,-0.6349,
                                      -0.7075,-0.7733,0.8317,-0.8820,-0.9239,-0.9570,-0.9808,-0.9951,};       //N=64
  float   x_r[N]={1,1,1,1,1,1,1,1,
                              1,1,1,1,1,1,1,1,
                              1,1,1,1,1,1,1,1,
                              1,1,1,1,1,1,1,1,
                                    0,0,0,0,0,0,0,0,
                              0,0,0,0,0,0,0,0,
                              0,0,0,0,0,0,0,0,
                              0,0,0,0,0,0,0,0,};
  float   x_i[N];

  void   fft_init()
  {
          int   i;
          for(i=0;i<N;i++)
                  x_i=0.0;
  }
  void   bitrev()
  {
          int   p=1,q,i;
          int   bit_rev[N];
          float   xx_r[N];
          bit_rev[0]=0;
          while(p<N)
          {
                  for(q=0;q<p;q++)
                  {
                          bit_rev[q]=bit_rev[q]*2;
                          bit_rev[q+p]=bit_rev[q]+1;
                  }
                  p=p*2;
          }
          for(i=0;i<N;i++)
          {
                  xx_r=x_r;
          }
          for(i=0;i<N;i++)
          {
                  x_r=xx_r[bit_rev];
          }
  }

  void   display()
  {
          int   i;
          for(i=0;i<N;i++)
                  printf("%f %f ",x_r,x_i);
  }

  void   fft1()
  {
          int   L,i,b,j,p,k,tx1,tx2;
          float   TI,TR,temp;
          float   tw1,tw2;

          for(L=1;L<=m;L++)
          {                                                                   /*   for(1)   */
                  b=1;   i=L-1;
                  while(i>0)
                  {b=b*2;i--;}                                   /*   b=   2^(L-1)   */
                  for(j=0;j<=b-1;j++)                           /*   for   (2)   */
                  {   p=1;   i=m-L;
                  while(i>0)                                           /*   p=pow(2,7-L)*j;   */
                  {p=p*2;   i--;}
                  p=p*j;
                  tx1=p%(N);
                  tx2=tx1+(3*N)/4;
                  tx2=tx2%(N);
                  if   (tx1>=(N/2))
                                  tw1=-twiddle[tx1-(N/2)];
                          else
                                  tw1=twiddle[tx1];
                  if   (tx2>=(N/2))
                                  tw2=-twiddle[tx2-(N/2)];
                          else
                                  tw2=twiddle[tx2];
                  for(k=j;k<N;k=k+2*b)                 /*   for   (3)   */
                  {TR=x_r[k];   TI=x_i[k];   temp=x_r[k+b];
                  x_r[k]=x_r[k]+x_r[k+b]*tw1+x_i[k+b]*tw2;
                  x_i[k]=x_i[k]-x_r[k+b]*tw2+x_i[k+b]*tw1;
                  x_r[k+b]=TR-x_r[k+b]*tw1-x_i[k+b]*tw2;
                  x_i[k+b]=TI+temp*tw2-x_i[k+b]*tw1;
                  }
                  }
          }

  }

  void   dft()
  {
          int   i,n,k,tx1,tx2;
          float   tw1,tw2;
          float   xx_r[N],xx_i[N];
          //clear   any   data   in   Real   and   Imaginary   result   arrays   prior   to   DFT
          for(k=0;k<=N-1;k++)
                  xx_r[k]=xx_i[k]=x_i[k]=0.0;
          //caculate   the   DFT
          for(k=0;k<=(N-1);k++)
          {
                  for(n=0;n<=(N-1);n++)
                  {
                  tx1=(n*k);
                  tx2=tx1+(3*N)/4;
                  tx1=tx1%(N);
                  tx2=tx2%(N);
                  if   (tx1>=(N/2))
                                  tw1=-twiddle[tx1-(N/2)];
                          else
                                  tw1=twiddle[tx1];
                  if   (tx2>=(N/2))
                                  tw2=-twiddle[tx2-(N/2)];
                          else
                                  tw2=twiddle[tx2];
                  xx_r[k]=xx_r[k]+x_r[n]*tw1;
                  xx_i[k]=xx_i[k]+x_r[n]*tw2;
                  }
                  xx_i[k]=-xx_i[k];
          }
          //display
            for(i=0;i<N;i++)
                  printf("%f %f ",xx_r,xx_i);

  }

  void   main()
  {
  /*
          fft_init();
          bitrev();
          fft1();
          display();               //FFT
  */
          dft();                       //DFT
  }

只看该作者 · 2007-10-4 21:20

1万 · 2007-10-4 21:31

这样最后的结果就是原来的1024倍，可以保证3位小数的精度。

当然，点数多了，即使全部用整数，32bit的也可能会溢出，可以将最后的结果缩小采样点数分之一。
你还是去找找相关文献吧，TI或者ADI网上或许有些相关的资料？

只看该作者 · 2007-10-5 02:52

float   twiddle[N/2] 改为 WORD twiddle[N/2] = { 32767, int(0.9951*32768), ... };

float   x_r[N]  改为 INT48 x_r[N]  : 这是迭代累加器, 如果使用 16 点以上,一定要用48-bit 或是 64-bit.

结果:  Xr = x_r >> (15+m), Xi = x_i >> (15+m)

只看该作者 · 2013-2-18 21:38

dsplib库有自带的函数可以实现但是不知道对输入数据的格式有什么要求

只看该作者 · 2013-8-13 17:53

学习了

如何实现定点FFT算法

相关下载

相关帖子

先 采样 然后分离数据 最后蝶型 运算

那是浮点FFT

我有 但是 不知道 如何 上传

借问 楼主 的IC 是什么 ？？

~!

在 书本 上

！！

什么 东西 溢出 啊 ？？

摆渡 搜索 很多的拉

数据溢出

可以将系数的小数部分事先放大一定的倍数，例如扩大1024倍

把123654789的程序改改就有了

精华达人奖章

湍急之河流

十世金身

技术导师奖章

荣誉元老奖章

坚毅之洋流

永恒之光奖章

七世轮回

技术高手奖章

常驻人口

先采样然后分离数据最后蝶型运算

我有但是不知道如何上传

借问楼主的IC 是什么？？

在书本上

什么东西溢出啊？？

摆渡搜索很多的拉