FFT算法杂整

FFT算法是计算DFT的高效算法。算法最初由J.W.Cooley和J.W.Tukey于1965年提出，之后又有新的算法不断涌现，总的来说发展方向有两个：一是针对N等于2的整数次幂的算法，如基2算法、基4算法和分裂基算法等； 另一个是N不等于2 的整数次幂的算法，如素因子算法、Winograd算法等。其中基2算法是目前所常用的FFT算法，其核心思想是将N点的序列逐次分解为(N-1)/2点，最后分解为2点DFT进行计算，从而消除DFT中大量的重复运算。

FFT算法可从时域或频域对序列进行分解：
①时间抽取法(DIT)，即直接将序列x(n)按奇、偶逐次分成奇数子序列和偶数子序列，然后通过计算子序列的DFT来实现整个序列的DFT；

② 频率抽取法(DIF)，即将频域X(k)的序号k按照奇、偶逐次分解成偶数点子序列和奇数点子序列，然后计算子序列的DFT，得到整个频域内的DFT。

时间抽取法和频率抽取法的计算复杂程度和所需要的计算量都是相同的，且由两种方法不同的分解形式可知：时间抽取法需要对输入数据序列x(n)进行重新排序，频率抽取法需要对输出数据序列X[k]进行进行排序。