FFT算法研究及基2-FFT算法的C语言实现.doc

毕 业 设 计 论 文题 目：FFT算法研究及基2-FFT算法的C语言实现 学 院： 电气与信息工程学院 专 业： 电气工程及其自动化 姓 名： XXX 学 号： XXXXXX 指导老师： XXX 完成时间： 2015年06月01日 河南城建学院本科毕业设计（论文） 摘要 摘 要 离散傅立叶变换（DFT）常常用于计算信号处理。DFT算法可以得到信号的频域特性，因为该算法在计算上是密集的，长时间的使用时，计算机不能实时进行信号处理。所以DFT被发现之后的相当长时间内是没被应用到实际的项目。到了二十世纪六十年代中期一种新的计算方法被研究者发现出来，它就是FFT。FFT并不是一种新的获取频域特征的方式，而是离散傅里叶变换的一种快速实现算法。数字信号处理在当今科技发展中发展很迅速，不但是在传统的通信领域，其他方面也经常用到。利用快速傅里叶变换，实现了信号频域的变换处理。对于信号的处理，往往会和数学中的算法联系到一起。如果处理得当，将会对气象，地理信息等的发展，起到举足轻重的作用，同时对世界其他领域的发展有很大的促进作用。关键词: FFT算法，C语言，编译实现I河南城建学院本科毕业设计（论文） Abstract AbstractDiscrete Fourier Transform (DFT) is often used to calculate the signal processing to obtain frequency domain signals. DFT algorithm can get the frequency domain characteristics of the signal, because the algorithm is computationally intensive, long-time use, the computer is not conducive to real-time signal processing. So DFT since it was discovered in a relatively long period of time is not to be applied to the actual projects until a new fast discrete Fourier calculation method -FFT is found in discrete Fourier transform was able to actually project has been widely used. FFT is not a new way to get the frequency domain, but the discrete Fourier transform of a fast algorithm.Fast Fourier Transform (FFT) is a digital signal processing important tool that the time domain signal into a frequency-domain signal processing. matched filtering has important applications. FFT is a discrete Fourier transform (DFT) is a fast algorithm, it can be a signal from the time domain to the frequency domain. Some signals in the time domain is not easy to observe the characteristics of what is, but then if you change the signal from the time domain to the frequency domain, it is easy to see out of. This design is required to be familiar with the basic principles of FFT algorithm, based on the preparation of C language program to achieve FFT algorithm real number sequence.Keywords: FFT algorithm, C language compiler to achieve河南城建学院本科毕业设计（论文） 目录河南城建学院本科毕业设计（论文） 目录目 录摘 要IAbstractII目 录III1 引言11.1 课题背景11.2 FFT算法的现状11.3 研究内容21.4 论文的研究成果22 数字信号处理综述32.1 数字信号理论32.2 数字信号处理的实现32.3 数字信号处理的应用及特点43 基本理论63.1 FFT算法的基本概念63.1.1离散傅里叶变换（DFT）63.1.2 快速傅里叶变换（FFT）73.2 FFT算法的分类73.2.1按时间抽取（DIT）的FTT83.2.2 按频率抽取（DIF）的FTT123.2.3 快速傅里叶分裂基FFT算法153.2.4 N为组合数的FFT混合基算法173.3 傅里叶变换的应用204 基-2FFT算法的C语言实现及仿真214.1 码位倒序214.2 蝶形运算22结论23参考文献24附录A25附录B35致谢42III河南城建学院本科毕业设计（论文） 1 引言1 引言1.1 课题背景 离散傅里叶变换（DFT）可以将有限长序列的的频域也离散化成有现长序列，但是计算量很大，不利于应用于实际工程。直到1965年J.W.库利和T.W.图基提出了一种快速计算离散复傅里叶的计算方法，DFT的计算量减少了几个数量级，特别是被变换的抽样点数N越多，FFT算法计算量的就越少。快速傅立叶变换作为一种数学计算方法，已经被广泛地运用在几乎所有领域的频谱分析中，而且长久不衰，因为信号处理方法不分先进和落后之说。只有经典的和现代的之别，在实际系统中用得最好的方法就是实用的方法。换句话说信号处理方法与应用背景和目的的近程度是衡量信号处理方法优劣的唯一标准。快速傅里叶变换（FFT），它在当今的科技世界表现的很是活跃。无论是在信号分析中，还是应用在高科技领域中的不断发展研究中都占有很重要的位置。1.2 FFT算法的现状在过去的几十年里，数字信号处理技术，数字计算机，LSI等先进技术发展一直较快，日新月异，已成为科学技术里面具有强大的生命力。由于它本身具有许多优点，它可以有效地推动技术创新和各种工程学科的发展，在应用领域更加广泛，深入，越来越多的人们关注这一领域。在数字信号处理里，离散傅立叶变换（DFT）是一种常见的变换方法，它在各种各样的数字信号处理系统中占有很重要的位置。快速傅立叶变换（FFT)与离散傅里叶变换（DFT）不是两种不同的计算方法，FFT只是为了更快捷有效的计算离散傅里叶变换。傅立叶变换已经出现了一个多世纪，众所周知，信号的频域分析往往比时域分析更好，它不仅简单，易于分析较为复杂的信号。但有一个更准确的数值计算方法，就是利用离散傅里叶变换进行信号的频谱分析，但是由于DFT的计算量大，耗费更多的时间，此法没有很好地得到应用。直到二十世纪六十年代中期，一种更为便捷的算法出现即FFT，数字信号处理这门技术才得以快速的发展。应当注意的是，在二十世纪六十年代中后期的时候FFT在电子计算机的帮助下已经提出了，此时FFT的硬件电路部分也已可以制作了。在这个时候DFT运算较之以前减少了很多，计算的时间较之以前也大大减少。因此，FFT算法大量运用到各种学科和技术领域，信号处理技术在近半个世纪的时间里得到了很好地发展，变为数字信号处理这门学科在应用领域中功能强大的工具，广泛应用于各种领域里。1.3 研究内容研究FFT算法，掌握其原理，针对目前FFT算法的广泛使用，本文提出了（1） 设计出一个FFT算法的实验项目，用C语言来编译实现。（2） 为了验证该程序的准确性，用C语言仿真。1.4 论文的研究成果通过查阅图书等更深入的了解FFT算法，熟悉FFT算法的的基本原理，掌握FFT算法及应用，培养C语言编程能力，用C语言完成基2-FFT算法的C语言实现，最后使用C语言实现软件仿真。本次设计的程序又较强的适应性，对于有相关需求的相关，可以快速扩展。23河南城建学院本科毕业设计（论文） 2 数字信号处理综述 2 数字信号处理综述2.1 数字信号理论 数字信号的处理，在理论上所涉及的范围非常广泛。在数学领域中 ，不但在微积分、概率统计、随机过程，还在高等代数、数值分析和复变函数等等，都是它基本的工具，网络理论和信号以及系统等，均都是它的理论基础。在学科的发展上，数字信号处理不但和最优控制、通信理论以及故障诊断等紧密相连，近年来又成为了人工智能、模式识别以及神经网络等新兴的学科理论基础之一，其算法的实现不但和计算机学科紧密相连，而且与微电子技术密不可分。故可以说，数字信号处理是将经典的理论体系（如数学、系统）当作自己的理论基础。一般把二十世纪六十年代中期快速傅里叶（FFT）的出现，作为数字信号处理这门新学科的开端。在这几十年的发展中，数字信号处理这门学科本身已经基本形成了比较完整的理论体系。这些理论包括：（1）信号采集；（2）离散信号分析；（3）离散系统分析；（4）信号处理中的快速计算；（5）信号的估值；（6）滤波技术；（7）信号的建模；（8）信号处理中的特殊算法；（9）信号处理技术的实现；（10）信号处理技术的运用。上述10个方面可以看出有着千丝万缕的联系。把信号处理技术应用到实际工程项目中，并需要结合相应的算法来实现。随着科学技术的飞速发展，数字信号处理理的论不断丰富和完善各种新的算法，新理论不断被提出，在未来，数字信号处理的理论，会获得更快速发展。2.2 数字信号处理的实现数字信号处理的实现，大体上有如下几种方法：（1）在计算机上用使用者自己编写，或者使用现成的软件来实现。这种实现的方法多用于教学与科研，但是速度较慢。（2）用微控制器来实施。微控制器发展迅速，它的功能也非常强大。依靠微控制器的硬件环境与信号处理的软件可以在工程实践中使用，诸如数字控制，医疗设备。（3）使用专门的DSP芯片进行信号处理来实现。 DSP芯片比微控制器有一个更突出的优点，例如内部有乘法累加器，其工作方式采用并行结构，多总线，速度快，以适于指示信号处理等。信号处理技术应用于工程实际成为可能是由于DSP芯片的问世及飞速发展。（4）采用专用的DSP芯片。现在国际社会已推出的专门的DSP芯片进行卷积、FFT、FIR滤波、相关和其它专用的芯片，在芯片的硬件电路中实现软件算法，用户给定输出数据，其结果，可直接在输出端获得。2.3 数字信号处理的应用及特点数字信号处理技术有着非常广泛的应用领域。在声呐、雷达、地球物理、广播电视、消费电子、军事等众多领域都活的了极其广泛的应用，它有效地促进了众多领域的迅速发展。数字信号处理具有以下优点：（1）高可靠性、高精度性和高稳定性 在传输和处理过程中，数字信号用二进制数0和1的码字序列表示，而0和1又是用脉冲的有无或脉冲的正负表示，即使在有噪声干扰存在的情况下，只要能够判别出脉冲的有无和正负，就能够准确传输和处理0和1表示的数字序列，因此，这种表示几乎不受噪声和干扰的影响。（2）时分复用在数字信号相邻取样值之间，存在着比较长的空闲时间。在这个期间内，可以利用同一个数字信号处理设备来处理其他通道的信号，这就是所谓的时分复用的过程。（3）灵活、方便、易于集成在数字信号处理中，无论视频信号、图像信号和声音信号，还是其他任何信号，都统一由二进制数0和1表示成数字序列，数字序列可以很方便的进行保存、复制、剪裁、融合、加密、传输和处理。数字信号处理归结为对数字序列进行一序列运算，这些运算够成了各种数字信号处理算法。将数字信号处理算法编写成程序，可以在计算机上运行。（4）其他的独特优点数字信号处理还具有模拟信号处理完全不可能有的其他一些独特的优点。例如，利用数字滤波器组可以实现多速率信号处理；数字系统的级联不需要考虑负载匹配问题；能够处理如地震信号那样的非常低频率的信号，如果采用模拟信号处理，模拟元件的尺寸将大到无法容忍的地步。河南城建学院本科毕业设计（论文） 4 基-2FFT算法的C语言实现及仿真 3 基本理论3.1 FFT算法的基本概念离散傅立叶变换（DFT）是信号分析与处理中的一种重要的变换。DFT 的计算，需要作次复数乘法运算和次复数加法运算，当N比较大时，计算量就非常大，为了快速计算DFT，近几十年以来，科学工作者们对离散傅立叶变换的计算进行了大量的研究，提出了很多有效的快速计算DFT的方法。这些算法，称之为快速傅立叶变换（FFT）。快速傅立叶变换并不是不同于离散傅立叶变换的另一个变换，而是减少了DFT计算次数的一种快速的算法。其突出的优点是可以快速，更精确的，高效地完成DFT的计算。3.1.1离散傅里叶变换（DFT）随着科技发展的日新月异，人们对开发和应用频率分析技术充满了希望。先前进行一次频率分析，既费时又费力。今天，随着电脑的硬件设备工艺提升了很多，计算机的性能也不断提升，因此计算机的计算速度才变得越来越快。由于计算机不可以对连续的信号进处理，它只能处理一个有限的离散数据。为了便于使用计算机对傅立叶积分变换，计算机需要对连续信号进行采样和分析，从而产生一系列离散的数据。这个离散傅里叶变换，称为离散傅立叶变换，简称DFT。DFT 的定义：设x(n) 是一个长度为 N 的有限长序列，定义x(n) 的N点离散傅立叶变换为 式（3.1） 其中k=0，1,，N1X (k) 的傅立叶反变换为 式（3.2）其中n= 0,1,N-1在(式3.1)式和(式3.2)式中， x(n) 和 X(k)均可以是复数。因为在(式3.1)式和(式3.2)式的右边仅在指数上差一个符号，并相差一个比例因子 ，所以有关(式3.1)式计算步骤的讨论稍加修改可以直接用于(式3.2)式。3.1.2 快速傅里叶变换（FFT）二十世纪六十年代中期，Cooley和Tukey两人经过研究，提出了一种可以快速算出DFT的算法，那就是FFT。从此以后，在计算机上DFT的计算时间减少了很多。在随后的几十年中，研究员们经过更透彻的对FFT的研究，DSP这门学科才得以快速发展。由于不同的有限长序列选择的分解方法不同，因此就出现了一些不同的FFT算法，其基本算法是2DIT和基2DIF。快速傅里叶变换（FFT）是计算离散傅里叶变换（DFT）的快速算法。DFT的定义式为 = 式（3.3）在所有复指数值的值全部已算好的情况下，要计算一个需要N次复数乘法和次复数加法。要算出所有N点共需次复数乘法和次复数加法。即其计算量是与成正比的。旋转因子具有如下两个特性，可以使DFT运算量尽可能分解为多个小点数的DFT运算：（1）周期性：（2）对称性：利用旋转因子这两个性质，可以使DFT运算中的某些项合并，以便减少乘法的次数。例子：求当N4时，X(2)的值 通过合并，使乘法次数由原来的4次减少到现在的1次，因此运算量减少了。FFT算法有许多种表示形式，但从基本上可以分为两大类：一种是按时间抽取（DIT），另一种是按频率抽取（DIF）。3.2 FFT算法的分类DFT从基本上可以分为两类分解方法：一类是把时间序列x(n) 进行连续的分解，于是得到的FFT算法可以称之为按时间抽取的算法，另一类是把傅立叶变换序列X(k) (k为频率基准)进行连续的分解 ，叫做按频率抽取的算法。对于每一种算法，根据基本的蝶形运算的构成，又可把FFT算法分为基2、基 4、基8以及任意因子等的FFT 算法，FFT算法对于不同基所需要的计算量是有所不同的，之所以说有差异是指的是并没有数量级的差别。表3.1列出了 N=4096 时各种基的 FFT 算法所需运算量次数的的比较。 表3.1 算法运算量的比较算法实数乘法次数实数加法次数基281 924139 266 基457 348126 978基849 156126 978基1648 132125 422从上述表格可以看出，计算的时候基数和计算总量成反比。从计算量这一个角度进行判断显然是片面的，在计算中基数越高的算法越好。判断一个算法不仅需要从计算量本身而且还需从算法的复杂程度方面来加以分析。往往算法的复杂性伴随着计算中高基数而变化。所以，在选择算法分析的时候要视情况而定。3.2.1按时间抽取（DIT）的FTT基2FFT变换主要就是为了解决大数拆分成小点数DFT运算这个问题的，这时需要取（M为正整数、N为复合数）。对该算法讨论如下。视奇偶项把x(n)一分为二 将DFT运算也相应分为两组 （因为）其中、分别是的N/2点的DFT 式（3.4） 式（3.5） 至此，一个N点DFT被分解为两个N/2点的DFT。上面能将全部N点的求解出来。分析：和只有N/2个点（），只能求出的前N/2个点的DFT，要求出全部N点的，需要找出、和的关系，其中。是由式子可得 式（3.6）化简得，这样N点DFT可全部由下式确定出来： 上式可用一个专用的碟形符号来表示，这个符号对应一次复数乘法和两次复数加法运算图3.1蝶形运算符号DFT通过这样的分解以后，每一个点的DFT只需要次复数乘法两个N/2点的DFT需要次复乘，再加上将两个点DFT合并成为N点DFT时有次与W因子相乘，一共需要次复乘。可见，通过这样的分解，计算量就会减少很多。因为，且N/2仍然是偶数，因此就可以对两个N/2点的DFT再次分别作进一步的分解，于是将两个N/2点的DFT分解成两个N/4点的DFT。 例如对，可以在按其偶数部分及奇数部分进行分解： 则的运算可相应分为两组： 式（3.7）将系数统一为以为周期，即，可得 相同的，分解类似。经过分解后，DFT就只有2点，下图的蝶形符号表示其运算。依据时间抽取的分解的过程，下图是其完整的流程图：图3.2 8点的DFT分解图3.3 按时间抽取将一个N点的DFT分解为两个4点的DFT图3.4 一个N=8点DFT分解为4个2点的DFT图3.5 N=8按时间抽取的FFT运算信号流图“时间抽取法”就是在每一次分解时，其步骤是按有限长序列顺序在时域上的奇偶进行抽取。根据上面流图的分析，总共需要进行M次分解，于是构成了从x(n)至X(k)的M级运算过程。每一级的计算都是由N/2个蝶形运算构成的，因此每一级计算都需要N/2次复数乘法和N次复数加法，因此按时间抽取的M级运算后总共需要复数乘法次数：复数加法次数： 根据上面的运算流图，需要对FFT算法的两个特点来进行分析，这两个特点对FFT的软硬件造成的影响很大。（1）原位运算也叫做同址运算，计算过程中每一级蝶形的输入与输出在运算前后都可以存储在同一个地址上，直到最后输出，中间没有任何其它的存储器。根据运算流图分析原位运算是如何进行的。原位运算的这种结构可以为硬件节省存储单元，从而降低对计算机存储量的要求，同时也可以大大的降低硬件设备成本。 （2）变址分析运算流图中的输入和输出序列的顺序，输出是按顺序，而输入是“码位倒置”的顺序。如下图所示： 表3.2 码位倒置顺序自然顺序二进制表示码位倒置码位倒置顺序0000000010011004201001023011110641000011510110156110011371111117为了解决计算过程中输入数据由码位倒置的顺序排好再次输入的不便，这里借助于存储单元这个中间桥梁来实现，避免了数据发生冲突的可能。上图就是变址的功能。码位倒置顺序在软件上利用雷德算法进行运算。高要求应用实现变址必须保证具有恰当的电路。3.2.2 按频率抽取（DIF）的FTT频率抽取法遵循两个规则：一是把频率进行偶、奇分组，二是把时间前后分为两部分： 式（3.8）因为，k为偶数时，k为奇数时，因此可以把X(k)分为两组，分别为偶数组和奇数组： 式（3.9） 式（3.10） 式（3.11）令这两个序列都是N/2点的序列，下面是一半的DFT计算：这样，同样是将一个N点的DFT分解为两个N/2点的DFT了。频率抽选法对应的碟形运算关系图如下：对于N=8时频率抽取法的FFT流图如下：图3.6 8点的DFT分解图3.7 按频率抽取的第一次分解图3.8 按频率抽取的第二次分解图3.9按频率抽取的FFT（N=8）运算信号流图每一个操作是根据该输出序列X（k）的顺序在频域是属于奇数或偶数来分组，这种方法被称为频率抽取分组方法。常见的问题是：使用快速算法IDFT。分析IDFT的公式： 式（3.12）比较DFT的公式： 式（3.13）3.2.3 快速傅里叶分裂基FFT算法自从基-2FFT算法出现以来，人们仍在研究追寻更快的算法。从理论上讲，用较大的基数还可以进一步减少计算的次数，但是要以程序或硬件复杂为代价，所以取大于8的基数没有多大实际意义。1984年，法国的研究员们提出了一种把基2FFT和基4FFT连接在一起的算法叫做分裂基算法。基运算量比基2少，运算流图和和基2-FFT接近，运算程序也不长，也是一种高效实用算法。由于出现的基础-2FFT算法，人们仍在寻找更快的算法。从理论上讲，具有较大的碱可以进一步减少操作的数量，但在该程序或硬件复杂度为代价，它需要不大于实际意义的基础部8大得多。用分裂基算法计算点的DFT，基本方法与频选FFT类比相似，是建立在把X（k）分解成越来越多的小点数的子序列基础上，每次都是均等分解。二十世纪八十年代中期研究出来的算法分裂基算法，这种算法把基2和基4算法结合在一起，是对于解决N=2L各类算法中最好的一个。当n=p*q，且p=N/4，q=4时，n可表示为并有 式（3.14）再将上式中的k表示为可得 对=0,1,2,3，并用表示，用表示，可以写出则上式可写成如下更简明的形式3.2.4 N为组合数的FFT混合基算法以2的基数的FFT算法，即，由于此计算方法具有程序简单，计算效率高、对存储要求不是很高等特点，其在实际工程中得到了大范围的使用。在实际应用中，人们决定了有限长序列的长度N，因此多数场合可取，因此可以直接使用FFT的算法是以2的基数为准。假设N不能人为确定的，N的数值也不等于2的幂，通常有下列两种处理方法：（1） 补零：将补零，使得。例如N=60，可在序列的末尾填补上4个0，即另，使N达到，这样就可以使用基2FFT算法。有限长序列在补零以后，只是频谱的采样点有所变化而不会影响它的频谱的形状。（2）如果要求准确度高的N点DFT值,也可采用任意数作为基数的FFT算法 , 其计算的速度远低于以2为基数FFT算法。如N为复合数，设N等于两个整数p与q的乘积,即N=p.q如前面所述的以2为基数时一样,FFT的计算就是把DFT的运算尽可能分小,于是,在N=p.q的情况下,则可将N点的DFT分解为p个q点DFT或q个p点DFT来计算,以便减少计算量。其步骤如下：，分别为0, 1,，Q-1，分别为0, 1,，P-1N点DFT可以重新写成为 式（3.15）考虑到 令 再令以P=3，Q=4,N=12为例 (1) 先将通过改写成 。因为Q=4, 故输入是按自然顺序的，即(2)求Q个P点的DFT (3)乘以得到。 (4)求P个Q点的DFT，参变量是 (5) 将通过恢复为（1）求Q个P点DFT需要QP2次复数乘法和QP(P-1)次复数加法；（2）乘N个W因子需要N次复数乘法；（3）求P个Q点DFT需要PQ2 次复数乘法和PQ（Q-1)次复数加法。总的复数乘法量:QP2+N+PQ2=N(P+Q+1)；总的复数加法量:QP(P-1)+PQ(Q-1)=N(P+Q-2)；上述分解原则可推广至任意基数的更加复杂的情况。例如,如果N可分解为m个质数因子即 则第一步：可把先把N分解成两个因子，其中，并用上述讨论的方法将DFT分解为个点DFT；第二步：将分解为，然后将每个点DFT，之后再分解为个点DFT；因为要获得最高的运算效率，要经过m次分解，直到分解到最小点数的DFT运算。但计算效率的提高是要以编程的复杂性为代价的，一般较少应用。 为基2FFT 算法。当组合数中所有的均为4时，就是基4FFT算法 ，以为例,第一级运算的一般形式为： 3.3 傅里叶变换的应用FFT算法可以分析处理每一个可以使用傅里叶变换来进行分析、处理的领域，FFT算法会对这些地方用数字计算处理然后利用软件实现其所表现出来的功能。其表现形式为包括卷积分的积分，它是傅里叶变换实现近似处理的理论基础。不仅在信号、通信里会用到它，还在需要仿真、分析一些系统，对语音功率谱的估计时会用到。4 基-2FFT算法的C语言实现及仿真对于FFT算法的C语言实现，要解决码位倒序和蝶形运算这两个问题。4.1 码位倒序首先需要解决的就是码位倒序的问题，只有这样在FFT的结果中才会按自然顺序排列。假设一个N点的输入序列，那么它的序号二进制数位数就是t=log2N.有两个问题是需要码位倒序解决：（1）把t位进行二进制数倒序；（2）然后两个存储单元要在倒序后进行交换。倒序流程图如下：i=0:N-1nN-1ij?x(i)和x(j)交换kN/2kj+1?jj-kkk/2jj+kYNNY下面是码位倒序函数的程序代码： voidReverse(void) unsignedinti,j,k; unsignedintt; complextemp;/临时交换变量 for(i=0;iN;i+)/从第0个序号到第N-1个序号 k=i;/当前第i个序号 j=0;/存储倒序后的序号，先初始化为0 for(t=0;tlog2N;t+)/共移位t次，其中log2N是事先宏定义算好的 j=1;/k右移一位，次低位变为最低位 if(ji)/如果倒序后大于原序数，就将两个存储单元进行交换（判断ji是为了 防止重复交换） temp=xi; xi=xj; xj=temp; 4.2 蝶形运算 FFT的C语言编程只需用3层循环即可实现，这是由N点的FFT从左到右共有log2N级蝶形，每级有N/2L组，每组有L个，具体的三层是：完成整个FFT共log2N级每一级的蝶形运算的最外层循环，完成每一组的蝶形运算（每一级有N/2L组）的中间层循环，完成每一组有L个的单独1个蝶形运算的最内层循环。第一层循环：运算的级数进行控制是第一层循环完成的，需要m级计算N=2m。第二层循环：根据乘数进行控制第二层循环，这是由有2(L-1)个蝶形因子（乘数）第L级决定的。第三层循环里面的每一个蝶形因子都必须要执行一次，每一级要进行2(L-1)次循环计算，第三层循环此时是在第二层循环控制下。第三层循环：第三层循环在第二层循环确定某一乘数后要将本级中每个群中具有这一乘数的蝶形计算一次，因为同一级内不同群的乘数分布相同，第L级共有N/2L即2（n-L）个群，即第三层循环每执行完一次要进行N/2L个碟形计算。（执行不同group中具有相同W的蝶形运算）可以得出结论：第三层循环在每一级中需要完成N/2L个碟形计算；第三层循环在第二层循环下进行 2(L-1)次，碟形计算在第二层循环完成时共进行2(L-1) *N/2L=N/2个。第L级的计算在第二、第三层循环得以完成。实序列256点FFT运算的主程序代码基2FFT算法的C语言程序编制，是在利用C语言软件调用上述FFT算法实现的，这是在设计要求下完成的。在这里是一个有限长序列，共有256点，由于，M=8,所以总共有8级蝶形运算，每级有个蝶形，共需要1024次复数乘法和2048次复数加法。用C语言实现256点实序列基2FFT的源程序见附录A，仿真见附录B。河南城建学院本科毕业设计（论文） 结论 结论对于这次毕业设计，我做了很多准备。在确定了设计课题后，我立刻就去了学校的图书馆，花了整整一下午时间，终于找齐了相关书籍，并借阅出去。然后就又把之前学习的有关快速傅里叶变换的知识重新温习了一遍。另外又上网查阅了各方面知识与资料。为后期设计打下基础。 通过了一段时间的学习，知道了FFT是离散傅里叶（DFT）的快速算法，它利用旋转因子特性：周期性和对称性两个性质，先把DFT的尽可能多的连续分解，使其变为许多个比较短序列的DFT，计算较短序列的DFT，再组合成原序列，从而减少了运算量，使运算更加高效。在一系列工作完成后，就开始论文方面的编写，这里对于每个学校而言，在论文格式方面，都有着相当规范的格式要求。不仅仅在字体方面，格式方面，在页面设置方面，还有标题，都有很多相关要求。对于这个工作，我特意在网上下载了有关WORD的学习视频与教程，另外为了防止一些方面没有讲解到位，我又从图书馆借阅了很多书籍。之后学习了将近一个星期，终于可以单独掌握了各个编写技巧，格式的整理等等。在这个过程中，难免会有些地方遗漏和淡忘，身边的同学和老师，给予了我很多帮助。在学校范文的参考下，顺利完成了论文写作。最后总结一下这个设计过程，我意识到自己在这方面知识的欠缺。不仅仅在专业知识方面，对于常用的WORD基本操作，都相当缺乏。另外对于自己的整体意识，也有待提高。对于即将参加工作的我来说，真的有许多知识需要学习和补充以及基本操作与技巧的强化与练习。在以后的工作中，肯定会大有帮助。虽然即将离开学校，但是学习这事一刻也不能停止。坚持不懈，方能取得更大的成功。46河南城建学院本科毕业设计（论文） 参考文献 参考文献1 郑君里，应启珩，杨为理信号与系统第二版.北京：高等教育出版社，2000. 2 管致中，夏恭恪孟桥信号与线性系统第四版北京：高等教育出版社，2004.3 刘永健信号与线性系统修订版北京：人民邮电出版社，1994.4 奥本海姆 A V等信号与系统第二版刘树棠译西安：西安交通大学出版社，2002.5 刘培森应用傅里叶变换北京：北京理工大学出版社，1990.6 奥本海姆 A V等离散时间信号处理黄建国，刘树棠译北京：科学出版社，1998. 7 帕普利斯 A 信号分析毛培法译北京：科学出版社，1981. 8 丁玉美高西全.数字信号处理第二版.西安：西安电子科技大学出版社，2001.9 乌镇杨.数字信号处理.北京：高等教育出版社.2004.10 斯坦利W D.数字信号处理.常迥，译.北京：科学出版社，1979.11 王华奎.数字信号处理及应用.北京：高等教育出版社，2009.12 姚天任.江太辉.数字信号处理.第三版.华中科技大学出版社，2007.13 周耀华，汪凯仁.数字信号处理M.上海：复旦大学出版社，1993.14 赵红怡.DSP技术M.北京：电子工业出版社，2008.15 刘松强.数字信号处理系统及其应用M.北京：清华大学出版社，1996.16 陈后金主编.数字信号处理M.北京：高等教育出版社，2004.17 胡广书.数字信号处理理论、算法与实现M.北京：清华大学出版社,1997.18 陈佩青.数字信号处理教程M.2版.北京.清华大学出版社，2001.19 门爱东，杨波，全子一.数字信号处理M.北京：人民邮电出版社，2003.20 冷建华，李萍，王良红.数字信号处理M.北京：国防工业出版社，2002.21 王风文，舒冬梅，赵宏才.数字信号处理M.北京：北京邮电大学出版社，2005.22 邹彦，唐冬，宁志刚.DSP原理与应用M.北京：邮电大学出版社，2004.23 吴湘淇.信号、系统与信号处理（上下册）M.北京：电子工业出版社，199河南城建学院本科毕业设计（论文） 附录 河南城建学院本科毕业设计（论文） 附录A 附录A#include #include #include math.husing namespace std;double pi = 3.1415926535897932;class complexpublic:/无参构造函数complex()re=0;im=0;/有参构造函数complex(double real,double imag)re=real;im=imag;/加法complex operator + (complex& c)return complex( re + c.re , im + c.im );/减法complex operator - (complex& c)return complex( re - c.re , im - c.im );/乘法complex operator * (complex& c)return complex( (re * c.re)-(im * c.im) , (re * c.im)+(im * c.re) );/除法complex operator / (complex& c)return complex( ( re*c.re + im*c.im )/( c.re*c.re + c.im*c.im ),(im * c.re)-(re * c.im)/(c.re*c.re)+(c.im*c.im) );/除2void half()re=re/2;im=im/2;/输出到ostreamvoid insert(ostream& out)if(re=0) cout ;outre=0)?+:-) j=0)?im:(0-im);/显示void show()coutre=0)?+:-) j=0)?im:(0-im) ;/设值void setValue(double real,double imag)if(real0.00000001|real0.00000001|imag -0.00000001) im=imag;else im=0;friend complex c_pow(complex c,int y);private:double re,im;/流输出ostream& operator (ostream& out, complex c)c.insert(out);return out;/乘方complex c_pow(complex c,int y)complex returnValue = c ;for(int i = 1 ; i y ; i+ )returnValue = returnValue *