第4章快速傅里叶变换.ppt
第第4章章 快速傅里叶变换快速傅里叶变换(Fast Fourier TransformFFT)4.1 引言引言4.2 基基2FFT算法算法4.1 引言引言)1()1()0()()0()1(01000100NxWxWxWWnxXNNNNNnnN)1()1()0()()1()1(11101101NxWxWxWWnxXNNNNNnnN)1()1()0()()()1(1010NxWxWxWWnxkXNkNkNkNNnnkNNkWnxenxnxkXNnknNNnknNjN0 )()()(DFT)(10102)1()1()0()1()1()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000NxxxWWWWWWWWWWWWNXXXNNNNNNNNNNNNNNNNNNNNnWkXekXNkXnxNknkNNknkNj0 )()(1)(IDFT)(10102)1()1()0(1)(1)0()1(01000100NXWXWXWNWkXNxNNNNNkkN)1()1()0(1)(1)1()1(11101101NXWXWXWNWkXNxNNNNNkkN)1()1()0(1)(1)()1(1010NXWXWXWNWkXNnxNnNnNnNNkknN)1()1()0(1)1()1()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000NXXXWWWWWWWWWWWWNNxxxNNNNNNNNNNNNNNNNNNN)1()1()0()1()1()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000NxxxWWWWWWWWWWWWNXXXNNNNNNNNNNNNNNNNNNN)1()1()0(1)1()1()0()1()1(2)1(1)1(0)1()1(1211101)1(0201000NXXXWWWWWWWWWWWWNNxxxNNNNNNNNNNNNNNNNNNN计算计算X(k)的一个值需要的一个值需要N次复数乘法和次复数乘法和(N-1)次复数加法，计算次复数加法，计算X(k)的所有的所有N个值需要个值需要NN次复数乘法和次复数乘法和N(N-1)次复数加法。次复数加法。NnWnxekXNkXnxNkWnxenxnxkXNknkNNkknNjNNnknNNnknNjN0)()(1)()(0)()()()(1010210102 IDFT DFT一、一、时域抽取法基时域抽取法基2FFT原理原理 4.2 基基2FFT算法算法将长度为将长度为N的序列的序列x(n)按奇偶分解为两个按奇偶分解为两个N/2点的子序列点的子序列 则则x(n)的的DFT为为12 1 0 )12()(12 1 0 )2()(21NrrxrxNrrxrx，1 1 0 ,)()()()()()()12()2()()()()(DFT)(12/0212/212/02/112/02212/02112/0)12(12/0210NkkXWkXWrxWWrxWrxWWrxWrxWrxWnxWnxWnxnxkXNrkNkrNkNNrkrNNrkrNkNNrkrNNrrkNNrkrNnknNnknNNnknNN，奇数偶数2/212/02/222/112/02/112110)(DFT)()()(DFT)()(1,1,0 )()()()(NNrkrNNNrkrNkNNnknNrxWrxkXrxWrxkXNkkXWkXWnxkX，1 1 0 ,)()()()()()()12()2()()()()(DFT)(12/0212/212/02/112/02212/02112/0)12(12/0210NkkXWkXWrxWWrxWrxWWrxWrxWrxWnxWnxWnxnxkXNrkNkrNkNNrkrNNrkrNkNNrkrNNrrkNNrkrNnknNnknNNnknNN，奇数偶数X(k)按前按前N/2点和后点和后N/2点分开表示点分开表示12 1 0)()()2()()()(2121NkkXWkXNkXkXWkXkXkNkN，ABCA CBA CB图图4.2.2 N点点DFT一次时域抽取分解运算流图（一次时域抽取分解运算流图（N=8）N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)12 1 0)()()2()()()(2121NkkXWkXNkXkXWkXkXkNkN，ABCA CBA CB)2()(1rxrx)12()(2rxrx12 1 0Nr，图图4.2.2 N点点DFT一次时域抽取分解运算流图（一次时域抽取分解运算流图（N=8）N/2点DFTWN0N/2点DFTWN1WN2WN3x(0)X1(0)x(2)x(4)x(6)x(1)x(3)x(5)x(7)X1(1)X1(2)X1(3)X2(0)X2(1)X2(2)X2(3)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)图图4.2.2包括两个包括两个N/2点点DFT和和N/2个蝶形，每个个蝶形，每个N/2点点DFT需要需要(N/2)(N/2)次复数乘法和次复数乘法和(N/2-1)(N/2)次复数加法运算，每个次复数加法运算，每个蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复蝶形只有一次复数乘法运算和两次复数加法运算。所以，总的复数乘法次数为：数乘法次数为：2/2/)1(2/2)2/(22NNNNN总的复数加法次数为：总的复数加法次数为：2/2)2/(2)2/()12/(2NNNN图图4.2.3 N点点DFT二次时域抽取分解运算流图（二次时域抽取分解运算流图（N=8）)(3rx)(4rx)(5rx)(6rx图图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(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)离散数据点按奇偶分组过程离散数据点按奇偶分组过程【例例】假设时域连续信号假设时域连续信号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的什么位置。的什么位置。
