FFT的研究历史及其现状

1、FFT的研究历史及其现状SANY GROUP system office room SANYUA16H-fft算法的历史及发展现状数字信号处理结课论文学院通信工程学院专业信息工程班级1301052班姓名徐益学号摘要离散傅里叶变换(DFT)是信号分析的最基本方法，它使计算机在领域处理信号成为可能，但当 DFT的N很大时，传统的算法会对计算机处理速度造成巨大的影响，于是快速傅里叶变换(FFT) 应运而生：，本文综述了离散变换快速算法的发展历史，并对近些年流行的FFT算法进行评述，其中 包括传统的基2、基4算法，以及多维离散余(正)弦变换、多维离散W变换(哈特莱变换)的快速算 法。最后对FFT的应用

2、及其对于数字信号处理的意义进行评述。关键词：算法；离散傅里叶变换；快速傅里叶变换；多维离散余(正)弦变换；哈特莱变换快速傅里叶变换这一概念是1%5年由J.W.库利和T.W.图基提出的，如今已经过去了整整50年。如 今，在大学的理工科课程中，在完成数学类课程后，数字信号处理一般会作为通信电子类专业的专业基础 课程进行学习。而在具体应用方面，例如对语音信号的分析和合成，在撅域对信号滤波以及相关分析，通 过对雷达、声纳、振动信号的撅谱分析以提高对目标的搜索和跟踪的分辨率等等，都要用到FFT。可以说 FFT的出现，对数字信号处理学科的发展起了重要的作用c1离散傅里叶变换(DFT)简述谈快速傅里叶变换之

3、前，我们必须了解一下离散傅里叶变换。下面我就自己的理解，对DFT产生的 原因和定义做简要叙述。我们知道，傅里叶变换，是一种数学的精妙描述。但如果要通过计算机实现，就必须一步步把时域和 领域离散化。所谓的离散化，也就是要采样。时域等间隔采样，频域发生周期延拓；撅域采样，时域发生 周期延拓。那么要得到时域领域都离散的结果，显然时域撅域都要采样。周期延拓怎么办？只取一个周期 就行了。具体的，我们可以把DFT产生的思路分为三步：第一步，时域离散化，我们得到离散时间傅里叶变换(DTFT),频谱被周期化；第二步，再将频域离散化，我们得到离散周期傅里叶级数(DFS),时域进一步被周期化；第三步，考虑到周期离

4、散化的时域和领域，我们只取一个周期研究，也就是众所周知的离散傅里叶变 换(DFT) o于是我们可以得到DFT的定义：设x(n)是一个长度为N的有限长序列，定义x(n)的N点离散傅立叶变换为其中，k=0.1.2,.N-l.X?(k)?的傅立叶反变换为其中，n=O.1.2,.2传统快速傅里叶变换(FFT)FFT(快速傅里叶变换)算法与DFT(离散傅里叶变换)算法比较，其运算量显着减少，用计算机实现时 速度大为提高。其思想是利用2点DFT运算无需乘法的特点，以减少过程在乘法运算上的时间开销。在 FFT被提出的这50年中，最为人所熟知的FFT算法有基2、基4等，下面为就以这两种FFT算法为例， 简要介

5、绍传统FPT的思路与大致算法。1.1 基 2FFT正如上文所说，直接计算DFT的算法，对于X (K)的每个K值，需要进行4N次实数相乘和(4N- 2)次相加，对于N个k值，共需N*N乘和N (4N-2)次实数相加。改进DFT算法，减小它的运算量， 利用DFT中喷的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运 算量，这就是FPT的基本思想。设N点序列x(n).N = 2叫将x(n)按奇偶分组，公式如下改写为：知幻+与温因八”?，一个N点DFT分解为两个N/2点的DFT,继续分解，迭代下去，其运算量约为""。下图为按时间抽取的8点的FFT蝶形图

6、：1.2 基 4FFT当N等于4时的四点DFT运算为：可以看到，类似2点DFT, 4点DFT运算也无需乘法，可以简少运算量。对式进行分解：由上式可得如下矩阵变换过程：可以看到，第一步先对最开始的采样点矩阵每一行进行K点DFT,然后第二步粤项对应乘以旋转因 子，nO为行(0到3行)，m为列(0到K-1列)，最后按列做4点DFT,得到一个按行顺序排列的最终 结果:)于是我们可以得到如下信号流图：3当今流行的FFT算法虽然传统的FFT算法已经能解决大多数数字信号的频谱分析问题，但是随着图像处理技术发展，传 统的算法在处理新的数字信号撅谱问题时已显得有所不足。因此，一些新的FFT算法也应运而生

