基2与基4时分FFT算法浅析及其比较

　　FFT 算法的实质是把一长序列的 DFT 计算分割为较短序列的 DFT 计算，对于基2算法而言，是把序列每次一分为二，最后分割成两点 DFT，也可以采用别的分割法，每次一分为三，四，五等，就得到了基3，基4，基5等算法，其中基4算法由于具备某些优点，应用价值较大。然而许多文献在阐述 FFT 算法时，重点都放在基2算法上，对于基4算法或者过于简略，或者比较晦涩

　　凡是可以利用傅里叶变换来进行分析、综合、变换的地方，都可以利用FFT算法及运用数字计算技术加以实现。FFT在数字通信、语音信号处理、图像处理、匹配滤波以及功率谱估计、仿真、系统分析等各个领域都得到了广泛的应用。但不管FFT在哪里应用，一般都以卷积积分或相关积分的具体处理为依据，或者以用FFT作为连续傅里叶变换的近似为基础。

　　离散傅里叶变换（DFT）

　　为了再科学计算和数字信号处理等领域使用计算机进行傅里叶变换，必须将函数定义在离散点而非连续域内，且满足有限性或周期性条件。这种情况下，使用离散傅里叶变换。

　　

　　快速离散傅里叶变换（FFT）

　　快速傅里叶变换计算离散傅里叶变换的一种快速算法，简称FFT。快速傅里叶变换是1965年由J.W库利和T.W.图基提出的。采用这种算法能使计算机计算离散傅里叶变换所需要的乘法次数大为减少，特别是被变换的抽样点数N越多，FFT算法计算量的节省就越显著。

　　基2时分蝶式运算定理

　　

　　

　　

　　多基时分蝶式运算定理

　

　　DFT的直接算法

　　算法

　　直接按DFT的定义式进行计算：

　　按照DFT的定义式有

　　

　　通常所遇到的序列都是实序列，因此

　　

　　复杂度分析

　　在整个计算过程中，若不考虑正弦函数和余弦函数的计算量，则直接计算N 点DFT所需要的复数乘法次数M，，和复数加法次数A。，由（1.1.1） 式容易求得

　　Mｃ=N2 （2.2.1）

　　Aｃ=N（N- 1）≈N 2 （2.2.2）

　　由于x（n）是实序列，而仅仅Wk 是复数，因此。上述复数乘法实际上是实数和复数相乘。易知，这样的- -次复数乘法相当于两次实数乘法。因此，所需要的实数乘法次数

　　Mｒ=2N 2 （2.2.3）

　　由于1次复数加法运算相当于2次实数相加，因此所需要的实数加法次数

　　Aｒ=2N（ N I）≈ 2N 2 （2.2.4）

　　在x（n）为复序列的一般情况下，由于两个复数相乘需要4次实数相乘和2次实数相加，因此与（2.2.1） 是相当的实数乘法次数为

　　Mｒ=4N2 （2.2.5）

　　同时需要的实数加法次数

　　A‘ｒ=2 N 2 （2.2.6）

　　考虑到（2.2.3） 式所需要的实数加法次数，因此，总共所需要的实数加法次数

　　Aｒ≈4N2 （2.2.7）

　　由此可见，无论是复数运算次数还是实数运算次数都表明，直接计算DFT 时的运算量与N‘成正比。当N较大时，如N=2048，运算量将是巨大的，运算时间长。

　　基2时分FFT算法

　　基本思想与原理

　　基2 FFT 算法是把长度N=2’的序列- 一分为二，将N点D FT 表示为两个N /2 点D FT的线性组合。然后再把N12点DFT- 一分为二，表示为两个N14点的DFT。如此重复下去，直至分解成两点DFT 的运算，两点DFT实际上只是加减运算。

　　1.3节中的基2时分蝶式运算定里是基2 时分FFT 算法的基础。相应的运算称为蝶式运算。相应的运算流图称为运算蝶。

　　基2时分蝶式运算定理表明： 若将任何- 一偶数点序列按n的奇偶性分为两个子列，则原序列的DFT 可由两子序列DFT的线性组合得到。

       

        

       

　　

　　

　　

　

　　

　　基2时分FFT算法和基4时分FFT算法的比较

　　

　　分别比较（5.2.1）式和（4.3.4）式与（5.2.2）式和（4.3.5）式，可以看出，基2时分FFT算法和基4时分FFT算法由相同的复数加法次数，但基4时分FFT算法的复数乘法仅为基2时分FFT算法的3/4。由此可见，基4时分FFT算法最好，基2时分FFT算法次之，DFT的直接算法最差。但由于基4时分FFT算法要求N=4’，相应的变换长度N更少，灵活性就不如基2时分FFT算法