2.2 FFT算法与DFT算法
由Cooley-Tukey提出的FFT算法是计算离散傅立叶变换(DFT)的高效率算法,它把运算量从O(N2)下降到O(NlogN)。FFT算法的出现使得实时处理日益复杂的信号处理算法变得更加有效可行。
DFT算法的计算公式:

式中,x(n)表示输入的离散数字信号序列,WN为旋转因子,X(k)为一组N点组成的频率成分的相对幅度。一般情况下,假设x(n)来自于低通采样,采样频率为fs,那么X(k)表示N个频率点的相对幅度。根据旋转因子WN的特性:
①WN的对称性

②WN的周期性

③WN的可约性

DFT算法的计算公式推导如下:(https://www.daowen.com)

式中,x1(r)=x(2r),x2(r)=x(2r+1),r=0,1,…,
。
经过整理可以得到如下DFT算法的迭代公式:

式中,X′N(k′)为偶数项分支的离散傅立叶变换,X″N(k″)为奇数项分支的离散傅立叶变换。
式(2-3)的计算过程可以用图2-1 的蝶形运算流图直观地表示出来。根据以上公式,8 点的DFT的分层迭代算法可以用图2-2 来表示。

图2-1 蝶形运算流图

图2-2 8点的DFT的分层迭代算法