1、 毕毕 业业 设设 计（论计（论 文）文）开开 题题 报报 告告 设计设计( (论文论文) )题目：题目：基于时间抽取 FFT 算法的 DSP 实现 2011 年 12 月 20 日 毕毕 业业 设设 计（论计（论 文）开文）开 题题 报报 告告 1结合毕业设计（论文）课题情况，根据所查阅的文献资料，每人撰 写不少于 1000 字的文献综述： 一、课题研究的意义一、课题研究的意义 快速傅氏变换（FFT）是离散傅氏变换的快速算法，它是根据离散傅氏变换的 奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。有些信号在时 域上是很难看出什么特征的，但是如果变换到频域之后，就很容易看出特征了。
2、这 就是很多信号分析采用 FFT 变换的原因。另外，FFT 可以将一个信号的频谱提取出 来，这在频谱分析方面也是经常用的。FFT 的这种方法充分利用了 DFT 运算中的对 称性和周期性，降低 DFT 的运算量。当 N 比较小时，FFT 优势并不明显。但当 N 大 于 32 开始，点数越大，FFT 对运算量的改善越明显。比如当 N 为 1024 时，FFT 的 运算效率比 DFT 提高了 100 倍。在库利和图基提出的 FFT 算法中，其基本原理是先 将一个 N 点时域序列的 DFT 分解为 N 个 1 点序列的 DFT，然后将这样计算出来的 N 个 1 点序列 DFT 的结果进行组合，得到最初
3、的 N 点时域序列的 DFT 值。它对傅氏变 换的理论并没有新的发现，但是对于在数字系统中应用离散傅立叶变换，可以说是 进了一大步。随着对信号处理实时性的要求，研究进一步减少 fft 运算量、fft 的 具体实现是非常必要的。 二、国内外的研究现状二、国内外的研究现状 1、FFT 的发展史及其在信号处理中的重要地位 实际上，对于 FFT 这种基本的思想很早就由德国伟大的数学家高斯提出过， 在某种情况下，天文学计算（也是现在 FFT 应用的领域之一）与等距观察的有限集 中的行星轨道的内插值有关。由于当时计算都是靠手工，所以产生一种快速算法的 迫切需要。 而且，更少的计算量同时也代表着错误的机会更
4、少，正确性更高。高 斯发现，一个富氏级数有宽度 N=N1*N2，可以分成几个部分。计算 N2 子样本 DFT 的 N1 长度和 N1 子样本 DFT 的 N2 长度。只是由于当时尚欠东风计算机还没发 明。在 20 世纪 60 年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数 字信号处理的革命， 因而 FFT 发明者的桂冠才落在他们头上。 之后， 桑德 （G.Sand） -图基等快速算法相继出现，几经改进，很快形成了一套高效运算方法，这就是现 在的快速傅立叶变换（FFT）。这种算法使 DFT 的运算效率提高 1 到 2 个数量级， 为数字信号处理技术应用于各种信号的实时处理创造了良好的条
5、件，大大推进了数 学信号处理技术。1984 年，法国的杜哈梅（P.Dohamel）和霍尔曼（H.Hollamann） 提出的分裂基块快速算法，使运算效率进一步提高。 库利和图基的 FFT 算法的最 基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2 算法。在这 之后，又有一些新的算法，进一步提高了 FFT 的运算效率，比如基-4 算法，分裂基 算法等。这些新算法对 FFT 运算效率的提高一般在 50%以内，远远不如 FFT 对 DFT 运算的提高幅度。从这个意义上说，FFT 算法是里程碑式的。可以说，正是计算机 技术的发展和 FFT 的出现，才使得数字信号处理迎来了一个崭新的时代
6、。除了运算 效率的大幅度提高外，FFT 还大大降低了 DFT 运算带来的累计量化误差，这点常为 人们所忽略。 2、进一步减少 FFT 计算量的方法 研究进一步减少运算量的途径，以程序的杂度复换取计算量的进一步提高多类 蝶形单元运算： 在基 2 FFT 程序中，若包含了所有旋转因子，则称该算法为一类蝶形单元运算； 若去掉1=W r N 的旋转因子，则称之为二类蝶形单元运算；若再去掉的旋转因子 j=W r N ，则称为三类蝶形单元运算；若再处理，则称之为四类蝶形运算。我们将 后三种运算称为多类蝶形单元运算。显然蝶形单元越多，编程就越复杂，但当 N 较 大时，乘法运算的减少量是相当可观的。例如.N=4096 时，三类蝶形单元运算的乘 法次数为一类蝶形单元运算的 75%。旋转因子的生成在 FFT 运算中，旋转因子 )jsin(2sin-)Nmcos(2 =W m N ，求余弦和正弦函数值的计算量很大，所以编程时， 一种方法是在每级运算中直接产生，另一种方法是在 FFT 程序开始前预先计算好， 存放在数组中，作为旋转因子表，在程序执行过程中直接查表得
