C# FFT 实现没有产生预期的结果

Question

为了我自己的学习，我正在尝试在 C# 中实现此处描述的 FFT 算法:

https://en.wikipedia.org/wiki/Cooley%E2%80%93Tukey_FFT_algorithm

在“数据重新排序、位反转和就地算法”下。

我的代码如下，为“cplx”结构重载了一些后台运算符，以允许我对这些对象进行算术运算。

Bitreverse 似乎工作正常，“旋转因子”计算也是如此，所以我不确定哪里出错了。该代码看起来与 wiki 页面上给出的伪代码非常相似。

    public cplx[] FFT(cplx[] x)
    {
        //Bitreverse Copy
        cplx[] a = BitReverse(x);

        //Number of points
        int n = a.Length;

        for (int s = 1; s <= Math.Log(n); s++)
        {
            int m = (int)Math.Pow(2,s);
            cplx w_m = Omega(m);

            for (int k = 0; k < n; k += m)
            {
                cplx w = new cplx(1, 0);

                for(int j = 0; j < m/2; j++)
                {
                    cplx t = w * a[k + j + (m / 2)];
                    cplx u = a[k + j];

                    a[k + j] = u + t;
                    a[k + j + (m / 2)] = u - t;

                    w = w * w_m;
                }
            }
        }

        return a;
    }

我正在使用一个包含 8 个样本的原始脉冲输入数组对其进行测试，它应该会产生一个恒定的输出。

相反，我按顺序得到 4 个 1 和 4 个 0。

顺便说一句，我假设在伪代码中:

for k = 0 to n-1 by m

引用for(k = 0; k < n; k += m)尽管我不确定那是否正确。

希望有人能指出我的无能!

干杯。

这是位反转和 omega 计算的代码。

       private int Rev(int x, int k)
    {
        int reversed = 0;

        for (int i = 0; i < k; i++)
        {
            reversed |= (x & (1 << i)) != 0 ? 1 << (k - 1 - i) : 0;
        }

        return reversed;
    }

    public cplx[] BitReverse(cplx[] x)
    {
        cplx[] r = new cplx[x.Length];

        int bits = (int)Math.Log(x.Length, 2);

        for(int k = 0; k < x.Length; k++)
        {
            r[Rev(k, bits)] = x[k];
        }

        return r;
    }

    private cplx Omega(int m)
    {
        float x = (- 2 * (float)Math.PI) / m;

        return new cplx((float)Math.Cos(x), (float)(Math.Sin(x)));
    }

Answer 1

我应该在使用 Math.Log() 时使用 log2(n)。