快速傅里叶变换：按时间抽取的数学表达

图3.2.4 序列的倒序程序框图

上节讨论中提出序号n可以用二进制码来表示，那么N点的离散傅里叶变换运算表示式也可以用二进制的形式来表示。对于N点的离散傅里叶变换，N=2^m，序号n可用m位二进制码表示，即

n=n₀+n₁2+n₂2²+…+n_m-12^m-1 （3.3.1）

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

同样，任意k=0，1，…，N-1

k=k₀+k₁2+k₂2²+…+k_m-12^m-1 （3.3.2）

式中，k_r取0或1（r=0，1，…，m-1）。k_r就等于k的第r比特的值（第0比特对应最低位）。变换基

其中，利用了

根据离散傅里叶变换的定义

式中，

这相当于把序列从中间分成两个子序列，

把k分成奇数和偶数两部分，则通过上式组合得到两个N/2点的序列，即

G₁[n]=x[n]+W¹₂x[N/2+n]=x[n]-x[N/2+n] （3.3.7）

G₀[n]=x[n]+W⁰₂x[N/2+n]=x[n]+x[N/2+n] （3.3.8）

奇偶由最低比特的值决定，0为偶数，1为奇数。式（3.3.7）和式（3.3.8）可写成统一的表达式

G_k0[n]=x[n]+W^k0₂x[N/2+n] （3.3.9）

分别对这两个系列作进一步处理可以得到原序列的离散傅里叶变换。第二步处理为

式中，

与第一次一样，式（3.3.11）相当于把序列从中间分成两个子序列，即

当序列G_k0[n]给定后，则k₀也确定，故式（3.3.12）中的k只有两种取值情况，即k₁为0或1，可以用下式把这两种情况写成统一的形式，即

根据k₁的取值，可以得到两种情况，即

分别对式（3.3.14a）和式（3.3.14b）描述的两个序列作进一步的处理，可以得到原序列的离散傅里叶变换。下面讨论第l步，已经得到第（l-1）步的输出序列为(www.xing528.com)

于是进一步计算的离散傅里叶变换有

式中，

式（3.3.17）中，。

由于给定后，k_l-2…k0已知，所以式（3.3.17）的k只有两种情况，即k_l-1为0或1，写成统一表达式为

根据k_l-1的取值，可以得到两种情况，即

式（3.3.19a）和（3.3.19b）构成了快速傅里叶变换算法中的基本单元，称为蝶形运算，如图3.3.1所示。

图3.3.1中，为两级蝶形图之间的旋转因子。根据这个基本蝶形就可以画出任意2的整数次幂点数的快速傅里叶变换的完整的蝶形图。下面仍以8点为例，详细给出每一步的蝶形图和最终的蝶形图。

第一步：

蝶形图如图3.3.2所示。

图3.3.1 DIT-FFT蝶形运算图

图3.3.2 N=8的第一步分解

第二步：

蝶形图如图3.3.3所示。

第三步：

以上三步，每一步都要完成4个蝶形运算，完整的蝶形图如图3.3.4所示。

图3.3.3 N=8的第二步分解

图3.3.4 N=8的第三步分解

可见输入是比特倒序的，最后一步序列的下标正好是k的二进制表示。也可以把蝶形重排变成输入正序，而输出倒序的蝶形图。

对于N点快速傅里叶变换，上述过程一共要执行m=log₂N步，每步有N/2个蝶形运算，每个蝶形运算中需要一次复数乘法和两次复数加法，所以这种快速傅里叶变换算法所需要的计算量为次复数乘法和Nlog₂N次加法。

根据按时间抽取的快速傅里叶变换运算规律可以得出用软件实现时的编程框图，如图3.3.5所示。运算从第一级开始，逐级进行，共运行m级。在进行第l级运算时，依次求出2^l-1个不同的旋转因子，每求出一个旋转因子就计算完它所对应的所有2^m-l个蝶形运算，整个流程通过三层循环完成。最内一层循环用以计算具有相同旋转因子W_N^r的蝶形结运算，中间一层循环是计算不同种W_N^r蝶形结运算，最外一层是控制整个m=log₂N级的顺序运算。