1

我有一个奇怪的问题。从这里开始（重新：复制），我一直在尝试为大小为 2 的数组实现Cooley–Tukey FFT 算法，但从这个实现返回的答案是真实答案的共轭。

int fft_pow2(int dir,int m,float complex *a)
{
   long nn,i,i1,j,k,i2,l,l1,l2;
   float c1,c2,tx,ty,t1,t2,u1,u2,z;
   float complex t;
   /* Calculate the number of points */
   nn = 1;
   for (i=0;i<m;i++)
      nn *= 2;

   /* Do the bit reversal */
   i2 = nn >> 1;
   j = 0;
   for (i=0;i<nn-1;i++) {
      if (i < j) {
         t = a[i];
         a[i] = a[j];
         a[j] = t;
      }
      k = i2;
      while (k <= j) {
         j -= k;
         k >>= 1;
      }
      j += k;
   }

   /* Compute the FFT */
   c1 = -1.0;
   c2 = 0.0;
   l2 = 1;
   for (l=0;l<m;l++) {
      l1 = l2;
      l2 <<= 1;
      u1 = 1.0;
      u2 = 0.0;
      for (j=0;j<l1;j++) {
         for (i=j;i<nn;i+=l2) {
            i1 = i + l1;
            t = u1 * crealf(a[i1]) - u2 * cimagf(a[i1])
                + I * (u1 * cimagf(a[i1]) + u2 * crealf(a[i1]));

            a[i1] = a[i] - t;

            a[i] += t;

         }
         z =  u1 * c1 - u2 * c2;
         u2 = u1 * c2 + u2 * c1;
         u1 = z;
      }
      c2 = sqrt((1.0 - c1) / 2.0);
      if (dir == 1)
         c2 = -c2;
      c1 = sqrt((1.0 + c1) / 2.0);
   }

   /* Scaling for forward transform */
   if (dir == 1) {
      for (i=0;i<nn;i++) {
        a[i] /= (float)nn;
      }
   }

   return 1;
}

int main(int argc, char **argv) {
    float complex arr[4] = { 1.0, 2.0, 3.0, 4.0 };
    fft_pow2(0, log2(n), arr);
    for (int i = 0; i < n; i++) {
        printf("%f %f\n", crealf(arr[i]), cimagf(arr[i]));
    }
}

结果：

10.000000 0.000000
-2.000000 -2.000000
-2.000000 0.000000
-2.000000 2.000000

而真正的答案是共轭。

有任何想法吗？

4

1 回答 1

2

FFT 通常定义为 H k = sum(e –2•π•i•j•k/N •h j , 0 < j ≤ N)。注意指数中的减号。FFT 可以用加号而不是减号来定义。在很大程度上，定义是等价的，因为 +i 和 -i 是完全对称的。

您显示的代码是为带有负号的定义编写的，并且还编写了第一个参数dir1 表示正向变换，而其他参数表示反向变换。由于关于正向变换缩放的注释，我们可以确定预期的方向：如果dir为 1，它会缩放。

因此，如果您的代码使用 0 formain调用，则它正在请求反向转换。您的代码使用带负号的 FFT 定义执行了反向转换。带负号的变换的逆是带正号的变换。对于 [1, 2, 3, 4]，结果为：fft_pow2dir

  • 1 0 •1 + 1 1 •2 + 1 2 •3 + 1 3 •4 = 1 + 2 + 3 + 4 = 10。
  • i 0 •1 + i 1 •2 + i 2 •3 + i 3 •4 = 1 + 2i – 3 – 4i = –2 – 2i。
  • (–1) 0 •1 + (–1) 1 •2 + (–1) 2 •3 + (–1) 3 •4 = 1 – 2 + 3 – 4 = –2。
  • (–i) 0 •1 + (–i) 1 •2 + (–i) 2 •3 + (–i) 3 •4 = 1 – 2i – 3 + 4i = –2 + 2i。

这就是你得到的结果。

于 2013-05-16T11:33:15.327 回答