7、6;这里 我以多维离散余(正)弦变换和多维离散W变换(哈特莱变换)的快速算法为例，简要介绍一些新的FFT算 法。1.3 多维离散余(正)弦变换离散傅里叶变换需要进行复数运算，尽管有FFT可以提高运算速度，但在图像编码、特别是在实时 处理中非常不便。离散傅里叶变换在实际的图像通信系统中很少使用，但它具有理论的指导意义：，根据离 散傅里叶变换的性质，实偶函数的傅里叶变换只含实的余弦项，因此构造了一种实数域的变换离散余 弦变换(DCT)。通过研究发现，DCT除了具有一般的正交变换性质外，其变换阵的基向量很近似于 Toepliiz矩阵的特征向量，后者体现了人类的诺言、图像信号的相关特性。因此，在对语音

8、、图像信号变 换的确定的变换矩阵正交变换中，DCT变换被认为是一种准最佳变换。在近年饷布的一系列视频压缩编 码的国际标准建议中，都把DCT作为其中的一个基本处理模块。DCT除了上述介绍的几条特点，即：实数变换、确定的变换矩阵、准最佳变换性能外，二维DCT还 是一种可分离的变换，可以用两次一维变换得到二维变换结果。最常用的一种离散余弦变换的类型是下面给出的第二种类型，通常我们所说的离散余弦变换指的就是 这种。它的逆，也就是下面给出的第三种类型，通常相应的被称为“反离散余弦变换”，"逆离散余弦变换“ 或者"IDCT"。有两个相关的变换，一个是离散正弦变换(DSTfor

9、DiscrtteSineTransform),它相当于一个长度大概是它 两倍的实奇函数的离散傅里叶变换；另一个是改进的离散余弦变换 (MDCTforModifiedDiscreteCosineTransform),它相当于对交接的数据进行离散余弦变换。1.4 W变换(哈特莱变换)的快速算法哈特莱变换(Hartleytransform)1942年美国学者哈特莱(R.V.L.Hartley.l8901970)为了简化信号分析 过程的数学计算，提高运算速度和效率，提出了一对与傅里叶变换相似，同闾于正弦型的正交变换。与快速傅立叶变换类似，快速哈特莱变换有以下几种：时间抽取型FHT算法，频率抽取型FHT

10、算 法，基4FHT算法，混合基FHT算法，递归型FHT算法等。在这里，使用基2的时间抽取型FHT算法。对N点信号序列，其离散哈特莱变换为：对于上述公式，将信号序列按奇偶序分开，并设：即可导出时间抽取型FHT算法。下面，我们给出快速哈特莱变换的蝶形因子：4 FFT的应用4.1 FFT在语音信号处理中的应用对语音信号进行FFT变换，将其从时域变换到频域，可以更加直观地观察它的频谱分布、宽度等信 息，对进一步设计各种滤波器、编码及调制方式、识别模式等工作奠定基础。FFT在语音信号处理方面的应用非常常见，如语音识别(刑侦、门禁系统等)、声音模拟(候鸟、鱼 群的迁徙引导等)、话音伪装(TOM猫等)。4.

11、2 FFT在图像处理中的应用FFT在图像处理中的应用主要体现在图像保存和图像遮波。图像保存方面，通过FFT将图像分解为一组越来越小的正交归一图像，具有很高的压缩比仍能够将 原始数据完全恢复而不引入任何失真。所以当我们希望将一幅图像以一种更紧凑的数据格式进行编码，同 时保持数据不丢失时，FFT不失为一个很好的工具。图像滤波方面，在进行FFT后，若在反变换之前对变换域进行选择，可对图像进行遮波处理c4.3 FFT在雷达信号处理中的应用雷达信号处理算法中大多数采用FFT方法测量频率，如果提高测频精度需增加FFT点数，增加FFT 点数的实质是在整个单位圆(即整个距离谱)上均匀增加频域采样点数，从而造成

12、运算量的成倍增加。 Chirp-z变换可以实现对回波撅谱中的某段进行局部细化，从而在采样点数、运算量增加不多的情况下， 大大提高雷达的冽量精度。匹配傅里叶变换，检测反辐射导弹，改进机戮宙达的目标跟踪性能，地面运动目标检测，特别是在实 际3米SAR数据中，应用匹配傅里叶变换检测出了慢速运动目标。匹配傅里叶变换的基本原理是其变换 基的相位随时间变化规律必须与信号相位随时间变化规律相同。5 结束语通过了解FFT的发展及应用，我得到以下启发：(1)快速变换算法的每一次突破都是找到一种数学工具以揭示变换的内在关系，从而推动了快速算 法的发展。因而对于工程，数学工具的重要性不容小觑；(2)在计算机运算速度不断发展的今天，增强算法运算效率依然有着必要性；(3)作为通信行业的研究者，我们应充分重视算法对于信号处理的重要性，认识到数字信号处理是 信号处理的发展方向。参考文献川高西全.丁玉美.阔永红.数字信号处理Ml.北京:电子工业出版社.2015.马维祯.快速傅里叶变换FFT的发展现状IN.华南