数字信号处理（二）|快速傅里叶变换

快速傅里叶变换(FFT)

一、FFT出现的原因

进行x（n）的N点离散傅里叶变换运算，则总共包含N²次乘法运算和同样数量次数加法操作。
当取样点数为1024时，则所需总运算量达到约2,097,152次（即2 \times 1048576），这使得单纯的直接算法在实际应用中显得过于笨重。
快速傅里叶变换通过将长序列分解为较短子序列的离散傅里叶变换，并巧妙利用WNkn所具有的周期性和对称性特性来降低整体运算复杂度。

二、DIT-FFT

（1）8点DFT一次时域抽取分解运算

在进行一次分解之后，在完成1次长度为N的快速傅里叶变换（DFT）运算时，则需分别完成两个长度为N/2的DFT运算以及执行N/2个蝶形运算。对于每个长度为N/2的子过程而言，在完成其内部运算时将涉及(N/4)²次复数乘法操作以及(N)(N-1)/8次