fft.c 1.8 KB

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