FFT函数的参数是什么意思

Question

我正在尝试了解 FFT 算法。这是代码

void fft(double *a, double *b, double *w, int m, int l)
{
    int i, i0, i1, i2, i3, j;
    double u, v, wi, wr;
    for (j = 0; j < l; j++) {
        wr = w[j << 1];
        wi = w[j << 1 + 1];
        for (i = 0; i < m; i++) {
            i0 = (i << 1) + (j * m << 1);
            i1 = i0 + (m * l << 1);
            i2 = (i << 1) + (j * m << 2);
            i3 = i2 + (m << 1);
            u = a[i0] - a[i1];
            v = a[i0 + 1] - a[i1 + 1];
            b[i2] = a[i0] + a[i1];
            b[i2 + 1] = a[i0 + 1] + a[i1 + 1];
            b[i3] = wr * u - wi * v;
            b[i3 + 1] = wr * v + wi * u;
        }
    }
}

如果没猜错，输入数组W，奇数为实数，偶数为虚数。 A 和 B 是复数结果的虚部和实部我还发现 l = 2**m

但是当我尝试这样做时：

double a[4] = { 0, 0, 0, 0 };
double b[4] = { 0, 0, 0, 0 };
double w[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };
int m = 3;
int l = 8;

fft(a, b, w, m, l);

有错误。

Answer 1

这段代码只是 FFT 的一部分。 a 已输入。 b 是输出。 w 包含预先计算的权重。 l是FFT中当前点的细分数。 m 是每分区的元素数。 a、b 和 w 中的数据是交错复数数据——数组中的每对 double 元素由一个复数的实部和虚部组成数.

代码对数据执行一基二蝶形传递。要使用它来计算 FFT，必须使用 l、m 的特定值和 w 中的权重多次调用它。因为，对于每个调用，输入在 a 中，输出在 b 中，调用者必须至少使用两个缓冲区并在它们之间交替以连续调用例程。

从 i0 和 i2 中执行的索引来看，数据似乎正在稍微重新排列。这可能旨在以“自然”顺序而不是简单实现中出现的位反转顺序生成 FFT 的最终结果。

But when i'm trying to do this:

double a[4] = { 0, 0, 0, 0 };
double b[4] = { 0, 0, 0, 0 };
double w[8] = { 1, 0, 0, 0, 0, 0, 0, 0 };
int m = 3;
int l = 8;
 
fft(a, b, w, m, l);

There's error.

从for (j = 0; j < l; j++)我们看到循环中j的最大值是l-1。从for (i = 0; i < m; i++)，我们看到i的最大值是m-1。然后在 i0 = (i << 1) + (j * m << 1) 中，我们有 i0 = ((m-1) << 1) + ((l-1) * m << 1) = (m-1)*2 + (l-1) * m * 2 = 2*m - 2 + l*m*2 - m*2 = 2*m*l - 2。在 i1 = i0 + (m * l << 1) 中，我们有 i1 = 2*m*l - 2 + (m * l * 2) = 4*m*l - 2。当代码使用a[i1 + 1]时，索引为i1 + 1 = 4*m*l - 2 + 1 = 4*m*l - 1.

因此 a 必须有一个索引为 4*m*l - 1 的元素，所以它必须至少有 4*m*l 个元素。 b 所需的大小可以类似地计算并且是相同的。

当您调用 fft 并将 m 设置为 3 且 l 设置为 8 时，a 必须有 4•3•8 = 96 个元素。您的示例代码显示了四个元素。因此，数组溢出，代码失败。

我不认为 l 应该等于 2^m 是正确的。更有可能的是，4*m*l 在同一个完整的 FFT 计算中对 fft 的调用之间不应发生变化，而且，因为 a 和 b 包含两个 double 元素复数，4*m*l 应该是被转换信号中复数元素数量的两倍。

FFT函数的参数是什么意思

What could parametrs of FFT function mean

c++

fft