VC++的FFT编程设计+文献综述(2)
1.2.2 离散傅里叶变换（DFT） 2
1.2.3 快速傅里叶变换（FFT） 3
1.3 FFT算法的分类 5
1.3.1 基2、DIT-FFT（按时间抽取） 6
1.3.2 基2、DIF-FFT（按频率抽取） 11
1.3.3 基4、DIF-FFT(按频率抽取) 12
1.3.4 分裂基FFT算法 13
1.3.5 分裂基FFT算法的运算量 19
1.3.6 N为组合数的FFT——混合基算法 20
1.3.7 Chirp-z变换 23
1.3.8 Visual Studio 6.0 的应用与介绍 25
2 分析 30
2.1 变址倒序 30
2.2 蝶形级递推运算 32
2.3 系数W_N^r的求得 32
3 设计 33
3.1 变址 33
3.2 L级递推计算 35
3.3 输入输出 38
4 结论 45
4.1 设计结果 45
4.2 调试运行 54
4.3 总结 60
致谢 61
参考文献 62
绪论
1965年，库利（J.W.Cooley）和图基（J.W.Tukey）在《计算数学》杂志上发表了“机器计算傅立叶级数的一种算法”的文章，这是一篇关于计算DFT的一种快速有效的计算方法的文章。它的思路建立在对DFT运算内在规律的认识之上。这篇文章的发表使DFT的计算量大大减少，并导致了许多计算方法的发现。这些算法统称为快速傅立叶变换（Fast Fourier Transform），简称FFT，1984年，法国的杜哈梅尔（P.Dohamel）和霍尔曼（H.Hollmann）提出的分裂基快速算法，使运算效率进一步提高。FFT即为快速傅氏变换，是离散傅氏变换的快速算法，它是根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。 随着科学的进步，FFT算法的重要意义已经远远超过傅里叶分析本身的应用。FFT算法之所以快速，其根本原因在于原始变化矩阵的多余行，此特性也适用于傅里叶变换外的其他一些正交变换，例如，快速沃尔什变换、数论变换等等。在FFT的影响下，人们对于广义的快速正交变换进行了深入研究，使各种快速变换在数字信号处理中占据了重要地位。因此说FFT对数字信号处理技术的发展起了重大推动作用。
FFT算法的研究与发展
近十多年来数字信号处理技术同数字计算机、大规模集成电路等先进技术一样，有了突飞猛进的发展，日新月异，已经形成了一门具有强大生命力的技术科学。由于它本身具有一系列的优点，所以能有效地促进各工程技术领域的技术改造和学科发展，应用领域也更加广泛、深入，越来越受到人们的重视。 在数字信号处理中，离散傅里叶变换(Discrete Fourier Transform, DFT)是常用的变换方法，它在各种数字信号处理系统中扮演着重要的角色。快速傅里叶变换〔Fast Fourier Transfonn, FFT〕并不是与离散傅里叶变换不同的另一种变换，而是为了减少DFT 计算次数的一种快速有效的算法。 傅里叶变换已有一百多年的历史了，我们知道频域分析常常比时域分析更优越，不仅简单，且易于分析复杂信号。但用较精确的数字方法，即 DFT 进行谱分析，在FFT 出现以前是不切实际的。这是因为 DFT 计算量太大。直到 1965 年出现了FFT。 应该指出，当时电子数字计算机的条件也促成了这个算法的提出。1967 年至 1968年间 FFT 的数字硬件就制成了。至此 DFT 的运算大为简化，运算时间一般可降低 1-2个数量级。因而各个科学技术领域广泛地采用了 FFT 技术，它大大推动了近 30 年来信号处理技术的发展，成为数字信号处理应用领域强有力的工具，广泛应用于雷达、声纳、通信、地质劫探、图像处理、生物医学等领域中。 Sande 提出了按照频率抽取的 FFT 算法，Bergland 提出了采用高基数结构的算法,Winograd 博士提出的，可以称为 WFTA 算法，Rader 和 Brenner 提出的余割因子算法，王中德提出的对称分解法，Vetlerli 和 Nussbaumer 提出的 DFT DCT 算法，其中最具代表性的是法国的 Duhamel 和 Hollman 提出的分裂基算法。各种 DFT 的快速算法，都利用了 nk N W 的周期性和对称性，通过将一个大点数N的 DFT分解为若干小点数的DFT的组合,来减少运算量。
上一篇：留守儿童文献综述和参考文献