离散信号：快速傅里叶变换算法

当组合数快速傅里叶变换算法中所有N_i都为4时，就是基4快速傅里叶变换。假定N=4^m，则任意n=0，1，…，N-1可以表示为

n=n₀+n₁4+…n_r4^r+…+n_m-14^m-1 （3.7.1）

式中，n_r（r=0，1，…，m-1）取0，1，2或3。事实上，上式是n的四进制表示，4是四进制数系统的基。n_r就等于n的第r位的值（第0位对应最低位）。

同样，任意k=0，1，…，N-1可以表示为

k=k₀+k₁4+…k_r4^r+…+k_m-14^m-1 （3.7.2）

式中，k_r（r=0，1，…，m-1）取0，1，2或3。k_r就等于k的第r位的值。

变换基为

离散傅里叶变换为

式中

令(www.xing528.com)

把k的最低位分成0、1、2、3这4种情况，则通过上式组合我们得到4个N/4点的序列

如此重复把序列分为4个子序列，直至序列长度为1止。先讨论其中第l步，（（k））_4l-1已知，可得到

令n=n′并化简得

式中，k_l-1取0、1、2、3构成了基4快速傅里叶变换算法的基本单元，称为蝶形运算，其图形如图3.7.1所示。

图3.7.1 基4-FFT基本蝶形运算图

根据这个基本蝶形就可以画出任意4的整数次幂点数的快速傅里叶变换的完整的蝶形图，并且最后一步序列的下标的奇偶序列正好是k的四进制表示。

对于N点基4快速傅里叶变换，上述过程一共要执行m=log₄N步，每步有N/4个蝶形运算，每个蝶形运算中需要3次复数乘法和12次复数加法，所以这种快速傅里叶变换算法所需要的计算量为次复数乘法和次加法。可见，基4快速傅里叶变换算法比基2快速傅里叶变换算法复数乘法次数减少了25%，但是复数加法次数增加了50%。