3.4 快速傅里叶变换
快速傅里叶变换（FFT）是为提高DFT运算速度而采用的一种算法。
对一个有限长度序列x(n)的N点的DFT为：X（k）=∑x（n）W^knN (k=0,1,……，N-1；n=0,1,……，N-1;W=e^-j2π/N)
当N=4时，X（k）可展开为：
X（0）= x（0）W^0*4+ x（1）W^0*4 +x（2）W^0*4+ x（3）W^0*4 X（1）= x（0）W^0*4+ x（1）W^1*4 +x（2）W^2*4+ x（3）W^3*4 X（2）= x（0）W^0*4+ x（1）W^2*4 +x（2）W^4*4+ x（3）W^6*4 X（3）= x（0）W^0*4+ x（1）W^3*4 +x（2）W^6*4+ x（3）W^9*4
从上式可以看出,要求4点的DFT,需要16次的复数乘法运算,12次复数乘法运算算。由此类推，要求出N点的DFT，需要N^2次复数乘法运算，N*(N-1)次复数加法运算。当N值较大时，要完成的复数乘法运算和复数加法运算得次数都非常多，无论是用通用计算机还是用DSP芯片，都需要消耗大量的时间，不适合于对实时处理要求高的场合。为了能实时处理DFT,要想减少DFT的运算量可以有两个途径：
第一是降N，N的值减小了，运算量就减少了；第二是利用旋转因子的周期性和对称性，可约性。利用这两个途径实现DFT的快速傅里叶变换（FFT），FFT算法基本上可分为时域抽取法和频域抽取法。 W=e^-j2π/N的性质：
（1）周期性
kn(k N)nk(n N)
WN WN WN
kn( k)n*k( n)*
（2）共轭对称性 WN [WN] [WN]knmkn（3）可约性 WN WmN,
knkn/m
WN WN/m
本程序是用基2的按时间抽取的FFT算法（DIT-FFT），设序列x(n)的长度为N，且N满足N=2^M,M为正整数。若N不能满足上述关系，可以将序列x(n)补零实现，则x(n)的N点DFT为：
X（k）=∑x（n）W^knN (k=0,1,……，N-1；n=0,1,……，N-1;W=e^-j2π/N)将n分为奇数与偶数两部分。
按时间抽取基2-FFT算法的基本思路是将N点序列按时间下标的奇偶分为两个N/2点序列，计算这两个N/2点序列的N/2点DFT，计算量可减小约一半；每一个N/2点序列按照同样的划分原则，可以划分为两个N/4点序列，最后，将原序列划分为多个2点
第 8 页 共 23页