你可能想看看：

Tran-Thong，“快速傅里叶变换的代数公式”，IEEE 电路与系统杂志，第一卷。3，没有。2，1981 年 6 月，第 9-19 页。

作者描述了 16 种“基本”FFT 算法——8 种及时抽取和 8 种频率抽取，也按以下分类：输入顺序、输出顺序和特征（或几何：就地、相同输出、相同输入、或等几何）。很明显，在 FFT 的结尾（或开头）并不总是需要位反转。

此外，还有其他 FFT 算法无法用上述方案整齐地定义，例如 Rabiner 和 Gold 的书的第 10 章所示：“数字信号处理的理论和应用”，Englewood Cliffs，NJ，Prentice-Hall， 1975 年。

此外，有可能推导出其他算法，这些算法将无视任何形式的简单分类。

然而，尽管存在许多差异（对实施有很大影响），但还是可以从 Tran-Thong 论文中收集到一些简单的基本思想。例如，从那篇论文中的任何一个图表开始，很容易证明所有其他相同抽取类型的图表都可以通过简单的图形操作得到。类似地，可以通过将旋转因子分解为公共因子来改变抽取（例如：旋转 3 = 旋转 1 乘以旋转 2），然后将蝶形输入腿上的公共旋转因子移动到输出（反之亦然）。同样，很容易看出如何将四个连接的 radix-2 蝴蝶重新绘制为单个 radix-4 蝴蝶（当然，使用适当的输出顺序）。

FFT 是一个非常图形化的东西。很多时候，一些作者将其变形为丑陋和困难的东西。它不是。

radix-2 FFT 的典型实现需要在开始或结束时进行置换的一个原因是在使用过程/顺序处理引擎时减少对任何临时存储器的使用。当对输入、输出和中间结果使用一个大于 CPU 寄存器集的单个复杂数组时，中间蝶形结果必须位于该数组中的某个位置。但是最适合非置换结果的位置可能仍然被未处理的输入数据占据。因此，您可以使用更多内存将未处理的输入保存在其他地方，使用更多内存将中间结果放在其他地方，或者只是将结果放在不再需要输入数据的数组位置（例如蝶形输入位置） .

如果您为每个 FFT radix-2 层分配一个全新的数组，则不需要后洗牌。您也可以 ping-pong 2 数组，但这仍然是内存的两倍。

如果您有足够多的并行 ALU 单元，不需要临时结果，并且整个 FFT 结果可以在 ALU 输出上一次获得，那么您也可以写出没有任何排列的 FFT 结果。