快速傅里叶变换FFT的实现分析
首先列出DFT变换的公式，然后分别从时间分离和频域分离两种方式描述。
1，有限长序列的傅里叶变换对如下：
2，时间域基2快速算法推导
方法就是对原始序列的奇数点和偶数点拆分，形成两个子序列，然后再进行DFT运算。假定原始序列的长度N为2的L次幂。
原则上上式中的k的范围是0~N-1，如果将范围限制到0~N/2-1，那么上式成为正变换前半部分的结果。而后半部分为：
如果令x1(n)=x(2r)，x2(n)=x(2r+1)，N1=N/2，那么变换结果可以如下表示
,前半部分
,后半部分
进一步简化可得
,前半部分
,后半部分
下面以N=8举例画出示意图，如下：
进一步对DFT 4进行二分，那么裂变示意图变为如下：
进一步对DFT 2进行二分，那么裂变示意图变为如下：
3，频率域基2快速算法推导
方法就是对原始序列前后一半拆分，形成两个子序列，然后再进行DFT运算。假定原始序列的长度N为2的L次幂。
将X(k)分成奇偶点，则
再次转化一下
化简得到如下
下面以N=8举例画出示意图，如下：