1

Kiss_fft是一个非常简单的 FFT 实现；这几乎是教科书。它通过分解 FFT 大小将较大的 DFT 分解为重复的较小 FFT。它针对基数 2、3、4 和 5 优化了蝶形函数。

2,3 和 5 蝴蝶是小素数，通常在因式分解时发现，但 radix-4 蝴蝶是一种优化的情况，与使用 radix-2 两次*相比，它节省了一些乘法。例如，对于 32 点 FFT，大小 32 被分解为 4x4x2 - 两个阶段kf_bfly4后跟一个kf_bfly2

但是，这意味着您只能拥有一个kf_bfly2阶段。如果您的 FFT 大小是 4 的倍数，那么您将不会有两个kf_bfly2阶段，而是一个kf_bfly4阶段。这也意味着该kf_bfly2函数适用于长度为 1 的“数组”。

在代码中，声明是

static void kf_bfly2(kiss_fft_cpx * Fout, const size_t fstride, const kiss_fft_cfg st, int m)

其中Fout是一个大小为 的“数组” m，即始终为 1。蝶形循环结束Fout，编译器当然无法进行数值分析来证明这一点m==1。但由于这是最后一只蝴蝶，它经常被称为。

Q1)我的分析正确吗？kf_bfly2确实是只用m==1?

Q2）假设这确实是一个错过的优化，有两种可能的方法。我们可以直接m从 中删除参数kf_bfly2，或者我们可以将因子分析更改为因子 32 为 2x4x4（向前移动kf_bfly2，对于大小为 4x4=16 的数组在顶层调用一次）。什么是最好的？

[*] radix-4 蝶形最终具有因子 +1、-1、+i 和 -i，它们可以被实现为加法和减法。请参阅为什么 Kiss_fft 的正向和反向 radix-4 计算不同？

4

1 回答 1

1

编辑

这个问题有一个一次性错误。该函数不遵循通常的约定；m==1是上限。输入实际上是一个长度为 2 的数组，而不是一个标量。以下答案的其余部分是正确的，并且确实可以进行优化

优化的代码（也适用于 C++）

GitHub

原始答案

要理解“m”的值，有助于理解 Kiss FFT 的工作原理：它通过分解 FFT 大小将大 FFT 递归地转换为更小的 FFT。并且有多种可能的因式分解：32 是 4x4x2，但也是 2x4x4。

现在m参数 inkf_bfly2和其他蝶形函数是以下所有因素的乘积。因此，再次以 32 为例，kf_bfly4将以 m=8 和 m=2 调用。

我认为这m=1是kf_bfly2因为在我的测试中它总是碰巧是最后一个因素，如果它是一个因素的话。如果您使用 221 点 FFT，则最后一个因子将是 17，而不是 2。

但是 34 被分解为 2x17，在这种情况下m==17. 这没有什么特别的原因，这恰好是kf_factor. 它通过检查来测试分解n%4, n%2, n%3, n%5, n%7, n%9, n%11 ...。当然，这不是最有效的方法。Checking n%9毫无意义，因为您之前已经找到了 3 的两个因数。

但是请注意，从n%4检查因素的角度来看是有自由的。我们可以简单地检查n%2最后。如果我们这样做，那么 34 将作为17x2而不是2x17. 这似乎是一个微不足道的优化，但它确实允许我们删除kf_bfly2. 此外，它现在只使用了第一个旋转因子——这很方便{1 + 0i}。所以唯一的乘法kf_bfly2也被消除了。

优化并不止于此 - 因为kf_bfly2现在要小得多，而且只有一个调用站点*，您的编译器可能会内联kf_bfly2到kf_work. 我们从改变的因式中知道2只能是最后一个因素，所以我们也可以停止递归kf_work。

TL;博士

当您更改分解顺序时，您会连续解锁多个优化。

  • * 脚注：有一种特殊情况，如果足够小，OpenMP 优化将使用多个线程作为顶层。将 2x17 FFT 转换为 17x2 FFT 将意味着不再使用第二个线程，但对于如此小的 FFT 来说无论如何这有点毫无意义。
于 2021-10-14T14:49:37.337 回答