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的负二倍。

此外，维基百科表明可以使用以下方法计算FFT的逆变换：

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

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

- Just Kauser

---

寻找现有的处理FFT的库。不太确定你希望从别人那里为你调试代码获得什么。 - Alexei Levenkov

我想找一个有FFT经验的人，能够向我解释如何获得FFT的逆变换，例如使用另一种算法或者可能不可能实现。我的代码可以工作。我尝试了正弦和余弦输入，并得到了正确的输出。 - Just Kauser

Answer 1

不同的实现通常使用不同的离散傅里叶变换（DFT）定义，因此得到的结果也不同。这些实现之间的对应关系通常是非常微不足道的（例如缩放因子）。

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

另一方面，Wolfram Alpha 默认使用定义，在调整为从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所示。

- SleuthEye

---

那么这个反函数只适用于Wolfram定义吗？如果是，那么第一个DFT定义的函数会是什么？ - WDUK

@WDUK inverseFt适用于OP的原始ft实现（以及相应的DFT定义），如ideone演示所示。 - SleuthEye