c# - 一维快速傅立叶变换

Question

下面是什么算法？

我从下面的源码中了解到的是:

1. dir为FFT的方向:forward=1,inverse=-1。
2. x 是实部
3. y为虚部

这里的m是什么？

如果 x = {1, 1, 1, 1, 0, 0, 0, 0}，并且 y = {0,0,0,0 ,0,0,0,0,0}，m 的值是多少？

        //Inplace 1D FFT
        public static void FFT1D(int dir, int m, ref double[] x, ref double[] y)
        {
            long nn, i, i1, j, k, i2, l, l1, l2;
            double c1, c2, tx, ty, t1, t2, u1, u2, z;
            /* Calculate the number of points */
            nn = 1;
            for (i = 0; i < m; i++)
                nn *= 2;
            /* Do the bit reversal */
            i2 = nn >> 1;
            j = 0;
            for (i = 0; i < nn - 1; i++)
            {
                if (i < j)
                {
                    tx = x[i];
                    ty = y[i];
                    x[i] = x[j];
                    y[i] = y[j];
                    x[j] = tx;
                    y[j] = ty;
                }
                k = i2;
                while (k <= j)
                {
                    j -= k;
                    k >>= 1;
                }
                j += k;
            }
            /* Compute the FFT */
            c1 = -1.0;
            c2 = 0.0;
            l2 = 1;
            for (l = 0; l < m; l++)
            {
                l1 = l2;
                l2 <<= 1;
                u1 = 1.0;
                u2 = 0.0;
                for (j = 0; j < l1; j++)
                {
                    for (i = j; i < nn; i += l2)
                    {
                        i1 = i + l1;
                        t1 = u1 * x[i1] - u2 * y[i1];
                        t2 = u1 * y[i1] + u2 * x[i1];
                        x[i1] = x[i] - t1;
                        y[i1] = y[i] - t2;
                        x[i] += t1;
                        y[i] += t2;
                    }
                    z = u1 * c1 - u2 * c2;
                    u2 = u1 * c2 + u2 * c1;
                    u1 = z;
                }
                c2 = Math.Sqrt((1.0 - c1) / 2.0);
                if (dir == 1)
                    c2 = -c2;
                c1 = Math.Sqrt((1.0 + c1) / 2.0);
            }
            /* Scaling for forward transform */
            if (dir == 1)
            {
                for (i = 0; i < nn; i++)
                {
                    x[i] /= (double)nn;
                    y[i] /= (double)nn;
                }
            }
        }

Answer 1

您发布的 FFT 的实现仅限于大小为 2^m 的输入。因此，这里的 m 间接指定了 FFT block 大小的大小。因此，对于您使用 x = {1,1,1,1,0,0,0,0} 和 y={1,1,1,1,0,0 ,0,0} 是大小为 8=2³ 的数组，m 将等于 3。

请注意，没有额外检查数组 x 和 y 的大小，因此请确保它们至少为该大小。