VC++的FFT编程设计+文献综述(4)
根据式（６），第L个数组中每个 的计算只依赖于上一个数组的两个数据这两个数据的标号相差 ，即 ，而且这两个数据只用于计算第L个数组中标号的数据（等号右端为二进制数）。当 分别取０和１时，分别有 。因此，用上一组的两个数据计算所得的两个新数据仍可储存在原来位置，计算过程中只需要N个存储器。将 与 称为第L个数组中的对偶结点对。计算每个对偶结点对只需一次乘法，事实上由式（６）可得
式中： ； 别为式（７）中 取０，１时对应的P值。因 ，于是对偶结点的 有如下关系：
,因此式（６）可表示为
P的求法：在 中，i写成二进制数 右移 位，就成为
颠倒位序得 式（５），前面的γ个等式，每个等式均对应一组数据进行计算，每组数据都有N/２对结点，根据式（９），每对结点只需作１次乘法和２次加法，因此，每组数据只需N/2次乘法和N次加法，因而完成γ组数据的计算共需Nγ/2次乘法和Nγ次加法
FFT算法的分类
DFT 分解法基本上分为两类：一类是将时间序列x(n) (n 为时间标号)进行逐次分解，由此得到的 FFT 算法称为按时间抽取(Decimation-in-time)算法，另一类是 将 傅 立 叶 变 换 序 列 X(k) (k为 频率标号)进行分 解 ，叫做按频率抽取（Decimation-in-frequency）算法。对这两种算法，库利—图基和桑德－图基进行了理论的推导，故又称为库利—图基〔Cooley－Tukey〕算法和桑德—图基(Sande－Tukey)算法。对每一算法，按基本的蝶形运算的构成又可分为基 2、基 4、基 8 以及任意因子等的 FFT 算法。不同基的 FFT 算法所需的计算量略有差异。之所以说略有差异是指并无数量级的差别，甚至无成倍的差别。只是某种基的算法比另一种省几分之几而已。表 1.3.1 列出了 N=4096 时各种基的 FFT 算法所需运算量的比较。
算法 实数乘法次数 实数加法次数
基2 81 924 139 266
基4 57 348 126 978
基8 49 156 126 978
基16 48 132 125 422
（表1.3.1 算法运算量的比较）
表 1.3.1 给出了N是2的任意次乘方时所需的运算量。这里假定每一种算法都以最有效的方法来完成尽可能多的计算。
从表格可以看出，一般地说，基数越高，总计算量愈少。但是我们不能光从运算量的角度来简单地判断说基数越高的算法越好。判断一个算法不仅要从计算量而且还应从算法的复杂性方面来加以考察。一般来说，基数愈高，算法本身也愈复杂。所以，选择算法要依据具体情况进行考虑。如考虑用何种语言设计程序，在什么机器上运行程序，或者采用何种逻辑器件和系统结构来构成FFT硬件等等。
本文只介绍最常见的几种算法，其中前两种算法，是本次设计主要采用的算法。
基2、DIT-FFT（按时间抽取）
为了将大点数的DFT分解为小点数的DFT运算，要求序列的长度N为复合数，最常用的是 的情况（M为正整数）。该情况下的变换称为基2FFT。下面讨论基2情况的算法。
先将序列x(n)按奇偶项分解为两组
将DFT运算也相应分为两组（因为 ）
其中 、 分别是 的N/2点的DFT
上一篇：留守儿童文献综述和参考文献