基于DSP的FFT研究的开题报告

附件B：开题报告附件B：开题报告1、课题的目的及意义1.1、DSP数字信号处理（DSP）是一门涉及许多学科而又广泛应用于许多领域的新兴学科。DSP是利用计算机或专用处理设备，以数字的形式对信号进行分析、采集、合成、变换、滤波、估算、压缩、识别等加工处理，以便提取有用的信息进行有效的传输与应用。1.2、DFTDFT(离散傅里叶变换)作为的基本运算，其快速算法离散傅里叶变换（DiscreteFourierTransform，缩写为DFT），是傅里叶变换在时域和频域上都呈离散的形式，可以将信号从时域转换到频域，在各种数字信号处理中起着核心作用。它将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。即使对有限长的离散信号作DFT，也应当将其看作其周期延拓的变换。1.3、FFT在实际应用中通常采用DFT的快速算法FFT(快速傅里叶变换)，它有效地提高了DFT的计算效率，并在无线通信、语音识别、图像处理和频谱分析等领域有着广泛的应用。特别是随着OFDM(正交频分复用)技术的出现，不同OFDM系统需要不同变换点数的FFT运算，如何更快速、更灵活地实现FFT变得越来越重要。FFT根据离散傅氏变换的奇、偶、虚、实等特性，对离散傅立叶变换的算法进行改进获得的。因为计算机的乘法运算需要通过加法实现，所以做一次复数乘法的时间比加法多得多，而FFT算法的研究主要在于减少乘法运算的次数。它对傅氏变换的理论并没有新的发现，但是对于在计算机系统或者说数字系统中应用离散傅立叶变换，可以说是进了一大步。而且随着计算机的发展，FFT在工程上进入实际运用阶段。高效率的FFT算法是雷达信号处理、卫星通讯、生物医学、和多媒体信号处理等基础和核心算法。提高FFT处理速度，满足对雷达信号处理实时性的要求，在EW接收机高速数据处理方面将有广泛的应用前景。随着科学技术的不断进步，相控阵体制已广泛应用于各种兴载、机载、舰载、和地面雷达，对于电尺寸较大的相控阵天线，用公式按级数求和计算阵列天线方向图的方法效率很低，而FFT的引入解决了这一难题。设x(n)为N项的复数序列，由DFT变换，任一X（m）的计算都需要N次复重庆大学本科学生毕业设计（论文）数乘法和N-1次复数加法，而一次复数乘法等于四次实数乘法和两次实数加法，一次复数加法等于两次实数加法，即使把一次复数乘法和一次复数加法定义成一次“运算”（四次实数乘法和四次实数加法），那么求出N项复数序列的X（m）,即N点DFT变换大约就需要N^2次运算。当N=1024点甚至更多的时候，需要N2=1048576次运算，在FFT中，利用WN的周期性和对称性，把一个N项序列（设N=2k,k为正整数），分为两个N/2项的子序列，每个N/2点DFT变换需要（N/2）2次运算，再用N次运算把两个N/2点的DFT变换组合成一个N点的DFT变换。这样变换以后，总的运算次数就变成N+2*（N/2)^2=N+（N^2）/2。继续上面的例子，N=1024时，总的运算次数就变成了525312次，节省了大约50%的运算量。而如果我们将这种“一分为二”的思想不断进行下去，直到分成两两一组的DFT运算单元，那么N点的DFT变换就只需要Nlog2N次的运算，N在1024点时，运算量仅有10240次，是先前的直接算法的1%，点数越多，运算量的节约就越大，这就是FFT的优越性。1.4FFT几种常见算法的比较1.4.1基2、基4、基8、基16算法1965年,J.W.Cooley和J.W.Tukey提出了快速傅立叶变换算法,FFT算法可分为按时间抽取算法和按频率抽取算法，还可以分为基二算法、基四算法、分裂基算法、混合基算法、Bruun算法等等。按基本的蝶形运算的构成,可将每一种算法分为基2、基4、基8、基16及任意因子等的FFT算法.基4FFT的点数的取值种类是基2FFT的一半.从这个意义上说,基4FFT的应用是受限制的.但基4FFT迭代次数比基2减少一半,每次迭代运算需取出和存入N个数据,所以基4FFT需要访问内存的次数减少一半,这有利于提高运算速度.基4FFT总的复数乘法次数比基2FFT减少1/4.采用基8和基16算法可使运算次数进一步减少,但减少量并不显著,而且基8、基16算法的运算流程图更复杂,硬件和软件实现不便,所以目前应用不多.基4的FFT的缺点是实现困难,软硬件复杂;它的优点是运算量小,计算速度快.由于实时处理对高速运算的要求,基4算法越来越受到重视.一般来说,基数越高总计算量越少.但判断一个算法的优劣不仅要从计算量,而且还应从算法的复杂性方面加以考虑.特别值得指出的是,在大规模集成电路迅速发展的时代,高速阵列乘法器的出现,在乘法计算量上节省几分之一已不具有明显的吸引力.目前,半导体制造厂正在把FFT算法用大规模集成电路来实现,因此算法的简单性和规则性将更适合大规模集成.就目前来说,基2、和基4算法是使用最广泛的算法.附件B：开题报告1.4.2分裂基算法1984年,法国的杜哈梅尔和霍尔曼提出的分裂基快速算法,使运算效率进一步提高.该算法的基本思路是对偶序号输出使用基2算法,奇序号输出使用基4算法.分裂基算法有下述显著的特点:(1)分裂基算法有着和基2、基4算法一样的规则结构,可以同址运算,这对用IC芯片来实现这些算法时是特别重要的.(2)若把基2、基4和分裂基算法中所有无关紧要的旋转因子都考虑在内,那么三者所需的计算量其实是一样的.分裂基算法的特点是合理地安排了算法结构,使无关紧要的旋转因子最大程度的减小.对N=2的M次方的一类FFT算法,至少对一维序列而言,已很难再使乘法量进一步减小到更接近理论值的下界.1.5、FFT在实际中的应用1.5.1、用FFT计算IDFTFFT可以用来计算IDFT，只要时间序列足够长，采样足够密，频域采样也就可较好地反映信号的频谱趋势，所以FFT可以用以进行连续信号的频谱分析。当然，这里作了几次近似处理：1）用离散采样信号的傅立叶变换来代替连续信号的频谱，只有在严格满足采样定理的前提下，频谱才不会有畸变，否则只是近似；2）用有限长序列来代替无限长离散采样信号。1.5.2、FFT计算线性卷积线性卷积是求离散系统响应的主要方法之一,许多重要应用都建立在这一理论基础上,如卷积滤波等。以前曾讨论了用圆周卷积计算线性卷积的方法归纳如下:将长为N2的序列x(n)延长到L,补L-N2个零将长为N1的序列h(n)延长到L,补L-N1个零如果L≥N1+N2-1,则圆周卷积与线性卷积相等,此时,可有FFT计算线性卷积,方法如下:a.计算X(k)=FFT[x(n)]b.求H(k)=FFT[h(n)]c.求Y(k)=H(k)Y(k)k=0～L-1d.求y(n)=IFFT[Y(k)]n=0～L-11.5.3、FFT计算相关函数重庆大学本科学生毕业设计（论文）互相关和自相关函数的计算可利用FFT实现。由于离散付里叶变换隐含着周期性，所以用FFT计算离散相关函数也是对周期序列而言的。直接做N点FFT相当于对两个N点序列x(n)、y(n)作周期延拓，作相关后再取主值（类似圆周卷积）。而实际一般要求的是两个有限长序列的线性相关，为避免混淆，需采用与圆周卷积求线性卷积相类似的方法，先将序列延长补0后再用上述方法。可见，只要进行二次FFT,一次IFFT就可完成线性卷积计算。计算表明,L32时,上述计算线性卷积的方法比直接计算线卷积有明显的优越性,因此,也称上述圆周卷积方法为快速卷积法FFT计算相关函数互相关和自相关函数的计算可利用FFT实现。由于离散付里叶变换隐含着周期性，所以用FFT计算离散相关函数也是对周期序列而言的。直接做N点FFT相当于对两个N点序列x(n)、y(n)作周期延拓，作相关后再取主值（类似圆周卷积）。而实际一般要求的是两个有限长序列的线性相关，为避免混淆，需采用与圆周卷积求线性卷积相类似的方法，先将序列延长补0后再用上述方法。1.6本设计带给我们的作用本设计让我们学会查阅资料，可以加深我们对DFT算法原理和基本性质的理解，可以更加熟悉FFT的算法原理和FFT子程序算法原理及应用，可以学会用FFT对连续信号和时域信号进行频谱分析的方法，可以掌握DSP中FFT的设计和编程思想，实现DSP开发系统对DFT，FFT仿真，最后还能简要画出硬件设计电路图。2、FFT的研究状况及国内外现状DFT是数字信号处理最重要的基石之一，也是对信号进行分析和处理时最常用的工具之一。在200多年前法国数学家、物理学家傅里叶提出后来以他名字命名的傅里叶级数之后，用DFT这个工具来分析信号就已经为人们所知。但在很长时间内，这种分析方法并没有引起更多的重视，最主要的原因在于这种方法运算量比较大。直到1965年，Cooley和Tukey在《计算机科学》发表著名的《机器计算傅立叶级数的一种算法》论文，FFT才开始大规模应用。FFT的这种方法充分利用了DFT运算中的对称性和周期性，从而将DFT运算量从N2减少到N*log2N。当N比较小时，FFT优势并不明显。但当N大于32开始，点数越大，FFT对运算量的改善越明显。比如当N为1024时，FFT的运算效率比DFT提高了100倍。在库利和图基提出的FFT算法中，其基本原理是先将一个N点时域序列的DFT分解为N个1点序列的DFT，然后将这样计算出来的N个1点序列DFT的结果进行组合，得到最初的N点时域序列的DFT值。在20世纪60年代，伴随着计算机的发展和成熟，库利和图基的成果掀起了数字信号处理的革命，因附件B：开题报告而FFT发明者的桂冠才落在他们头上。之后，桑德（G.Sand）-图基等快速算法相继出现，几经改进，很快形成了一套高效运算方法，这就是现在的快速傅立叶变换（FFT）。这种算法使DFT的运算效率提高1到2个数量级，为数字信号处理技术应用于各种信号的实时处理创造了良好的条件，大大推进了数学信号处理技术。1984年，法国的杜哈梅（P.Dohamel）和霍尔曼（H.Hollamann）提出的分裂基块快速算法，使运算效率进一步提高。库利和图基的FFT算法的最基本运算为蝶形运算，每个蝶形运算包括两个输入点，因而也称为基-2算法。在这之后，又有一些新的算法，进一步提高了FFT的运算效率，比如基-4算法，分裂基算法等。这些新算法对FFT运算效率的提高一般在50%以内，远远不如FFT对DFT运算的提高幅度。从这个意义上说，FFT算法是里程碑式的。可以说，正是计算机技术的发展和FFT的出现，才使得数字信号处理迎来了一个崭新的时代。除了运算效率的大幅度提高外，FFT还大大降低了DFT运算带来的累计量化误差，这点常为人们所忽略。传统FFT算法是递归分解算法，Linzer-Feig提出了融合乘、加运算的FFT分度算法，把复数的旋转因子变为平方乘法运算。Stasiniski提出的基K-FFT是其他基数FFT算法的新发展。基KC-FFT是由K点卷积和K点DFT组成,,基于卷积定理将长度降低的DFT和乘旋转因子的运算代之以卷积和DFT运算,并证明新算法具有和传统算法相同的乘法复杂性。2.1国外现状国外围绕快速傅里叶变换的并行计算进行了多项研究和开发。美国NewMexico大学VasiliosGeorgitsis等人设计了2-DFFT程序，可处理512*512个点的图像，其底层通信基于PVM，将2-DFFT转化成1-DFFT并行计算，完成了二维图像的变换。目前最新的研究成果是由麻省理工学院计算机科学实验室超级计算技术组开发的FFTW，FFTW是计算DFT的快速C程序的一个完整集合，它可计算一维或多维、实数据以及任意规模的DFT.在FFTW中，DFT的计算由执行器完成，执行器是由许多高度优化、可组装的子代码模块组成的。FFTW有一个规划器，规划器用以根据具体机器的体系结构特点和具体的DFT宽度N，在运行时寻找一种有效地子代码组装方式，因此使得FFTW具有很好的自适应性和很快的运行速速。FFTW还包括对共享和分布式存储系统的并行变换。2.2国内现状在我国