基于时间抽取FFT算法的DSP实现 毕业设计(论文)开题报告-.doc

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