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 快得多？

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

谢谢。

Answer 1

见How to compute Discrete Fourier Transform?

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

有两种众所周知的方法可以将等式拆分为两个相似的一半和，一种称为时间抽取，另一种称为频率抽取. Booth 以代数方式拆分原始总和（利用 W 权重矩阵的对称性），因此只需 google.

调整通常涉及将数据集拆分为 even 和 odd 条目，或者使用 butterfly shuffle 涉及 索引顺序的位反转 并且可以非常快速地硬连线...用于 HW DFFT 实现...有关详细信息，请参阅 Wiki Butterfly diagram

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

What are the differences between DFT and FFT that make FFT so fast?

algorithm

audio

waveform

fft

spectrum

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