DSP的FFT研究的开题报告.docVIP

附件B： 开题报告 课题的目的及意义 1.1、DSP 数字信号处理（DSP）是一门涉及许多学科而又广泛应用于许多领域的新兴学科。DSP是利用计算机或专用处理设备，以数字的形式对信号进行分析、采集、合成、变换、滤波、估算、压缩、识别 等加工处理，以便提取有用的信息进行有效的传输与应用。 1.2、DFT DFT(离散傅里叶变换)作为的基本运算，其快速算法离散傅里叶变换（Discrete Fourier Transform，缩写为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 需要访问内存的次数减少一半, 这有利于提高运算速度. 基4 FFT 总的复数乘法次数比基2FFT 减少1/ 4. 采用基8 和基16 算法可使运算次数进一步减少, 但减少量并不显著, 而且基8、基16 算法的运算流程图更复杂, 硬件和软件实现不便, 所以目前应用不多. 基4 的FFT 的缺点是实现困难, 软硬件复杂; 它的优点是运算量小, 计算速度快. 由于实时处理对高速运算的要求, 基4 算法越来越受到重视.一般来说, 基数越高总计算量越少. 但判断一个算法的优劣不仅要从计算量, 而且还应从算法的复杂性方面加以考