FFT的研究历史及其现状《数字信号处理》结课论文.docx

FFT算法的历史及发展现状 数字信号处理结课论文 学 院 通信工程学院 专 业 信息工程 班 级 1301052班 姓 名 徐 益 学 号 13010520033 摘 要 离散傅里叶变换(DFT)是信号分析的最基本方法，它使计算机在频域处理信号成为可能。但当DFT的N很大时，传统的算法会对计算机处理速度造成巨大的影响，于是快速傅里叶变换（FFT）应运而生。本文综述了离散变换快速算法的发展历史， 并对近些年流行的FFT算法进行评述，其中包括传统的基2、基4算法，以及多维离散余(正)弦变换、多维离散W变换 (哈特莱变换)的快速算法。最后对FFT的应用及其对于数字信号处理的意义进行评述。关键词：算法；离散傅里叶变换；快速傅里叶变换；多维离散余(正)弦变换；哈特莱变换快速傅里叶变换这一概念是1965年由J.W.库利和T.W.图基提出的，如今已经过去了整整50年。如今，在大学的理工科课程中，在完成数学类课程后，数字信号处理一般会作为通信电子类专业的专业基础课程进行学习。而在具体应用方面，例如对语音信号的分析和合成，在频域对信号滤波以及相关分析，通过对雷达、声纳、振动信号的频谱分析以提高对目标的搜索和跟踪的分辨率等等，都要用到FFT。可以说FFT的出现，对数字信号处理学科的发展起了重要的作用。1 离散傅里叶变换（DFT）简述谈快速傅里叶变换之前，我们必须了解一下离散傅里叶变换。下面我就自己的理解，对DFT产生的原因和定义做简要叙述。我们知道，傅里叶变换，是一种数学的精妙描述。但如果要通过计算机实现，就必须一步步把时域和频域离散化。所谓的离散化，也就是要采样。时域等间隔采样，频域发生周期延拓；频域采样，时域发生周期延拓。那么要得到时域频域都离散的结果，显然时域频域都要采样。周期延拓怎么办？只取一个周期就行了。具体的，我们可以把DFT产生的思路分为三步：第一步，时域离散化，我们得到离散时间傅里叶变换（DTFT），频谱被周期化；第二步，再将频域离散化，我们得到离散周期傅里叶级数（DFS），时域进一步被周期化；第三步，考虑到周期离散化的时域和频域，我们只取一个周期研究，也就是众所周知的离散傅里叶变换（DFT）。于是我们可以得到DFT的定义：设x(n)是一个长度为N的有限长序列，定义x(n)的N点离散傅立叶变换为其中，k=0,1,2,.,N-1.X (k) 的傅立叶反变换为其中，n=0,1,2,.,N-1.2 传统快速傅里叶变换（FFT）FFT(快速傅里叶变换) 算法与 DFT(离散傅里叶变换) 算法比较， 其运算量显著减少， 用计算机实现时速度大为提高。其思想是利用 2 点 DFT 运算无需乘法的特点，以减少过程 在乘法运算上的时间开销。在FFT被提出的这50年中，最为人所熟知的FFT算法有基2、基4等。下面为就以这两种FFT算法为例，简要介绍传统FFT的思路与大致算法。2.1 基2FFT正如上文所说，直接计算DFT的算法，对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是FFT的基本思想。设N点序列x(n),.将x(n)按奇偶分组，公式如下改写为：，一个N点DFT分解为两个 N/2点的DFT，继续分解，迭代下去，其运算量约为。下图为按时间抽取的8点的FFT蝶形图：2.2 基4FFT当 N 等于4时的四点DFT运算为：可以看到，类似2点DFT，4点DFT运算也无需乘法，可以简少运算量。对式进行分解：由上式可得如下矩阵变换过程：可以看到，第一步先对最开始的采样点矩阵每一行进行 K 点 DFT，然后第二步每项对 应乘以旋转因子 ，n0 为行（0 到 3 行），m 为列（0 到 K-1 列），最后按列做 4 点 DFT，得到一个按行顺序排列的最终结果。于是我们可以得到如下信号流图：3 当今流行的FFT算法虽然传统的FFT算法已经能解决大多数数字信号的频谱分析问题，但是随着图像处理技术发展，传统的算法在处理新的数字信号频谱问题时已显得有所不足。因此，一些新的FFT算法也应运而生。这里我以多维离散余(正)弦变换和多维离散W变换(哈特莱变换)的快速算法为例，简要介绍一些新的FFT算法。3.1 多维离散余(正)弦变换离散傅里叶变换需要进行复数运算，尽管有FFT可以提高运算速度，但在图像编码、特别是在实时处理中非常不便。离散傅里叶变换在实际的图像通信系统中很少使用，但它具有理论的指导意义。根据离散傅里叶变换的性质，实偶函数的傅里叶变换只含实的余弦项，因此构造了一种实数域的变换离散余弦变换(DCT)。通过研究发现，DCT除了具有一般的正交变换性质外，其变换阵的基向量很近似于Toeplitz矩阵的特征向量，后者体现了人类的语言、图像信号的相关特性。因此，在对语音、图像信号变换的确定的变换矩阵正交变换中，DCT变换被认为是一种准最佳变换。在近年颁布的一系列视频压缩编码的国际标准建议中，都把 DCT 作为其中的一个基本处理模块。DCT除了上述介绍的几条特点，即：实数变换、确定的变换矩阵、准最佳变换性能外，二维DCT还是一种可分离的变换，可以用两次一维变换得到二维变换结果。最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为"反离散余弦变换"，"逆离散余弦变换"或者"IDCT"。有两个相关的变换，一个是离散正弦变换(DST for Discrete Sine Transform)，它相当于一个长度大概是它两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换(MDCT for Modified Discrete Cosine Transform)，它相当于对交叠的数据进行离散余弦变换。3.2 W变换(哈特莱变换)的快速算法哈特莱变换（Hartley transform) 1942年美国学者哈特莱（R.V.L.Hartley, 18901970)为了简化信号分析过程的数学计算，提高运算速度和效率，提出了一对与傅里叶变换相似，同属于正弦型的正交变换。与快速傅立叶变换类似，快速哈特莱变换有以下几种：时间抽取型FHT算法，频率抽取型FHT算法，基4FHT算法，混合基FHT算法，递归型FHT算法等。在这里，使用基2的时间抽取型FHT算法。对N点信号序列，其离散哈特莱变换为:对于上述公式，将信号序列按奇偶序分开，并设：即可导出时间抽取型FHT算法。下面，我们给出快速哈特莱变换的蝶形因子：4 FFT的应用4.1 FFT在语音信号处理中的应用对语音信号进行FFT变换，将其从时域变换到频域，可以更加直观地观察它的频谱分布、宽度等信息，对进一步设计各种滤波器、编码及调制方式、识别模式等工作奠定基础。 FFT在语音信号处理方面的应用非常常见，如语音识别（刑侦、门禁系统等）、声音模拟（候鸟、鱼群的迁徙引导等）、话音伪装（TOM猫等）。4.2 FFT在图像处理中的应用FFT在图像处理中的应用主要体现在图像保存和图像滤波。图像保存方面，通过FFT将图像分解为一组越来越小的正交归一图像，具有很高的压缩比仍能够将原始数据完全恢复而不引入任何失真。所以当我们希望将一幅图像以一种更紧凑的数据格式进行编码，同时保持数据不丢失时，FFT不失为一个很好的工具。图像滤波方面，在进行FFT后，若在反变换之前对变换域进行选择，可对图像进行滤波处理。4.3 FFT在雷达信号处理中的应用雷达信号处理算法中大多数采用FFT方法测量频率，如果提高测频精度需增加FFT点数，增加FFT点数的实质是在整个单位圆(即整个距离谱)上均匀增加频域采样点数，从而造成运算量的成倍增加。Chirp-z变换可以实现对回波频谱中的某段进行局部细化，从而在采样点数、运算量增加不多的情况下，大大提高雷达的测量精度。 匹配傅里叶变换，检测反辐射导弹，改进机载雷达的目标跟踪性能，地面运动目标检测，特别是在实际3米SAR数据中，应用匹配傅里叶变换检测出了慢速运动目标。匹配傅里叶变换的基本原理是其变换基的相位随时间变化规律必须与信号相位随时间变化规律相同。5 结束语通过了解FFT的发展及应用，我得到以下启发：（1）快速变换算法的每一次突破都是找到一种数学工具以揭示变换的内在关系，从而推动了快速算法的发展。因而对于工程，数学工具的重要性不容小觑；（2）在计算机运算速度不断发展的今天，增强算法运算效率依然有着必要性；（3）作为通信行业的研究者，我们应充分重视算法对于信号处理的重要性，认识到数字信号处理是信号处理的发展方向。参 考 文 献1 高西全,丁玉美,阔永红.数字信号处理M.北京:电子工业出版社,2015.2 马维祯.快速傅里叶变换FFT的发展现状N.华南理工大学报,1995,5.3 咚懂.如何理解离散傅立叶变换JOL.https:/www.zhihu.com/question/23218891,2015.4 马亦飞.快速傅立叶变换的前世今生JOL. http:/www.go-gddq.com/html/s124,2014.5 万宵鹏.基4FFT原理及MATLAB算法实现N.电子科技大学报,2012,10.6 刘德坤. 基于哈特莱变换的快速模板互相关算法设计N.华中科技大学报,2011.7 杨丽娟,张白桦,叶旭桢. 快速傅里叶变换FFT及其应用J.光电通信,2004.8 章玮.音频FFT技术现状J.电声技术,1997.5