需要帮助理解 FFT 算法中的这一行

Question

在我的程序中，我有一个执行快速傅立叶变换的函数。我知道有非常好的免费实现，但这是一个学习的东西，所以我不想使用它们。我最终通过以下实现找到了此评论（它源自意大利语的 FFT 条目）：

void transform(complex<double>* f, int N) //
{
  ordina(f, N);    //first: reverse order
  complex<double> *W;
  W = (complex<double> *)malloc(N / 2 * sizeof(complex<double>));
  W[1] = polar(1., -2. * M_PI / N);
  W[0] = 1;
  for(int i = 2; i < N / 2; i++)
    W[i] = pow(W[1], i);
  int n = 1;
  int a = N / 2;
  for(int j = 0; j < log2(N); j++) {
    for(int k = 0; k < N; k++) {
      if(!(k & n)) {
        complex<double> temp = f[k];
        complex<double> Temp = W[(k * a) % (n * a)] * f[k + n];
        f[k] = temp + Temp;
        f[k + n] = temp - Temp;
      }
    }
    n *= 2;
    a = a / 2;
  }
  free(W);
}

我现在已经做了很多改变，但这是我的起点。我所做的更改之一是不缓存旋转因素，因为我决定先看看是否需要它。现在我决定要缓存它们。这个实现的方式似乎是它有这个W长度数组N/2，其中每个索引k都有值. 我不明白的是这个表达：

W[(k * a) % (n * a)]

请注意，n * a始终等于N/2。我知道这应该等于，我可以看到 ，这依赖于。我也知道模数可以在这里使用，因为旋转因子是循环的。但有一件事我不明白：这是一个长度为 N 的 DFT，但只N/2计算过旋转因子。数组的长度不应该是 N，模数应该是 N？

Answer 1

但有一件事我不明白：这是一个长度为 N 的 DFT，但只计算了 N/2 个旋转因子。数组的长度不应该是 N，模数应该是 N？

旋转因子是单位圆上等距的点，因为 N 是 2 的幂，所以点数是偶数。绕了半圈后（从 1 开始，在 X 轴上方逆时针走），下半部分是前半部分的重复，但这次它在 X 轴下方（点可以通过原点反射）。这就是Temp第二次减去的原因。该减法是对旋转因子的否定。