FFT的研究历史及其现状《数字信号处理》结课论文.docx
《FFT的研究历史及其现状《数字信号处理》结课论文.docx》由会员分享,可在线阅读,更多相关《FFT的研究历史及其现状《数字信号处理》结课论文.docx(6页珍藏版)》请在三一文库上搜索。
1、FFT算法的历史及发展现状 数字信号处理结课论文 学 院 通信工程学院 专 业 信息工程 班 级 1301052班 姓 名 徐 益 学 号 13010520033 摘 要 离散傅里叶变换(DFT)是信号分析的最基本方法,它使计算机在频域处理信号成为可能。但当DFT的N很大时,传统的算法会对计算机处理速度造成巨大的影响,于是快速傅里叶变换(FFT)应运而生。本文综述了离散变换快速算法的发展历史, 并对近些年流行的FFT算法进行评述,其中包括传统的基2、基4算法,以及多维离散余(正)弦变换、多维离散W变换 (哈特莱变换)的快速算法。最后对FFT的应用及其对于数字信号处理的意义进行评述。关键词:算法
2、;离散傅里叶变换;快速傅里叶变换;多维离散余(正)弦变换;哈特莱变换快速傅里叶变换这一概念是1965年由J.W.库利和T.W.图基提出的,如今已经过去了整整50年。如今,在大学的理工科课程中,在完成数学类课程后,数字信号处理一般会作为通信电子类专业的专业基础课程进行学习。而在具体应用方面,例如对语音信号的分析和合成,在频域对信号滤波以及相关分析,通过对雷达、声纳、振动信号的频谱分析以提高对目标的搜索和跟踪的分辨率等等,都要用到FFT。可以说FFT的出现,对数字信号处理学科的发展起了重要的作用。1 离散傅里叶变换(DFT)简述谈快速傅里叶变换之前,我们必须了解一下离散傅里叶变换。下面我就自己的理
3、解,对DFT产生的原因和定义做简要叙述。我们知道,傅里叶变换,是一种数学的精妙描述。但如果要通过计算机实现,就必须一步步把时域和频域离散化。所谓的离散化,也就是要采样。时域等间隔采样,频域发生周期延拓;频域采样,时域发生周期延拓。那么要得到时域频域都离散的结果,显然时域频域都要采样。周期延拓怎么办?只取一个周期就行了。具体的,我们可以把DFT产生的思路分为三步:第一步,时域离散化,我们得到离散时间傅里叶变换(DTFT),频谱被周期化;第二步,再将频域离散化,我们得到离散周期傅里叶级数(DFS),时域进一步被周期化;第三步,考虑到周期离散化的时域和频域,我们只取一个周期研究,也就是众所周知的离散
4、傅里叶变换(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 基
5、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运算也无需乘
6、法,可以简少运算量。对式进行分解:由上式可得如下矩阵变换过程:可以看到,第一步先对最开始的采样点矩阵每一行进行 K 点 DFT,然后第二步每项对 应乘以旋转因子 ,n0 为行(0 到 3 行),m 为列(0 到 K-1 列),最后按列做 4 点 DFT,得到一个按行顺序排列的最终结果。于是我们可以得到如下信号流图:3 当今流行的FFT算法虽然传统的FFT算法已经能解决大多数数字信号的频谱分析问题,但是随着图像处理技术发展,传统的算法在处理新的数字信号频谱问题时已显得有所不足。因此,一些新的FFT算法也应运而生。这里我以多维离散余(正)弦变换和多维离散W变换(哈特莱变换)的快速算法为例,简要介绍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数字信号处理 FFT 研究 历史 及其 现状 数字信号 处理 论文
链接地址:https://www.31doc.com/p-3902058.html