c# - C# 中的逆 FFT

Question

我正在编写程序音频文件的应用程序，我必须分析我的新文件，获取其频谱并在其计算中更改它。

我想用快速傅里叶变换 (FFT) 来做到这一点。这是我的递归 C# FFT:

void ft(float n, ref Complex[] f)
{
    if (n > 1)
    {
        Complex[] g = new Complex[(int) n / 2];
        Complex[] u = new Complex[(int) n / 2];

        for (int i = 0; i < n / 2; i++)
        {
            g[i] = f[i * 2];
            u[i] = f[i * 2 + 1];
        }

        ft(n / 2, ref g);
        ft(n / 2, ref u);

        for (int i = 0; i < n / 2; i++)
        {
            float a = i;
            a = -2.0f * Mathf.PI * a / n;
            float cos = Mathf.Cos(a);
            float sin = Mathf.Sin(a);
            Complex c1 = new Complex(cos, sin);
            c1 = Complex.Multiply(u[i], c1);
            f[i] = Complex.Add(g[i], c1);

            f[i + (int) n / 2] = Complex.Subtract(g[i], c1);
        }
    }
}

鼓舞人心的例子是

然后我将我的结果与来自 wolframalpha 的结果进行了比较对于相同的输入 0.6,0.7,0.8,0.9 但结果并不相同。我的结果是 Wolfram 的两倍，虚部是 Wolfram 的 -2 倍。

此外，wiki 指出可以计算 FFT 的逆

但我比较输入和输出，它们是不同的。

有人知道哪里出了问题吗？

Answer 1

不同的实现通常使用不同的离散傅里叶变换 (DFT) 定义，结果也相应不同。实现之间的对应关系通常相当微不​​足道(例如比例因子)。

更具体地说，您的实现基于 DFT 的以下定义:

另一方面，Wolfram alpha 默认使用 a definition ，在调整到基于 0 的索引之后看起来像:

相应地，可以转换您的实现结果以匹配 Wolfram alpha 的:

void toWolframAlphaDefinition(ref Complex[] f)
{
  float scaling = (float)(1.0/Math.Sqrt(f.Length));
  for (int i = 0; i < f.Length; i++)
  {
    f[i] = scaling * Complex.Conjugate(f[i]);
  }
}

现在就使用正变换计算逆DFT而言，公式的直接实现

您提供的是:

void inverseFt(ref Complex[] f)
{
  for (int i = 0; i < f.Length; i++)
  {
    f[i] = Complex.Conjugate(f[i]);
  }
  ft(f.Length, ref f);
  float scaling = (float)(1.0 / f.Length);
  for (int i = 0; i < f.Length; i++)
  {
    f[i] = scaling * Complex.Conjugate(f[i]);
  }
}

在原始序列 0.6, 0.7, 0.8, 0.9 上调用 ft 应该会得到转换后的序列 3, -0.2+0.2j, -0.2 , -0.2-0.2j.

在此转换序列上进一步调用 inverseFt 应该会将您带回原始序列 0.6, 0.7, 0.8, 0.9(在一些合理的浮点误差范围内)，因为显示在 this live demo .