matlab求kcf算法响应图_1周学FFT——第5天 时间抽选奇偶分解基-2 FFT算法
时间抽选奇偶分解基-2 FFT算法名字很长，其内容包括三部分内容：
时间抽选（Decimation-in-time，DIT）是指在时域内将序列进行分解；
奇偶分解是指按照n的取值将分为奇偶两组，目的是将计算1个N点的DFT转化为计算2个
点的DFT；
基-2（radix-2）是指，M为自然数，比如
就是符合基-2条件的。目的是可以一直进行奇偶分解直到将N点DFT分解为一堆2点DFT。
在不致混淆的时候，时间抽选奇偶分解基-2 FFT算法可简称为基-2 FFT算法。由于基-2可以最大限度的减少乘法运算次数，所以实际当中如果点数不满足基-2条件，可以人为在
基-2。
以下为算法的推导过程： 序列
若
根据周期性2，
设
则根据定义，
式（5）表示
而
所以将
将式（5）、（6）合并可得
式（3）、（4）、（7）就是基-2FFT算法的核心。
例子：
利用基-2 FFT算法求序列x(n)的N=4的DFT。
知乎对多行公式的支持简直一言难尽，没办法只能在其他地方再贴一遍：
1周学FFT——第5天 时间抽选奇偶分解基-2 FFT算法www.jianshu.com
另外，通过观察可以发现，计算
蝶形运算（butterfly operation）。
比如计算
再如计算
将N=4的基-2FFT算法全部的蝶形运算画在一起如下图所示：
一次标准的蝶形运算包含1次复数乘法和2次复数加法（或1次复数乘加和1次复数加法）。如上图所示，N=4的DFT需要4次蝶形运算，共计4次复数乘法，远少于传统DFT的16次复数乘法。更进一步，经过更一般的推导可知，基-2 FFT算法的时间复杂度为
习题
- 根据基-2 FFT算法求序列x(n)的8点DFT，并画出蝶形流程图；
- 设计matlab程序，实现基-2 FFT算法。