一种常见的误解是，所有 FFT 算法都要求其输入的长度是 2 的幂。radix-2 Cooley-Tukey算法是第一个广为人知的算法，它有这个限制，但也有混合基数的版本不需要 2 次方输入的算法。除了 Cooley-Tukey 之外，还有许多其他 FFT 算法对其输入大小有不同的要求；甚至还有像Rader 算法这样的技术可以处理大小为素数的输入。

良好的通用 FFT 实现（如 MATLABfft()或FFTW）支持广泛的算法，并选择最适合特定情况的算法。有关细节的更多详细信息，请转到 MATLAB 文档本身：

> doc fft

算法

FFT 函数（fft、fft2、fftn、ifft、ifft2、ifftn）基于名为 FFTW [3]、[4] 的库。为了在 N 为复合时（即 N = N1N2）计算 N 点 DFT，FFTW 库使用 Cooley-Tukey 算法 [1] 分解问题，该算法首先计算 N1 个大小为 N2 的变换，然后计算 N2大小为 N1 的变换。分解递归地应用于 N1 点和 N2 点 DFT，直到可以使用几个机器生成的固定大小“codelet”之一来解决问题。小码又组合使用几种算法，包括 Cooley-Tukey [5] 的变体、素因子算法 [6] 和拆分基数算法 [2]。N 的特定因式分解是启发式选择的。

当 N 是素数时，FFTW 库首先使用 Rader 算法 [7] 将 N 点问题分解为三个 (N – 1) 点问题。然后，它使用上述 Cooley-Tukey 分解来计算 (N – 1) 点 DFT。

对于大多数 N，实输入 DFT 需要的计算时间大约是复数输入 DFT 的一半。但是，当 N 具有较大的质因数时，速度差异很小或没有。

fft 的执行时间取决于转换的长度。对于 2 的幂，它是最快的。对于只有小的素因数的长度，它几乎一样快。对于素数或具有大素因数的长度，它通常慢几倍。

注意 您可以使用实用函数 fftw 来提高 fft 的速度，该函数控制用于计算特定大小和维度的 FFT 的算法的优化。

参考

[1] Cooley, JW 和 JW Tukey，“复杂傅里叶级数机器计算的算法”，计算数学，卷。19，1965 年 4 月，第 297-301 页。

[2] Duhamel, P. 和 M. Vetterli，“快速傅立叶变换：教程回顾和最先进的技术”，信号处理，卷。19，1990 年 4 月，第 259-299 页。

[3] FFTW ( http://www.fftw.org )

[4] Frigo, M. 和 SG Johnson，“FFTW：FFT 的自适应软件架构”，国际声学、语音和信号处理会议论文集，卷。3，1998，第 1381-1384 页。

[5] Oppenheim，AV 和 RW Schafer，离散时间信号处理，Prentice-Hall，1989 年，p。611。

[6] Oppenheim, AV 和 RW Schafer，离散时间信号处理，Prentice-Hall，1989 年，p。619.

[7] Rader, CM，“数据样本数为素数时的离散傅立叶变换”，IEEE 会议记录，卷。56，1968 年 6 月，第 1107-1108 页。

在简短的教科书章节中解释的最简单的 FFT 递归地将 DFT 长度乘以 2，log2(N) 倍，因此似乎只适用于 2 的幂的长度。但您不必递归地除以 -一直征服到最后两个元素，您也可以使用相同的基本算法将长度除以其他小因素，例如 3 或 5 等。因此，“时间”（实际上是算术操作数）任何可以分解成许多微小质因数的长度的复杂度大致相同。

对于需要较长教科书章节的较大素数，还有其他方法。

因此，最先进的现代 FFT 库（FFTW、Accelerate/vDSP 等）可以处理除 2 的幂之外的许多长度。无论如何，现代处理器的实际执行时间顺序更多是由于数据缓存和指令调度问题不仅仅是算术运算的数量，所以必须做很多其他的事情来计算快速 DFT 等价物，而不仅仅是 radix-2 减少。Matlab 使用这些现代库之一。

但是许多简单的规范外观（学生练习、最少的代码行等）FFT 仅使用短的教科书章节方法来处理长度为 2 的幂（并忽略 CPU 缓存等问题）。这些短 FFT 在指令内存非常有限的较旧或微型处理器上也很有用。因此普遍存在误解。

大多数“FFT”算法的基本思想是将非素数长度 N = KM 序列的 DFT 分解为长度为 K 序列的 M DFT 和长度为 M 序列的 K DFT，并通过 N 个复数“旋转因子”乘法互连。

由于直接实现的乘法复杂度为 N^2，因此得到的复杂度为 MK^2 + KM^2 + N = N(K + M + 1)，因此 N > K + M + 1 将节省成本。现在， K 和 M 可能会再次分解，依此类推。如果不是，则直接评估 DFT（长度为 2 非常简单）。

如果 N 是素数，还有其他方法，Bluestein、Rader 等。

如果 M 和 K 互质，则可以避免旋转因子乘法，但代价是序列的排序更复杂。

对于短（但长于两个）长度，在乘法方面有比直接评估更有效的方法，例如 Winograd 短长度 DFT。

有“分割基数”FFT 算法，它将长度分成两个以上的部分。FFTW 就是这种情况，它将序列拆分为长度为 N/2、N/4 和 N/4。