简单的原地离散傅里叶变换（DFT）

Question

我正在编写一个非常简单的原地离散傅里叶变换。我使用这里显示的公式，以及欧拉公式来避免仅为此目的使用复数类。到目前为止，我的代码如下：

private void fft(double[] data)
        {
            double[] real = new double[256];
            double[] imag = new double[256];
            double pi_div_128 = -1 * Math.PI / 128;
            for (int k = 0; k < 256; k++)
            {
                for (int n = 0; n < 256; n++)
                {
                    real[k] += data[k] * Math.Cos(pi_div_128 * k * n);
                    imag[k] += data[k] * Math.Sin(pi_div_128 * k * n);
                }
                data[k] = Math.Sqrt(real[k] * real[k] + imag[k] * imag[k]);
            }
        }

但是Math.Cos和Math.Sin术语最终会变成正数和负数，所以当我将这些术语乘以data [k]并加起来时，它们会互相抵消，而我只得到一些非常小的值。我知道它是如何发生的，但我无法理解我的代码可能如何歪曲数学。任何帮助都将不胜感激。顺便说一下，我必须自己编写代码，我意识到我可以获得现成的FFT。

- Adam

---

这是一个DFT而不是FFT，请用DFT替换FFT。由于最小编辑字符的限制，我无法完成此操作。 - Ivan Kochurkin

Answer 1

我认为你在这个部分有一个错误

for (int n = 0; n < 256; n++)
{
    real[k] += data[k] * Math.Cos(pi_div_128 * k * n);
    imag[k] += data[k] * Math.Sin(pi_div_128 * k * n);
}

你应该将data[k]替换为data[n]

编辑:

在这行代码中，你也破坏了你的数据：

data[k] = Math.Sqrt(real[k] * real[k] + imag[k] * imag[k]);

你必须将复数的模存储在其他地方或之后。如果模是你想要的全部内容，并且你想将其存储在数据[]中，你必须在计算变换后编写另一个循环。整个数据[]对于计算每个real[k]和imag[k]都是必要的。

- Maciej Hehl

---

修复后，确实解决了极小值问题，但结果看起来一点也不像傅里叶变换。它只是一个直流偏移，然后在转换的其余部分中右侧值在0到4之间。 - Adam

+1 Maciel是正确的。从概念上理解傅里叶变换在一个点（real[k] real[k]，其中k通常是“频率”）并不仅仅与原始信号在一个点（data[n]，其中n通常是“时间”）有关，而是与整个信号有关 - 同样反之亦然。 - leonbloy

Answer 2

private double[] dft(double[] data)
{
    int n = data.Length;
    int m = n;// I use m = n / 2d;
    double[] real = new double[n];
    double[] imag = new double[n];
    double[] result = new double[m];
    double pi_div = 2.0 * Math.PI / n;
    for (int w = 0; w < m; w++)
    {
        double a = w * pi_div;
        for (int t = 0; t < n; t++)
        {
            real[w] += data[t] * Math.Cos(a * t);
            imag[w] += data[t] * Math.Sin(a * t);
        }
        result[w] = Math.Sqrt(real[w] * real[w] + imag[w] * imag[w]) / n;
    }
    return result;
}

- MrHIDEn