数字信号处理第四章_第1页
数字信号处理第四章_第2页
数字信号处理第四章_第3页
数字信号处理第四章_第4页
数字信号处理第四章_第5页
已阅读5页，还剩25页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

第四章快速傅里叶变换FFT:FastFourierTransform学习目标理解按时间抽选的基-2FFT算法的算法原理、运算流图、所需计算量和算法特点引言FFT:

FastFourierTransform1965年，Cooley-Turky发表文章《机器计算傅里叶级数的一种算法》，提出FFT算法，解决DFT运算量太大，在实际使用中受限制的问题。FFT的应用。频谱分析、滤波器实现、系统分析等。DSP芯片实现。TI公司的TMS320c30，10MHz时钟，基2-FFT1024点FFT时间15ms。一、直接计算DFT的问题及改进途径运算量复数乘法复数加法一个X(k)NN–1N个X(k)(N点DFT)N2N(N–1)实数乘法实数加法一次复乘42一次复加2一个X(k)4N2N+2(N–1)=2(2N–1)N个X(k)(N点DFT)4N22N(2N–1)FFT算法分类:时间抽选法

DIT:Decimation-In-Time频率抽选法

DIF:Decimation-In-Frequency二、按时间抽选的基-2FFT算法1、算法原理设序列点数N=2L，L为整数。若不满足，则补零将序列x(n)按n的奇偶分成两组：N为2的整数幂的FFT算法称基-2FFT算法。N/2点DFT则x(n)的DFT:再利用周期性求X(k)的后半部分由两个N/2点DFT得到N点DFT分解后的运算量：复数乘法复数加法一个N/2点DFT(N/2)2N/2(N/2–1)两个N/2点DFTN2/2N(N/2–1)一个蝶形12N/2个蝶形N/2N总计运算量减少了近一半N/2仍为偶数，进一步分解：N/2N/4这样逐级分解，直到2点DFT当N=8时，即分解到X3(k)，X4(k)，X5(k)，X6(k)，k=0,1计算2点DFT也是一个基本蝶形运算

2、运算量当N=2L时，共有L级蝶形，每级N/2个蝶形，每个蝶形有1次复数乘法2次复数加法。复数乘法：复数加法：比较DFT3、算法特点1）原位计算（同址运算）m表示第m级迭代，k，j表示数据所在的行数蝶形运算输出可以放回输入的存储器地址2）倒位序倒位序自然序0000000010041001010220101106301100114100101551010113611011177111输入

输出0041226314553677x(n)X(k)3）蝶形运算蝶形运算两节点间距离对N=2L点FFT，输入倒位序，输出自然序，

第m级运算每个蝶形的两节点距离为2m–1

每个蝶形两节点距离22－1＝2

蝶形运算两节点的第一个节点为k值，表示成L位二进制数，左移L–

m位，把右边空出的位置补零，结果为r的二进制数。

r=(101)*23-2=0104）存储单元输入序列x(n):N个存储单元系数：N/

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论