FFT的研究历史及其现状

《FFT的研究历史及其现状》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

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

4、被周期化；第二步，再将频域离散化，我们得到离散周期傅里叶级数（DFS），时域进一步被周期化；第三步，考虑到周期离散化的时域和频域，我们只取一个周期研究，也就是众所周知的离散傅里叶变换（DFT）。于是我们可以得到DFT的定义：设x(n)是一个长度为N的有限长序列，定义x(n)的N点离散傅立叶变换为其中，k=0,1,2,...,N-1.X (k) 的傅立叶反变换为其中，n=0,1,2,...,N-1.1传统快速傅里叶变换（FFT）FFT(快速傅里叶变换)算法与DFT(离散傅里叶变换)算法比较，其运算量显著减少，用计算机实现时速度大

5、为提高。其思想是利用2点DFT运算无需乘法的特点，以减少过程在乘法运算上的时间开销。在FFT被提出的这50年中，最为人所熟知的FFT算法有基2、基4等。下面为就以这两种FFT算法为例，简要介绍传统FFT的思路与大致算法。91.1基2FFT正如上文所说，直接计算DFT的算法，对于X（K）的每个K值，需要进行4N次实数相乘和（4N-2）次相加，对于N个k值，共需N*N乘和N（4N-2）次实数相加。改进DFT算法，减小它的运算量，利用DFT中的周期性和对称性，使整个DFT的计算变成一系列迭代运算，可大幅度提高运算过程和运算量，这就是

6、FFT的基本思想。设N点序列x(n),.将x(n)按奇偶分组，公式如下改写为：，一个N点DFT分解为两个N/2点的DFT，继续分解，迭代下去，其运算量约为。下图为按时间抽取的8点的FFT蝶形图：1.2基4FFT当N等于4时的四点DFT运算为：可以看到，类似2点DFT，4点DFT运算也无需乘法，可以简少运算量。9对式进行分解：由上式可得如下矩阵变换过程：可以看到，第一步先对最开始的采样点矩阵每一行进行K点DFT，然后第二步每项对应乘以旋转因子，n0为行（0到3行），m为列（0到K-1列），最后按列做4点DFT，得到一个按行顺序排

7、列的最终结果。于是我们可以得到如下信号流图：1当今流行的FFT算法虽然传统的FFT算法已经能解决大多数数字信号的频谱分析问题，但是随着图像处理技术发展，传统的算法在处理新的数字信号频谱问题时已显得有所不足。因此，一些新的FFT算法也应运而生。这里我以多维离散余(正)弦变换和多维离散W变换(哈特莱变换)的快速算法为例，简要介绍一些新的FFT算法。91.1多维离散余(正)弦变换离散傅里叶变换需要进行复数运算，尽管有FFT可以提高运算速度，但在图像编码、特别是在实时处理中非常不便。离散傅里叶变换在实际的图像通信系统中很少使用，但它具

8、有理论的指导意义。根据离散傅里叶变换的性质，实偶函数的傅里叶变换只含实的余弦项，因此构造了一种实数域的变换——离散余弦变换(DCT)。通过研究发现，DCT除了具有一般的正交变换性质外，其变换阵的基向量很近似于Toeplitz矩阵的特征向量，后者体现了人类的语言、图像信号的相关