c - FFT 返回真实答案的共轭

Question

我有一个奇怪的问题。关注(回复:复制)来自 here ，我一直在尝试实现 Cooley–Tukey用于大小为 2 的幂的数组的 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

而真正的答案是共轭。

有什么想法吗？

Answer 1

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

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

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

• 1⁰•1 + 1¹•2 + 1²•3 + 1³•4 = 1 + 2 + 3 + 4 = 10。
• i⁰•1 + i¹•2 + i²•3 + i³•4 = 1 + 2i – 3 – 4i = –2 – 2i。
• (–1)⁰•1 + (–1)¹•2 + (–1)²•3 + (– 1)³•4 = 1 – 2 + 3 – 4 = –2。
• (–i)⁰•1 + (–i)¹•2 + (–i)²•3 + (– i)³•4 = 1 – 2i – 3 + 4i = –2 + 2i。

这就是你得到的结果。