数字信号处理 第4章 快速傅里叶变换.ppt

《数字信号处理 第4章 快速傅里叶变换.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章快速傅里叶变换(FastFourierTransform—FFT)4.1引言4.2基2FFT算法4.1引言计算X(k)的一个值需要N次复数乘法和(N-1)次复数加法，计算X(k)的所有N个值需要N×N次复数乘法和N×(N-1)次复数加法。一、时域抽取法基2FFT原理4.2基2FFT算法将长度为N的序列{x(n)}按奇偶分解为两个N/2点的子序列则x(n)的N点DFT为:由于x1(r)和x2(r)为N/2点X(k)按前N/2点和后N/2点分开表示偶序列的N/2点DFT奇序列的N/2点DFT图4.2.2N点

2、DFT一次时域抽取分解运算流图（N=8）图4.2.2N点DFT一次时域抽取分解运算流图（N=8）图4.2.2包括两个N/2点DFT和N/2个蝶形，每个N/2点DFT需要(N/2)×(N/2)次复数乘法和(N/2-1)×(N/2)次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为：总的复数加法次数为：图4.2.3N点DFT二次时域抽取分解运算流图（N=8）图4.2.4N点FFT运算流图（N=8）分组方法原始序列N/2分组N/4分组(最终分组结果)计算结果按奇偶分组x(0)x

3、1(0)x(0)x3(0)x(0)X(0)x(1)x1(1)x(2)x3(1)x(4)X(1)x(2)x1(2)x(4)x4(0)x(2)X(2)x(3)x1(3)x(6)x4(1)x(6)X(3)x(4)x2(0)x(1)x5(0)x(1)X(4)x(5)x2(1)x(3)x5(1)x(5)X(5)x(6)x2(2)x(5)x6(0)x(3)X(6)x(7)x2(3)x(7)x6(1)x(7)X(7)离散数据点按奇偶分组过程【例】假设时域连续信号x(t)=x1(t)+x2(t)+x3(t)，其中x1(t)=

4、3sin(30πt)，x2(t)=2sin(40πt)，x3(t)=sin(60πt)。如果用FFT对x(t)进行频谱分析，问采样频率Fs和采样点数N应如何选择，才能精确求出x1(t)、x2(t)、x3(t)的频率；按照你选择的Fs、N对x(t)等间隔采样，得到x(n)，用FFT进行频普分析求出各频率分量的幅值，计为X(k)，画出幅度谱，并说明x1(t)、x2(t)、x3(t)的信号频率出现在k的什么位置。