一.快速傅里叶变换——时域抽取2FFT算法

基本出发点是利用旋转因子的对称性和周期性，将一个大的DFT分解成一些小的DFT来计算。

算法原理：设输入序列长为（M为正整数）,将该序列按时间顺序的奇偶分解为越来越短的子序列，称为基2按时间抽取的2FFT算法。

如序列长度不满足条件，可以加零补长，使其达到。

输入序列长为（M为正整数），。

第一步：分组和变量置换

，，将按奇偶分成两组：

第二步：带入DFT定义式

第三步：求子序列的DFT

（有的资料写。）

其中，和分别为和的点DFT，式中：

。

因为和均以为周期，且，

  ，

  ，

至此，一次时域抽取法的理论推导就完成了，从上面的两个式子中，我们定义一种新的运算符，蝶形运算符：

用同样的方法，我们可以得到：

  ，

  ，

  ，

  ，

二.DIT-FFT与直接DFT运算量的比较

1.DIT-FFT

从上面的蝶形算法，当时，其运算应该有M级蝶形，每一级都由个蝶形运算构成。因此每一级运算都需要

次复数乘法和N次复数加法，所以M级蝶形运算的乘法次数为：

2.直接DFT运算

取定的一个值至少需要次复数乘法和次复数加法，而K的取值有个，所以总的时间复杂度为次复数乘法和次复数加法。

3.FFT算法与直接计算DFT所需乘法次数比郊曲线

---

注：本文整理网上资料，包括知乎、博客等，如有侵权立刻删除。