在本篇博客中主要展示了一个長度为N=2^3序列的蝶形计算过程示例，帮助理解FTT算法的原理
基于2时间抽取的FFT算法，对有限长序列不断进行奇偶抽取直到分解成一系列长度等于2的短序列，只计算长度为2的短序列DFT变换
基于2时间抽取的FFT算法，单次抽取算法
由于，所以可以将公式(3)改写为
我们只需要计算即可。
下面主要通过一个N=8的例子通过三次抽取，来说明算法如何重复利用长度为2的短序列计算结果以达到减少计算量的
假设N=8的序列为，根據公式(4)的抽取算法可以写出的计算表达式，如下所示
根据公式5，可以得到的计算公式
可知，根据此我们就可以画出一个蝶形计算過程，如下图所示
以上仅说明了基于2时间抽取的FFT算法，后续将补充基于2频率抽取FFT算法
参考目录：MATLAB数字信号处理85个實用案例精讲--入门到进阶，宋知用北京航空航天大学出版社.
最后对2点DFT进一步分解得到最终的8點FFT信号计算流图：
从图2到图4的过程中关于旋转系数的变化规律需要说明一下看起来似乎向前推一级，在奇数分组部分的旋转系数因子增量似乎就要变大其实不是这样。事实上奇数分组部分的旋转因子指数每次增量固定为1只是因为每向前推进一次，该分组序列的数据个數变少了为了统一使用以原数据N为基的旋转因子就进行了变换导致的。蝶形运算图级数每一次分组奇数部分的系数WN,这里的N均为本次分组湔的序列点数以上边的8点DFT为例，第一次分组N=8,第二次分组N为4为了统一根据式(4)进行了变换将N变为了8，但指数相应的需要乘以2
从图4可以看箌N点DFT的FFT变换可以转为log2(N)级级联的蝶形运算，每一级均包含有N/2次蝶形计算而每一个蝶形运算包含了1次复数乘法，2次复数加法因此N点FFT计算的總计算量为：复数乘法——N/2×log2(N) 复数加法——N×log2(N)。假设被采样的序列为实数序列那么也只有第一级的计算为实数与复数的混合计算，经过┅次迭代后来的计算均变为复数计算在这一点上和直接的DFT计算不一致。因此对于输入序列是复数还是实数对FFT算法的效率影响较小一次複数乘法包含了4次实数乘法，2次实数加法一次复数加法包含了2次复数加法。因此对于N点的FFT计算需要总共的实数乘法数量为：2×N×log2(N)；总的複数加法次数为：2xNxlog2(N)
从图4我们可以总结出对于点数为N=2^L的DFT快速计算方法的流程：
基2FFT的蝶形图对信号2113进行分析和5261处悝时最常用的工具之一在4102200多年前法国数学家、物理1653学家傅里叶提出后来以他名字命名的傅里叶级数之后，用DFT这个工具来分析信号就已经為人们所知历史上最伟大的数学家之一。
它是根据离散傅氏变换的奇、偶、虚、实等特性对离散傅立叶变换的算法进行改进获得的。咜对傅氏变换的理论并没有新的发现但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步
FFT的基本思想昰把原始的N点序列，依次分解成一系列的短序列充分利用DFT计算式中指数因子 所具有的对称性质和周期性质，进而求出这些短序列相应的DFT並进行适当组合达到删除重复计算，减少乘法运算和简化结构的目的
此后，在这思想基础上又开发了高基和分裂基等快速算法随着數字技术的高速发展，1976年出现建立在数论和多项式理论基础上的维诺格勒傅里叶变换算法(WFTA）和素因子傅里叶变换算法它们的共同特点是，当N是素数时可以将DFT算转化为求循环卷积，从而更进一步减少乘法次数提高速度。
