algorithm - DFT 和 FFT 之间有什么区别使 FFT 如此之快？

Question

我正在尝试理解 FFT，这是我目前所了解的:

为了找到波形中频率的大小，必须通过将波形乘以他们正在搜索的频率来探测它们，在两个不同的相位(sin 和 cos)中并对每个相位进行平均。阶段是通过它与两者的关系找到的，其代码如下所示:

//simple pseudocode
var wave = [...];                //an array of floats representing amplitude of wave
var numSamples = wave.length;
var spectrum = [1,2,3,4,5,6...]  //all frequencies being tested for.  

function getMagnitudesOfSpectrum() {
   var magnitudesOut = [];
   var phasesOut = [];

   for(freq in spectrum) {
       var magnitudeSin = 0;
       var magnitudeCos = 0;

       for(sample in numSamples) {
          magnitudeSin += amplitudeSinAt(sample, freq) * wave[sample];
          magnitudeCos += amplitudeCosAt(sample, freq) * wave[sample];
       }

       magnitudesOut[freq] = (magnitudeSin + magnitudeCos)/numSamples;
       phasesOut[freq] = //based off magnitudeSin and magnitudeCos
   }

   return magnitudesOut and phasesOut;
}

为了非常快速地对很多频率执行此操作，FFT 使用了很多技巧。

有哪些快捷方式可以使 FFT 比 DFT 快得多？

附言我曾尝试在网上查看完整的 FFT 算法，但所有技巧都倾向于浓缩成一段漂亮的代码，而没有太多解释。在我理解整个事情之前，我首先需要的是将这些有效变化中的每一个作为概念进行一些介绍。

谢谢。

Answer 1

参见 How to compute Discrete Fourier Transform?

想法是 N 点 DFT 离散和积分可以分成 2 个 N/2 点两半，其中两半都可以表示为 N/2 点 DFT 的函数，并进行一些小调整以将它们组合成最终结果。这导致每个整个数据集几乎需要一半的操作。如果你递归地应用这个，你得到 O(n.log2(n)) 而不是 O(n^2) 与天真的方法。

有 2 种众所周知的方法可以将等式拆分为两个相似的一半和，一种称为时间抽取，另一种称为频率抽取。 Booth 以代数方式拆分原始总和(利用 W 权重矩阵的对称性)，所以只需谷歌即可。

调整通常涉及将数据集分成偶数和奇数条目，或者使用涉及位反转的蝴蝶洗牌对它们重新排序 的索引顺序，可以非常快速地硬连线...用于HW DFFT 实现...有关更多信息，请参阅 Wiki Butterfly diagram