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