《第4章快速傅里叶变换》由会员分享，可在线阅读，更多相关《第4章快速傅里叶变换（12页珍藏版）》请在金锄头文库上搜索。
1、第第4章章 快速傅里叶变换快速傅里叶变换 (Fast Fourier TransformFFT)4.1 引言引言4.2 基基2FFT算法算法4.1 引言引言计算计算X(k)的一个值需要的一个值需要N次复数乘法和次复数乘法和(N-1)次复数加法，计算次复数加法，计算X(k)的所有的所有N个值需要个值需要NN次复数乘法和次复数乘法和N(N-1)次复数加法。次复数加法。一、一、时域抽取法基时域抽取法基2FFT原理原理 4.2 基基2FFT算法算法将长度为将长度为N的序列的序列x(n) 按奇偶分解为两个按奇偶分解为两个N/2点的子序列点的子序列 则则x(n)的的DFT为为X(k)按前按前N/2点和后点
2、和后N/2点分开表示点分开表示图图4.2.2 N点点DFT一次时域抽取分解运算流图（一次时域抽取分解运算流图（N=8）图图4.2.2 N点点DFT一次时域抽取分解运算流图（一次时域抽取分解运算流图（N=8）图图4.2.2包括两个包括两个N/2点点DFT和和N/2个蝶形，每个个蝶形，每个N/2点点DFT需要需要(N/2)(N/2)次复数乘法和次复数乘法和(N/2-1)(N/2)次复数加法运算，每个蝶次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为：乘法次数为：总的复数加法次数为：总的复数加法次数为：图
3、图4.2.3 N点点DFT二次时域抽取分解运算流图（二次时域抽取分解运算流图（N=8）图图4.2.4 N点点FFT运算流图（运算流图（N=8）分组分组方法方法原始数据原始数据序列序列N/2N/2分组分组N/4N/4分组分组( (最终分组结果最终分组结果) )计算计算结果结果按按奇奇偶偶分分组组x(0)x(0)x x1 1(0)(0)x(0)x(0)x x3 3(0)(0)x(0)x(0)X(0)X(0)x(1)x(1)x x1 1(1)(1)x(2)x(2)x x3 3(1)(1)x(4)x(4)X(1)X(1)x(2)x(2)x x1 1(2)(2)x(4)x(4)x x4 4(0)(0)x
4、(2)x(2)X(2)X(2)x(3)x(3)x x1 1(3)(3)x(6)x(6)x x4 4(1)(1)x(6)x(6)X(3)X(3)x(4)x(4)x x2 2(0)(0)x(1)x(1)x x5 5(0)(0)x(1)x(1)X(4)X(4)x(5)x(5)x x2 2(1)(1)x(3)x(3)x x5 5(1)(1)x(5)x(5)X(5)X(5)x(6)x(6)x x2 2(2)(2)x(5)x(5)x x6 6(0)(0)x(3)x(3)X(6)X(6)x(7)x(7)x x2 2(3)(3)x(7)x(7)x x6 6(1)(1)x(7)x(7)X(7)X(7)离散数据点
5、按奇偶分组过程离散数据点按奇偶分组过程 【例例】假假设设时时域域连连续续信信号号x(t)=x1(t)+x2(t)+x3(t)，其其中中x1(t)=3sin(30t)， x2(t)=2sin(40t)， x3(t)=sin(60t)。(1)如如果果用用FFT对对x(t)进进行行频频谱谱分分析析，问问采采样样频频率率Fs和和采采样样点点数数N应应如如何何选选择，才能精确求出择，才能精确求出x1(t)、x2(t)、x3(t)的频率；的频率；(2)按按照照你你选选择择的的Fs、N对对x(t)等等间间隔隔采采样样，得得到到x(n)，用用FFT进进行行频频普普分分析析求求出出各各频频率率分分量量的的幅幅值值，计计为为X(k)，画画出出幅幅度度谱谱，并并说说明明x1(t)、x2(t)、x3(t)的信号频率出现在的信号频率出现在k的什么位置。的什么位置。
