数字信号处理程佩青第三版第四章快速傅里叶变换FFT课件.ppt

文档介绍：该【数字信号处理程佩青第三版第四章快速傅里叶变换FFT课件 】是由【yzhlya】上传分享，文档一共【63】页，该文档可以免费在线阅读，需要了解更多关于【数字信号处理程佩青第三版第四章快速傅里叶变换FFT课件 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。第四章快速傅里叶变换(FFT)
主要内容
DIT-FFT算法
DIF-FFT算法
IFFT算法
Chirp-FFT算法
线性卷积的FFT算法
§
FFT:FastFourierTransform
1965年,Cooley-Turky发表文章《机器计算傅里叶级数的一种算法》,提出FFT算法,解决DFT运算量太大,在实际使用中受限制的问题。
FFT的应用。频谱分析、滤波器实现、实时信号处理等。
DSP芯片实现。TI公司的TMS320c30,10MHz时钟,基2-FFT1024点FFT时间15ms。
§
1、DFT与IDFT
2、DFT与IDFT运算特点
复数乘法
复数加法
一个X(k)
N
N–1
N个X(k)
(N点DFT)
N2
N(N–1)
同理:IDFT运算量与DFT相同。
实数乘法
实数加法
一次复乘
4
2
一次复加
2
一个X(k)
4N
2N+2(N–1)=2(2N–1)
N个X(k)
(N点DFT)
4N2
2N(2N–1)
3、降低DFT运算量的考虑
§(DIT)的FFT算法
(DecimationInTime)
1、算法原理
设序列点数N=2L,L为整数。
若不满足,则补零
将序列x(n)按n的奇偶分成两组:
N为2的整数幂的FFT算法称基-2FFT算法。
将N点DFT定义式分解为两个长度为N/2的DFT
记:………(1)
(这一步利用:)
再利用周期性求X(k)的后半部分
用“蝶形结”表示上面运算的分解: