实序列FFT算法的C语言实现

实序列FFT算法的C语言实现学生：XX指导教师：XX内容摘要：DFT和IDFT是数字信号分析与处理中的一种重要运算和变换，但直接根据定义计算DFT时，运算量大，不能实时得到计算结果。特别是在实际应用中，N都取得比较大，此时，由于乘法和加法的次数都近似与N的平方成正比，这将极大增加DFT计算所需时间。为此，提出了许多DFT和IDFT的快速算法，称为快速傅里叶变换（FFT）和快速傅里叶反变换（IFFT）。本文较为系统地阐述了快速傅里叶变换的算法原理然后用MATLAB实现了快速傅里叶变换。论文首先首要介绍了FT与DFT的定义、DFT与FFT的关系,然后重点介绍基2时域抽取FFT算法以及其原理和运算流图，再应用C语言实现了实序列的FFT。最后在Matlab软件上进行仿真，仿真结果验证了设计的正确性。关键词：傅里叶变换快速傅立叶变换Matlab仿真RealizationofFFTalgorithmforrealsequenceWithCprogramAbstract：DFTandIDFTareimportanttransformandprocessingindigitalsignalprocessing.However,therearelargeamountofcomputationbydirectlycalculatingaccordingtothedefinitionofDFT.Especiallyinthepracticalapplication,Nisbigger,atthistime,becausethetimeofmultiplicationandadditionareapproximatelyproportionaltothesquareofN,whichwillgreatlyincreasethecalculationtimeneededforDFT.Therefore,manyDFTandIDFTfastalgorithmareraised,whicharecalledFFTandIFFT.InthispaperrelativelysystematicallyelaboratedthefastFouriertransformalgorithmprincipleanduseMATLABsoftwaretorealizethefastFouriertransform.ThepaperfirstintroducesthedefinitionofFTandDFT,therelationshipbetweenDFTandFFT,andthenmainlyintroducesDIT-FFT,includingitsprincipleandoperationflowdiagram,andfinallyusedClanguagetorealizetherealsequenceFFT.ThedesignsaresimulatedinMatlabsoftware,theresultsofthesimulationconfirmtheexactnessofthedesign.Keywords：FouriertransformationfastFouriertransformationMatlabsimulation目录前言.....................................................................11序列的FT和DFT........................................................11.1序列的FT........................................................11.2序列的DFT.......................................................21.2.1DFT的定义和计算.........................................21.2.2实序列的DFT.............................................22FFT算法...............................................................32.1基2时域抽取FFT算法.............................................32.1.1基本原理.................................................32.1.2DIT-FFT算法的运算流图...................................52.1.3DIT-FFT算法的运算量和存储量.............................52.2实序列的FFT算法.................................................63实序列FFT算法的C语言实现............................................73.1VS2010简介......................................................73.1.1新建项目.................................................83.1.2新建文件.................................................83.2实序列FFT算法子程序.............................................93.2.1倒序....................................................103.2.2蝶形运算................................................123.3实序列FFT算法主程序............................................153.3.1原始序列的产生和读取....................................153.3.2计算结果的显示和输出....................................163.4运行结果分析....................................................163.4.1计算结果数据分析........................................173.4.2N点DFT波形分析........................................174结束语...............................................................20附录：................................................................21参考文献：..............................................................271实序列FFT算法的C语言实现前言在实际的数字系统中，DFT是一种得到了广泛的应用的、重要的信号处理手段，但它的运算效率非常低。随着DFT输入的点数增加到数百或数千，DFT需要的运算量变得非常大。快速傅里叶变换（FFT）可使实现DFT的运算量下降几个数量级，从而使数字信号处理的速度大大提高[1]。FFT是离散傅立叶变换（DFT）的快速算法，可以将一个信号变换到频域。有些信号在时域上是不易看出有什么特征的，但是如果变换到频域之后，就很容易了。FFT可以将一个信号的频谱提取出来，这在频谱分析方面也是经常用的。实际中需要做快速傅里叶变换的多为实序列数据，而其变换算法都是以复数序列作为输入。本设计利用频域的性质，将实序列数据变为复数序列，再进行FFT,以提高效率。本设计就是要求在熟悉DFT及FFT算法基本原理的基础上，编制C语言程序实现实数序列的FFT算法。1序列的FT和DFT序列的傅里叶变换（FourierTransform，FT）和离散傅里叶变换（DFT）都是对序列的频域描述，它们揭示了序列由那些分量构成，各分量的幅度和相位大小。1.1序列的FT序列x(n)的傅里叶变换又称为离散时间傅里叶变换（DTFT），其定义为nnnxnxXjje)()]([FT)e(（1.1-1）式中，称为数字角频率。如果已知x(n)的傅里叶变换X(ej)，则可下式求得其时域表达式ππ-jjde)e(π21)(nXnx（1.1-2）上式称为序列的傅里叶反变换（IFT）。序列的傅里叶变换是的连续函数，且一般情况下为复变函数，并可表示为)(jjje|)e(|)e(XX其中，|)e(|jX和)(分别称为幅度谱和相位谱。此外，根据je的周期性可知，序列的频谱及其幅度谱和相位谱都是关于以2为2周期的周期函数。1.2序列的DFT序列的FT变换j(e)Xw为的连续函数，不便于用计算机程序进行辅助分析和计算。为了便于用计算机辅助求解和分析，提出了离散傅里叶变换（DFT）。1.2.1DFT的定义和计算长度为M的有限长序列x(n)，n=0~M-1，其N点DFT和IDFT（离散傅里叶反变换）分别定义为10()DFT[()]()NknNnXkxnxnW，k=0~N-1（1.2.1-1）10)(1)]([IDFT)(NknkNWkXNkXnx，n=0~N-1（1.2.1-2）式中，NNW2πje，称为旋转因子。借助于矩阵，可以将以上两式所示序列的N点DFT和IDFT运算用矩阵表示为)1()1()0()1()1()0()1()1(2)1(1)1(00)1(1211100000Nxxx（1.2.1-3）)1()1()0(1)1()1()0()1()1()1(2)1(1001)1(121100000NXXX（1.2.1-4）1.2.2实序列的DFT实际系统中所处理的信号大多数是实序列，对这些实序列x(n)，根据式（1.2.1-1）得到111()000()()()()NNNNknNnknknNNNNnnnXNkxnWxnWWxnW则**111***000()()()()NNNknknknNNNnnnXNkxnWxnWxnW因为x(n)为实序列，则*()()xnxn。此外，有3**-j2πj2π-j2π()*eeeknknknknknNNNNNWW因此11***00()()()()NNknknNNnnXNkxnWxnWXk或者*()()XNkXk（1.2.1-5）上式说明，所有实数序列的DFT都具有共轭对称性。因此，对实序列，只需要计算出其N点DFT中的前面N/2个点，即k=0~N/2-1的点，即可根据共轭对称性，由式（1.2.1-5）求出另外N/2个点，即k=N/2~N-1的点，合起来得到完整的N点DFT。在式（1.2.1-5）中分别令k=0和N/2，又可得到*()(0)(0)XNXX*(/2)(/2)XNXN以上两式说明，在实