- 1、本文档共66页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第五章 快速傅里叶变换(FFT) 5.1 引言 DFT是信号分析与处理中的一种重要变换。因直接计算DFT的计算量与变换区间长度N的平方成正比,当N较大时,计算量太大,所以在快速傅里叶变换(简称FFT)出现以前,直接用DFT算法进行谱分析和信号的实时处理是不切实际的。直到1965年发现了DFT的一种快速算法以后,情况才发生了根本的变化。 5.2 基2FFT算法 5.2.1 直接计算DFT的特点及减少运算量的基本途径 长度为N的有限长序列x(n)的DFT为 考虑x(n)为复数序列的一般情况,对某一个k值,直接按(5.2.1)式计算X(k)值需要N次复数乘法、(N-1)次复数加法。 如前所述,N点DFT的复乘次数等于N2。显然,把N点DFT分解为几个较短的DFT,可使乘法次数大大减少。另外,旋转因子WmN具有明显的周期性和对称性。其周期性表现为 5.2.2 时域抽取法基2FFT基本原理 FFT算法基本上分为两大类:时域抽取法FFT(Decimation In Time FFT,简称DIT-FFT)和频域抽取法FFT(Decimation In Frequency FFT,简称DIF―FFT)。下面先介绍DIF―FFT算法。 设序列x(n)的长度为N,且满足 则x(n)的DFT为 其中X1(k)和X2(k)分别为x1(r)和x2(r)的N/2点DFT,即 与第一次分解相同,将x1(r)按奇偶分解成两个N/4长的子序列x3(l)和x4(l),即 用同样的方法可计算出 5.2.3 DIT―FFT算法与直接计算DFT运算量的比较 每一级运算都需要N/2次复数乘和N次复数加(每个蝶形需要两次复数加法)。所以,M级运算总共需要的复数乘次数为 5.2.4 DIT―FFT的运算规律及编程思想 1.原位计算 由图5.2.4可以看出,DIT―FFT的运算过程很有规律。N=2M点的FFT共进行M级运算,每级由N/2个蝶形运算组成。 2.旋转因子的变化规律 如上所述,N点DIT―FFT运算流图中,每级都有N/2个蝶形。每个蝶形都要乘以因子WpN,称其为旋转因子,p称为旋转因子的指数。 观察图5.2.4不难发现,第L级共有2 L-1个不同的旋转因子。N=23=8时的各级旋转因子表示如下: L=1时,WpN=WJ N/4=WJ2L, J=0 L=2时, WpN =WJ N/2=WJ2L, J=0,1 L=3时, WpN =WJN=WJ2L, J=0,1,2,3 对N=2M的一般情况,第L级的旋转因子为 3. 蝶形运算规律 设序列x(n)经时域抽选(倒序)后,存入数组X中。如果蝶形运算的两个输入数据相距B个点,应用原位计算,则蝶形运算可表示成如下形式: X (J) XL-1(J)+X L-1(J+B)WpN XL(J+B) XL-1(J)-X L-1(J+B)WpN ?式中 p=J·2 M-L;J=0,1,…,2 L-1-1;L=1,2,…,M 下标L表示第L级运算,XL(J)则表示第L级运算后数组元素X(J)的值。如果要用实数运算完成上述蝶形运算,可按下面的算法进行。 设 T=X L-1(J+B)WpN=TR+jTI X L-1(J)=X′R(J)+jX′I(J) 式中下标R表示取实部,I表示取虚部, 4. 编程思想及程序框图 5. 序列的倒序 DIT―FFT算法的输入序列的排序看起来似乎很乱,但仔细分析就会发现这种倒序是很有规律的。由于N=2M,所以顺序数可用M位二进制数(nM-1nM-2…n1n0)表示。 5.2.5 频域抽取法FFT(DIF―FFT) 在基2快速算法中,频域抽取法FFT也是一种常用的快速算法,简称DIF―FFT
您可能关注的文档
- 第四章 图像增强与平滑1.ppt
- 第四章 图形变换1.ppt
- 第四章 图形变换的矩阵方法1.ppt
- 第四章 图形的几何变换.ppt
- 第四章 网络扫描与网络监听.ppt
- 第四章 微机的设置与系统安装.ppt
- 第四章 无失真信源编码.ppt
- 第四章 形状和位置公差检测(二).ppt
- 第四章 形状和位置公差与检测(三).ppt
- 第四章 形状和位置公差与检测2.ppt
- 10《那一年,面包飘香》教案.docx
- 13 花钟 教学设计-2023-2024学年三年级下册语文统编版.docx
- 2024-2025学年中职学校心理健康教育与霸凌预防的设计.docx
- 2024-2025学年中职生反思与行动的反霸凌教学设计.docx
- 2023-2024学年人教版小学数学一年级上册5.docx
- 4.1.1 线段、射线、直线 教学设计 2024-2025学年北师大版七年级数学上册.docx
- 川教版(2024)三年级上册 2.2在线导航选路线 教案.docx
- Unit 8 Dolls (教学设计)-2024-2025学年译林版(三起)英语四年级上册.docx
- 高一上学期体育与健康人教版 “贪吃蛇”耐久跑 教案.docx
- 第1课时 亿以内数的认识(教学设计)-2024-2025学年四年级上册数学人教版.docx
文档评论(0)