离散傅里叶变换(DF课件

1、第第2章章 离散傅里叶变换离散傅里叶变换(DFT)12.1 离散傅里叶变换离散傅里叶变换(DFT) 2.2 快速傅里叶变换快速傅里叶变换(FFT) 2.3 离散卷积离散卷积2.4 FFT应用应用第第2章章 离散傅里叶变换离散傅里叶变换(DFT)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)22.1 离散傅里叶变换离散傅里叶变换(DFT) 2.1.1 DFT定义定义2.1.2 DFT推导推导2.1.3 DFT性质性质2.1.4 DFT的矩阵计算的矩阵计算第第2章章 离散傅里叶变换离散傅里叶变换(DFT)32.1.1 离散傅里叶变换的定义离散傅里叶变换的定义 1. 定义定义 设设x(n)是一个

2、长度为是一个长度为N的有限长序列，的有限长序列， 则定义则定义x(n)的的N点离散傅里叶变换为点离散傅里叶变换为10( ) ( )( ), k=0, 1, &, N-1 (3.1.1)NknNnX kDFT x nx n WX(k)的离散傅里叶逆变换为的离散傅里叶逆变换为1 1 0 )(1)()(10NnWkXNkXIDFTnxNkknN，(3.1.2)式中，式中， ，N称为称为DFT变换区间长度，通常称变换区间长度，通常称(3.1.1)式和式和(3.1.2)式为离散傅里叶式为离散傅里叶变换对变换对。NjNeW2第第2章章 离散傅里叶变换离散傅里叶变换(DFT)4证明证明IDFTX(k

3、)的唯一性。的唯一性。证明：把证明：把(3.1.1)式代入式代入(3.1.2)式有式有110011()001( )( )1( )NNmkknNNkmNNk m nNmkIDFT X kx m WWNx mWN 11,()0,01Nm n MN Mk m nNm n MN MkWN 为整数 为整数 所以，所以， 在变换区间上满足下式：在变换区间上满足下式： IDFTX(k)=x(n), 0nN-1 由此可见，由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。式定义的离散傅里叶逆变换是唯一的。 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)5例例 3.1.1 x(n)=R4(n)，求，

4、求x(n)的的8点和点和16点点DFT。 解：设变换区间解：设变换区间N=8， 则则设变换区间设变换区间N=16， 则则273880038( )( )sin()2,0,1,7sin()8jknknnNjkX kx n Wekekk n273880038( )( )sin()4,0,1,15sin()16jknknnNjkX kx n Wekekk16161615 n第第2章章 离散傅里叶变换离散傅里叶变换(DFT)62. DFT的隐含周期性的隐含周期性 前面定义的前面定义的DFT变换对中，变换对中， x(n)与与X(k)均为有限均为有限长序列，但由于长序列，但由于 的周期性，的周期性， 使使(

5、3.1.1)式和式和(3.1.2)式式中的中的X(k)隐含了周期性，且周期为隐含了周期性，且周期为N。对任意整数。对任意整数m， 总有总有(),kk mNNNWWk m N均为整数均为整数 所以所以(3.1.1)式中，式中， X(k)满足满足1()010()( )( )( )Nk mN nNnNknNnX kmNx n Wx n WX k同理可证明同理可证明(3.1.2)式中式中 x(n+mN)=x(n)nkNW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)7 实际上，任何周期为实际上，任何周期为N的周期序列的周期序列 都可以都可以看作看作长度为长度为N的有限长序列的有限长序列x(n)的周

6、期延拓的周期延拓序列，序列， 而而x(n)则是则是 的一个周期，的一个周期， 即即( )()(3.1.5)( )( )( )(3.1.6)mNx nx nmNx nx nRn为了叙述方便，为了叙述方便， 将将(3.1.5)式用如下形式表示：式用如下形式表示： )(nx)(nxNnxnx)()(3.1.7)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)8图图 3.1.2 有限长序列及其周期延拓有限长序列及其周期延拓 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)92.1.2 DFT推导推导 1. 由由Z变换推导变换推导 由由Z变换可知，非周期序列变换可知，非周期序列x(n)的的Z变换为变

7、换为 对于有限长序列对于有限长序列x(n)(n=0,N-1)，X(z)的收敛区域的收敛区域总包括单位圆。若总包括单位圆。若在单位圆的在单位圆的N个均分点上计算个均分点上计算Z变换变换，得周期序列为得周期序列为nnznxzX)()(10)()()()(2NnnkNnnkNWezWnxWnxzXkXkNkNj第第2章章 离散傅里叶变换离散傅里叶变换(DFT)10 上式两边乘以上式两边乘以 ，再对，再对k从从0N-1求和，得求和，得 这说明，长度小于或等于这说明，长度小于或等于N的有限时宽序列可以的有限时宽序列可以用它的用它的Z变换在单位圆上的变换在单位圆上的N个取样精确地表示，或个取样精确地表示，

8、或有有限时宽序列的限时宽序列的DFT相当于其相当于其Z变换在单位圆等间隔点上变换在单位圆等间隔点上的取样的取样。10)(1)(NknkNWkXNnxZ平面IR2/NrkNW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)11图图 3.1.1 X(k)与与X(e j)的关系的关系 X(z)X(ej)X(k)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)12 2. 由离散傅里叶级数推导由离散傅里叶级数推导 如果如果x(n)的长度为的长度为N，且，且 ，则可写，则可写出出 的离散傅里叶级数为的离散傅里叶级数为(3.1.8) (3.1.9) 式中式中 (3.1.10)(nxNnxnx)()(11

9、100010( )( )( )( )11( )( )( )NNNknknknNNNNnnnNknknNNnX kx n Wx nWx n Wx nX k WX k WNN10)(1NnknNWkXN( )( )( )NX kx k Rk)(kX第第2章章 离散傅里叶变换离散傅里叶变换(DFT)133. 由连续傅里叶变换推导由连续傅里叶变换推导设设xa(t)与与Xa(j)构成傅立叶变换对，则构成傅立叶变换对，则(1)时域采样时域采样：将：将xa(t)离散化离散化其频谱为其频谱为X(ej)，是以，是以2为周期的周期函数，即为周期的周期函数，即dejXtxdtetxjXtjaatjaa)(21)()

10、()(nanaanTtnTxnTttxnTx)()()()()(TTjkTajeXTkjjTjXeX)()2(1)()(第第2章章 离散傅里叶变换离散傅里叶变换(DFT)14(2) 时域截断时域截断：将：将xa(nT)由无限变为有限时宽由无限变为有限时宽x(n) x(n)= xa(nT)w(t)其中其中 且且N=T0/T也即也即此时频谱为此时频谱为 X(ejT)* *W(j) ，是，是的连续周期函数。的连续周期函数。 022 1)(0其他TTtTtw1-Nn0 )( )()( )()()()(10nTxnTtnTxtwnTtnTxnxaNnana第第2章章 离散傅里叶变换离散傅里叶变换(DFT

11、)15(3) 频域采样频域采样：将频谱离散化：将频谱离散化 为周期序列，其时域函数为为周期序列，其时域函数为 显然，显然， 是以是以T0（T0=NT）为周期的序列，故其一周）为周期的序列，故其一周内恰好为原信号内恰好为原信号xa(t)的的N个采样值。个采样值。)2(1)()()(00kTjTkjjTjWeXkX)()()()()()()()()()()()()()(010010100100100nxrTnTtnTxnTTtnTxnTtnTxnTTtnTxnTtnTtnTxnTtnxrNnaNnaNnaNnanNnan )(nx)(kX第第2章章 离散傅里叶变换离散傅里叶变换(DFT)16将上述

12、将上述 求解，得求解，得令令显然显然 完全由完全由X(k)确定，而确定，而X(k)是以是以N为周期的序列，为周期的序列，且在且在0N-1区间上区间上xa(nT)可用可用x(n)表示，于是表示，于是)(kX)2()(1 )2(1)( )2(1)()()(02100001000100 knTTkjNnaknTjNnaktjNnaTkjjenTxTTkjjTenTxTkjjTdtenTtnTxkXnkNjNnaenTxkX210)()()(kXnkNNnnkNjNnWnxenxkX)()()(10210第第2章章 离散傅里叶变换离散傅里叶变换(DFT)17 同样，可推导出同样，可推导出 显然，当显然

13、，当时域采样满足时域采样定理时域采样满足时域采样定理时，时，频域不会发频域不会发生混叠生混叠，这时，在，这时，在0N-1区间上定义的区间上定义的X(k)恰好表示恰好表示Xa(j)在带限区域内的采样值；而当在带限区域内的采样值；而当频域采样满足频频域采样满足频域采样定理域采样定理时，时，时域才不会发生混叠时域才不会发生混叠，在，在0N-1区间上区间上定义的定义的x(n)才能代表才能代表x(t)的有效采样值。的有效采样值。 上述推导说明，离散傅立叶变换与连续傅立叶变上述推导说明，离散傅立叶变换与连续傅立叶变换有密切关系。换有密切关系。10)(1)(NknkNWkXNnx第第2章章 离散傅里叶变换离

14、散傅里叶变换(DFT)182.1.3 DFT性质性质 DFT有许多性质与连续、序列傅里叶变换相似，但也有许多性质与连续、序列傅里叶变换相似，但也有其独特性，这主要源于它所隐含的周期性，即循环性。有其独特性，这主要源于它所隐含的周期性，即循环性。 1. 线性性线性性 如果如果x1(n)和和x2(n)是两个有限长序列，长度分别为是两个有限长序列，长度分别为N1和和N2 y(n)=ax1(n)+bx2(n) 0nN-1 式中式中a、b为常数，为常数，N=maxN1, N2，则，则y(n)的的N点点DFT为为 Y(k)=DFTy(n)=aX1(k)+bX2(k), 0kN-1 (3.2.1) 其中其中

15、X1(k)和和X2(k)分别为分别为x1(n)和和x2(n)的的N点点DFT。 该性质说明，该性质说明，DFT适用于离散线性系统适用于离散线性系统。第第2章章 离散傅里叶变换离散傅里叶变换(DFT)192. 循环位移性质循环位移性质 若若x(n) X(k)成立，则成立，则 x(n-n0) X(k) 称为时间位移性称为时间位移性 (1) 或或 x(n) X(k-k0) 称为频率位移性称为频率位移性 (2) (1)说明时域信号的加载时刻，对信号说明时域信号的加载时刻，对信号DFT的幅度的幅度不产生任何影响，只在不产生任何影响，只在频域引入一线性相移频域引入一线性相移。 (2)说明用特定频率的余弦（

16、或正弦）对信号进行说明用特定频率的余弦（或正弦）对信号进行调制，其结果是信号的调制，其结果是信号的频谱发生了位移频谱发生了位移（以调制频率（以调制频率为中心）。为中心）。 由于由于x(n)与与X(k)的周期性，使的周期性，使DFT的位移呈现的位移呈现循循环特性环特性。knNW00nkNW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)20图图 3.2.1 循环位移过程示意图循环位移过程示意图 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)213. 对称性对称性 若若x(n) X(k)成立，则成立，则 x*(n) X*(-k)（复共轭序列的（复共轭序列的DFT ） 或或 x*(-n) X*

17、(k) 或或 (1/N)X(n) x(-k)说明说明DFT的时域与频域具有的时域与频域具有对偶对偶关系。关系。第第2章章 离散傅里叶变换离散傅里叶变换(DFT)22 证明：证明： 根据根据DFT的唯一性的唯一性1()01()010()( )( )( )( )nnNN kNnNN kNnNknNnXNkx n Wx n Wx n WDFT x n由由X(k)的隐含周期性，有的隐含周期性，有X* *(N-k)=X* *(-k)，X(N)=X(0)。用同样的方法可以证明用同样的方法可以证明 DFTx* *(N-n)=X* *(k) (3.2.8) 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)2

18、34. DFT的共轭对称性的共轭对称性 如同任何实函数都可以分解成偶对称分量和奇对如同任何实函数都可以分解成偶对称分量和奇对称分量一样，任何有限长序列称分量一样，任何有限长序列x(n)也可以表示成其也可以表示成其共共轭对称分量轭对称分量和和共轭反对称分量共轭反对称分量之和，之和， 即即 x(n)=xep(n)+xop(n), 0nN-1 (3.2.11) 将式中的将式中的n换成换成N-n，并取复共轭，得到，并取复共轭，得到 x*(N-n)=x*ep(N-n)+x*op(N-n) =xep(n)-xop(n) (3.2.12) xep(n)=1/2x(n)+x*(N-n) (3.2.13) xo

19、p(n)=1/2x(n)-x*(N-n) (3.2.14)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)24 (1) 如果如果 x(n)=xr(n)+jxi(n) 其中其中 xr(n)=Rex(n)=1/2x(n)+x*(n) jxi(n)=jImx(n)=1/2x(n)-x*(n) 则则 DFTxr(n)=1/2DFTx(n)+x*(n) =1/2X(k)+X*(N-k)=Xep(k) DFTjxi(n)=1/2DFTx(n)-x*(n) =1/2X(k)-X*(N-k)=Xop(k) 由由DFT的线性性质可得的线性性质可得 X(k)=DFTx(n)=Xep(k)+Xop(k) (3.2

20、.16) 其中其中 Xep(k)=DFTxr(n)，X(k)的共轭对称分量的共轭对称分量 Xop(k)=DFTjxi(n)，X(k)的共轭反对称分量的共轭反对称分量第第2章章 离散傅里叶变换离散傅里叶变换(DFT)25(2)如果如果 x(n)=xep(n)+xop(n)， 0nN-1 (3.2.17) 其中其中 xep(n)=1/2x(n)+x*(N-n)，x(n)的共轭对称分量的共轭对称分量 xop(n)=1/2x(n)-x*(N-n)，x(n)的共轭反对称分量的共轭反对称分量 则则 DFTxep(n)=1/2DFTx(n)+x*(N-n) =1/2X(k)+X*(k)=ReX(k) DFT

21、xop(n)=1/2DFTx(n)-x*(N-n) =1/2X(k)-X*(k)=jImX(k) 因此因此 X(k)=DFTx(n)=XR(k)+jXI(k) (3.2.18) 其中其中 XR(k)=ReX(k)=DFTxep(n) jXI(k)=jImX(k)=DFTxop(n) 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)26有限长有限长实序列实序列DFT的共轭对称性说明：的共轭对称性说明： 设设x(n)是长度为是长度为N的实序列，且的实序列，且X(k)=DFTx(n)，则，则 (1) X(k)共轭对称，即共轭对称，即 X(k)=X*(N-k),0kN-1 (3.2.19) (2)

22、如果如果 x(n)=x(N-n)，则，则X(k)实偶对称，即实偶对称，即 X(k)=X(N-k) (3.2.20) (3) 如果如果x(n)=-x(N-n)， 则则X(k)纯虚奇对称，即纯虚奇对称，即 X(k)=-X(N-k) (3.2.21) 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)27 利用利用DFT的共轭对称性，的共轭对称性， 通过计算通过计算一个一个N点点DFT， 可以得到可以得到两个两个不同实序列的不同实序列的N点点DFT。 设设x1(n)和和x2(n)为两个实序列，构成新序列为两个实序列，构成新序列x(n)如下：如下： x(n)=x1(n)+jx2(n) 对对x(n)进行

23、进行DFT，得到，得到 X(k)=DFTx(n)=Xep(k)+Xop(k) 由由(3.2.16)式、式、 (3.2.13)式、式、(3.2.14)式得到式得到 Xep(k)=DFTx1(n)=1/2X(k)+X*(N-k) Xop(k)=DFTjx2(n)=1/2X(k)-X*(N-k) 所以所以 X1(k)=DFTx1(n)=1/2X(k)+X*(N-k) X2(k)=DFTx2(n)=-j1/2X(k)-X*(N-k)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)282.1.4 DFT的矩阵计算的矩阵计算 DFT计算也可以采用矩阵计算法，这样可以计算也可以采用矩阵计算法，这样可以利用

24、计算机中的矩阵乘法子程序。利用计算机中的矩阵乘法子程序。第第2章章 离散傅里叶变换离散傅里叶变换(DFT)291. DFT的矩阵计算的矩阵计算 根据根据DFT定义有定义有 用一组线性方程表示为用一组线性方程表示为10k )()(10NWnxkXNnnkN， 2) 1() 1(210) 1(242012100000) 1()2() 1 ()0() 1( ) 1()2() 1 ()0()2( ) 1()2() 1 ()0() 1 ( ) 1()2() 1 ()0()0( NNNNNNNNNNNNNNNNNNNNNWNxWxWxWxNXWNxWxWxWxXWNxWxWxWxXWNxWxWxWxX第第

25、2章章 离散傅里叶变换离散傅里叶变换(DFT)30令令 x(n)=x(0)， x(1)， x(2)， x(N-1)T X(k)=X(0)， X(1)， X(2)， X(N-1)T则方程组可用矩阵表示为则方程组可用矩阵表示为 X(k)=ANx(n)2)1()1(210)1(242012100000NNNNNNNNNNNNNNNNNNNNNNWWWWWWWWWWWWWWWWA第第2章章 离散傅里叶变换离散傅里叶变换(DFT)312. IDFT的矩阵计算的矩阵计算 根据根据IDFT定义有定义有 类似地，可将逆变换表示为类似地，可将逆变换表示为 其中其中AN*是是AN的共轭矩阵，即的共轭矩阵，即10n

26、 )(1)(10NWkXNnxNknkN， )(1)(*kXANnxN2)1()1(2)1(0)1(2420)1(2100000*NNNNNNNNNNNNNNNNNNNNNNWWWWWWWWWWWWWWWWA第第2章章 离散傅里叶变换离散傅里叶变换(DFT)32 显然，当显然，当N确定时，确定时， AN与与AN*为常数矩阵，只要给为常数矩阵，只要给定定x(n)或或X(k)就可以通过矩阵计算出就可以通过矩阵计算出X(k)或或x(n)。 用计算机程序实现时，可以事先将用计算机程序实现时，可以事先将AN与与AN*存储存储在内存中。在内存中。 AN与与AN*中各元素由旋转因子中各元素由旋转因子 组成，

27、利用旋转组成，利用旋转因子的周期性，可将因子的周期性，可将AN与与AN*简化。即简化。即AN与与AN*中中实际只包含实际只包含N个不相同的元素：个不相同的元素： ， ， ， 或或 ， ， ， 因此，只要确定出上述因此，只要确定出上述N个值，即可确定个值，即可确定AN或或AN*。iNW0NW1NW2NW1 -NNW0NW1NW2NW)1( NNW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)33 有两种确定方法：有两种确定方法： (1) 定义计算定义计算 (2) 几何计算几何计算 将单位圆从正实轴开始将单位圆从正实轴开始N等分，等分点在等分，等分点在Z平面上的平面上的坐标即确定了坐标即确定了

28、 的值。的值。 对于对于AN， 按按i=0N-1在在单位圆上顺时针取点单位圆上顺时针取点； 对于对于AN*， 按按i=0N-1在在单位圆上逆时针取点单位圆上逆时针取点。iNWiNjiNeW)(2iNWiNWiNW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)34以以N=8为例计算为例计算AN与与AN*。显然有，显然有，187828683858484858386828781808222222221222222221WjWWjWWjWWWWjWWjWWjWW08W18W28W38W48W58W68W78W18W28W38W48W58W68W78W第第2章章 离散傅里叶变换离散傅里叶变换(DFT

29、)35于是182838485868780828486808284868083868184878285808480848084808480858287848186838086848280868482808786858483828180808080808080808088WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWA 1828384858687808284868082848680838681848782858084808480848084808582878481868380868482808684828087868

30、58483828180808080808080808088WWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWWA第第2章章 离散傅里叶变换离散傅里叶变换(DFT)36例：计算例：计算x(t)=cos(2t)的频谱。的频谱。解解:(1)对对x(t)采样采样 根据采样定理，余弦信号一周至少采根据采样定理，余弦信号一周至少采3个点，取个点，取N=4， 则则 x(n)=1,0,-1,0T (2)求求X(k) (3)将将X(k)的观察区间位移到的观察区间位移到-N/2N/2-1，得，得 X(-2)=0, X(-1)=2, X(0

31、)=0, X(1)=2, (4)离散频谱与连续频谱的对比离散频谱与连续频谱的对比 频域采样间隔频域采样间隔f=1/T0=1/TP=1 由图中可看出由图中可看出 X(f)=(1/N)X(k) (f=kf) 该结论证明略。该结论证明略。20200101111111111111)()3()2() 1 ()0()(4jjjjnxAXXXXkXX(f)1/21/2-11fX(k)22-11k第第2章章 离散傅里叶变换离散傅里叶变换(DFT)37 时域时域 频域频域 非周期，连续非周期，连续 x(t) X(j)或或X(f) 非周期，连续非周期，连续 无限长序列无限长序列 x(n) X(ej) 周期，连续周

32、期，连续周期周期N(T0)，序列，序列 x(n) X(k) 周期周期N (1/T=fs) ,离散离散 时域采样间隔时域采样间隔T t=nT f=k(1/T0) 频域采样间隔频域采样间隔1/T0 = kf f X(f)=(1/N)X(k) (f=kf) =2f =T第第2章章 离散傅里叶变换离散傅里叶变换(DFT)382.2 快速傅里叶变换快速傅里叶变换(FFT) 频谱分析作为信号处理的基本工具已在多学科领频谱分析作为信号处理的基本工具已在多学科领域得到应用。然而域得到应用。然而DFT运算量大，使应用受到限制。运算量大，使应用受到限制。 1965年，库利年，库利图基图基(Cooley-Tukey

33、)发表了快速计发表了快速计算算DFT的方法，使的方法，使DFT得到实际应用，并由此发展成得到实际应用，并由此发展成为称之为快速傅立叶变换为称之为快速傅立叶变换(FFT)的一类算法。的一类算法。 FFT仅是仅是DFT的一类特殊计算方法。它的价值在的一类特殊计算方法。它的价值在于：将于：将DFT的计算时间减少的计算时间减少12个数量级（甚至性能改个数量级（甚至性能改善达善达100倍之多）。它的重要性在于：明显地证明了采倍之多）。它的重要性在于：明显地证明了采用数字方法进行频谱分析较之用模拟方法更经济。用数字方法进行频谱分析较之用模拟方法更经济。第第2章章 离散傅里叶变换离散傅里叶变换(DFT)39

34、 2.2.1 FFT原理原理 长度为长度为N的有限长序列的有限长序列x(n)的的DFT为为 考虑考虑x(n)为复数序列的一般情况，对某一个为复数序列的一般情况，对某一个k值，直值，直接按接按(4.2.1)式计算式计算X(k)值需要值需要N次复数乘法、次复数乘法、(N-1)次复数加法，次复数加法，N点点DFT的复乘次数为的复乘次数为N2，复加次数，复加次数为为N(N-1)。10( )( ),0,1,1NknNnX kx n WkN(4.2.1) 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)40 FFT的基本原理是：把的基本原理是：把N点序列的点序列的DFT逐次分解为逐次分解为若干个较短序列

35、若干个较短序列DFT的线性组合。的线性组合。 分解的效果是：分解的效果是：DFT的乘法和加法次数大大减少。的乘法和加法次数大大减少。 分解的方法不同，导致不同的分解的方法不同，导致不同的FFT算法。算法。 在在FFT算法中，普遍利用了旋转因子算法中，普遍利用了旋转因子WNm的周期性的周期性和对称性。即周期性为和对称性。即周期性为 对称性为对称性为22()jm lNjmm lNmNNNNWeeW(4.2.2) 2mN mN mmNNNNNmmNNWWWWWW 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)41 以一种序列分解法以一种序列分解法-时间抽取法为例说明时间抽取法为例说明FFT原理。

36、原理。 设设N为合数，即为合数，即N=ML，则，则N点序列可分解为点序列可分解为M个个L点的新序列，即点的新序列，即x(n)=x(0), x(1), x(2), , x(N-1) 分解为分解为 x(iM)=x(0),x(M), x(2M), , x(L-1)M) x(iM+1)=x(1), x(M+1),x(2M+1), , x(L-1)M+1) x(iM+M-1)=x(M-1), x(2M-1),x(3M-1), , x(L-1)M+ M- 1)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)42由此，由此，DFT可写为可写为式中，复数乘法次数：式中，复数乘法次数：ML2+NM=N(M+L

37、) 复数加法次数：复数加法次数：ML(L-1)+N(M-1)=N(M+L-2)当当L、M均大于均大于1时，有时，有 N(M+L)N2 N(M+L-2)N(N-1)即分解减少了计算次数。即分解减少了计算次数。)1(10)1(101010)1(10)1(1010) 1() 1()() 1() 1()() 1() 1()()()(MkNLkNLLLiMkNkiLLikNkiLLikiLLiMiMkNLiiMkNLikiMNNnnkNWMiMxDFTWiMxDFTiMxDFTWWMiMxWWiMxWiMxWMiMxWiMxWiMxWnxkX第第2章章 离散傅里叶变换离散傅里叶变换(DFT)43 若若L

38、也为合数的话，则上述分解可继续，从而使也为合数的话，则上述分解可继续，从而使计算次数进一步降低。计算次数进一步降低。 当当N=P1P2 P3 Pk时，按上述逐次分解方法可时，按上述逐次分解方法可得计算次数为得计算次数为 复数乘法：复数乘法：N(P1+P2 + P3 + + Pk) 复数加法：复数加法：N(P1+P2 + P3 + + Pk-k) 当当Pi各不相同时，按上述逐次分解方法得到的各不相同时，按上述逐次分解方法得到的FFT算法称为混基算法称为混基FFT；当；当Pi=r (即即N=rk)时，得到的时，得到的FFT算算法称为基法称为基r FFT； 当当r=2时，得到常用的基时，得到常用的基

39、2 FFT。第第2章章 离散傅里叶变换离散傅里叶变换(DFT)442.2.2 基基2 FFT1. 时间抽取法时间抽取法 设序列设序列x(n)的长度为的长度为N，且满足，且满足按按n的奇偶把的奇偶把x(n)分解为两个分解为两个N/2点的子序列点的子序列2 ,MNM为自然数为自然数 12( )(2 ),0,1,12( )(21),0,1,12Nx rxrrNx rxrr第第2章章 离散傅里叶变换离散傅里叶变换(DFT)45则则x(n)的的DFT为为其中其中kNNrkNrkNNrrkNNrkNrkNNrrkNNrkrNNrrkNnnkNnnkNNnnkNWKXKXWWrxWrxWWrxWrxWrxW

40、rxWnxWnxWnxkX)()( )()( ) 12()2( ) 12()2( )()()()(211202/21202/11202/1202/120)12(120210奇数偶数222222/2jkrNjkrkrkrNNNWeeW kr第第2章章 离散傅里叶变换离散傅里叶变换(DFT)46由于由于X1(k)和和X2(k)均以均以N/2为周期，且为周期，且所以所以X(k)又可表示为又可表示为2NkkNNWW 1212( )( )( )0,1,12()( )( )0,1,122kNkNNX kXkW XkkNNX kXkW Xkk(4.2.7) ( 4 . 2 .8) CABA BCA BC图图

41、4.2.1 蝶形运算符号蝶形运算符号 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)47图图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)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)48 与第一次分解相同，将与第一次分解相同，将x1(r)按奇偶分解成两个按奇偶分解成两个N/4长的子序列长的子序列x3(

42、l)和和x4(l)，即，即 那么，那么，X1(k)又可表示为又可表示为 同理，由同理，由X3(k)和和X4(k)的周期性和的周期性和Wm N/2的对称性得：的对称性得：3241( )(2 ),0,1,1( )(21)4x lxlNlx lxl1/4 1/4 12(21)11/21/200/4 1/4 13/4/24/4003/24( )(2 )(21)( )( )( )( ),0,1,/2 1NNklklNNiiNNklkklNNNiikNX kxl WxlWx l WWx l Wx kWX k kN(4.2.9) )(3kX13/2413/24( )( )( ),0,1,/41(/4)( )

43、( )kNkNX kXkWXkkNX kNXkWXk(4.2.10) 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)49用同样的方法可计算出用同样的方法可计算出其中其中25/2625/26( )( )( ),0,1,/41(/4)( )kNkNXkXkWXkkNXkNX kWXk(4.2.11)/4 155/450/4 166/4605262( )( )( )( )( )( )( )(2 ),0,1,/41( )(21)NklNiNklNiXkx l WDFT x lXkx l WDFT x lx lxllNx lxl第第2章章 离散傅里叶变换离散傅里叶变换(DFT)50图图4.2.3 N

44、点点DFT的第二次时域抽取分解图的第二次时域抽取分解图(N=8) N/4点DFTWN12WN12WN0WN1WN2WN3X1(0)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)x(0)X3(0)X3(1)X4(0)X4(1)x(4)x(2)x(6)x(1)x(5)x(3)x(7)N/4点DFTN/4点DFTN/4点DFTWN02WN02第第2章章 离散傅里叶变换离散傅里叶变换(DFT)51图图4.2.4 N点时域抽取点时域抽取FFT运算流图运算流图(N=8) 蝶形运算，同址计算，序列倒序，系数蝶形运算，同址

45、计算，序列倒序，系数WNr确定确定WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0 x(0)x(4)x(2)x(6)x(1)x(5)x(3)x(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)A(0)A(7)X(0)X(1)X(2)X(3)X(4)X(5)X(6)X(7)A(0)A(1)A(2)A(3)A(4)A(5)A(6)A(7)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)52算法复杂度：算法复杂度： 设设P(N)表示表示N点点DFT所需复数乘法计算次数，所需复数乘法计算次数，

46、Q(N)表示表示N点点DFT所需复数加法计算次数，则按时间抽取法所需复数加法计算次数，则按时间抽取法得到得到 当将当将DFT最终分解为最终分解为2点时，点时，P(2)=1，Q(2)=2。将此初始。将此初始条件带入上式递归求解得条件带入上式递归求解得 取取N=1024，基，基2FFT速度速度 比比DFT提高提高200倍。倍。NNQNQNNPNP)2(2)(2)2(2)(NNNQNNNP22log)(log2)(20051024log222NNN第第2章章 离散傅里叶变换离散傅里叶变换(DFT)53图图4.2.5 FFT算法与算法与DFT定义计算之间乘法次数比较曲线定义计算之间乘法次数比较曲线 第

47、第2章章 离散傅里叶变换离散傅里叶变换(DFT)54 2. 频率抽取法频率抽取法 设序列设序列x(n)长度为长度为N=2M，首先将，首先将x(n)前后对半分前后对半分开，得到两个子序列，其开，得到两个子序列，其DFT可表示为如下形式：可表示为如下形式：10/2 110/2/2 1/2 1(/2)00/2 1/20( ) ( )( )( )( )( )()2 ( )()2NkNnNNknknNNnn NNNknk n NNNnnNkNknNNnX kDFT x nx n Wx n Wx n WNx n Wx nWNx nWx nW第第2章章 离散傅里叶变换离散傅里叶变换(DFT)55将将X(k)

48、分为偶数与奇数组，当分为偶数与奇数组，当k取偶数取偶数(k=2r,r=0,1,N/2-1)时时当当k取奇数取奇数(k=2r +1, r =0,1,N/2-1)时时/21,( 1)1kNkNkWk 偶数 奇数 /2 1(21)0/2 1/20(21) ( )()2 ( )()2NnrNnNnnrNNnNXrx nx nWNx nx nWW(4.2.15)/ 2 120/ 2 12/ 20(2 ) ( )()2 ( )()2NrnNnNrnNnNXrx nx nWNx nx nW(4.2.14)rn第第2章章 离散傅里叶变换离散傅里叶变换(DFT)56将将x1(n)和和x2(n)分别代入分别代入(

49、4.2.14)和和(4.2.15)式，可得式，可得/2 11/20/2 12/20(2 )( )(21)( )NrnNnNrnNnXrx n WXrx n W (4.2.16) 图图4.2.10 DIFFFT蝶形运算流图符号蝶形运算流图符号 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)57图图4.2.12 DIFFFT二次分解运算流图二次分解运算流图(N=8) N/4点DFTWN0WN1WN2WN3x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)WN0WN2WN0WN2N/4点DFTN/4点DFTN/4点DF

50、T第第2章章 离散傅里叶变换离散傅里叶变换(DFT)58图图4.2.13 DIFFFT运算流图运算流图(N=8) WN0WN1WN2WN3WN0WN2WN0WN2WN0WN0WN0WN0X(0)X(4)X(2)X(6)X(1)X(5)X(3)X(7)x(0)x(1)x(2)x(3)x(4)x(5)x(6)x(7)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)593. DFT程序程序#include #include #include #include msp.hvoid mcmpdft(complex x, complex y, int n, int isign)/*- Routinue

51、mcmpdft: Directly to Compute the DFT/IDFT of Complex Data x(n) By DFT definition. If ISIGN=-1: For Forward Transform; ISIGN=1 : For Inverse Transform.-*/ complex t,ts,z; float pi2; int m,k; pi2=8.*atan(1.); t.real=0.;t.imag=isign*pi2/n; ts.real=0.0; for(m=0;mn;m+) ym=x0; for(k=1;kn;k+) ts.imag=t.ima

52、g*k*m; z=cexp(ts); ym.real+=xk.real*z.real-xk.imag*z.imag; ym.imag+=xk.real*z.imag+xk.imag*z.real; if(isign=1) ym.real/=n; ym.imag/=n; 第第2章章 离散傅里叶变换离散傅里叶变换(DFT)604. FFT程序程序#include #include #include #include msp.hvoid mcmpfft(complex x,int n,int isign)/*- Routine mcmpfft : to obtain the DFT of Compl

53、ex Data x(n) By Cooley-Tukey radix-2 DIT Algorithm . input parameters: x : complex array. input signal is stored in x(0) to x(n-1). n : the dimension of x and y. isign: if ISIGN=-1 For Forward Transform if ISIGN=+1 For Inverse Transform. output parameters: x : complex array. DFT result is stored in

54、x(0) to x(n-1). Notes: n must be power of 2.-*/ complex t,z,ce; float pisign; int mr,m,l,j,i,nn; for(i=1;i16) printf( N is not a power of 2 ! n); return; z.real=0.0; pisign=4*isign*atan(1.); mr=0; for(m=1;m=n)l=l/2; mr=mr%l+l; if(mr=n) if(isign=-1) return; for(j=0;jn;j+) xj.real=xj.real/n; xj.imag=x

55、j.imag/n; return; for(m=0;ml;m+) for(i=m;in;i=i+2*l) z.imag=m*pisign/l; ce=cexp(z); t.real=xi+l.real*ce.real -xi+l.imag*ce.imag; t.imag=xi+l.real*ce.imag +xi+l.imag*ce.real; xi+l.real=xi.real-t.real; xi+l.imag=xi.imag-t.imag; xi.real=xi.real+t.real; xi.imag=xi.imag+t.imag; l=2*l; 第第2章章 离散傅里叶变换离散傅里叶变

56、换(DFT)622.2.3 利用利用FFT计算计算IDFT DFT和和IDFT的运算公式为：的运算公式为： 由于由于 对上式两边同时取共轭，得对上式两边同时取共轭，得 可见，利用可见，利用FFT也可计算也可计算IDFT。10101( )( )1( )( )NknNkNknNkx nX k WNx nXk WN1011( )( )( )NknNkx nXk WDFT XkNN1010( ) ( )( )1( ) ( )( )NkNnNknNkX kDFT x nx n Wx nIDFT x nX k WNnX(k)第第2章章 离散傅里叶变换离散傅里叶变换(DFT)632.3 离散卷积离散卷积 由

57、于卷积运算可以描述线性时不变系统，因此它在信号由于卷积运算可以描述线性时不变系统，因此它在信号处理中具有重要作用。离散系统中的卷积用离散卷积计算。处理中具有重要作用。离散系统中的卷积用离散卷积计算。 2.3.1 定义定义 若若x1(n)与与x2(n)是宽度为是宽度为N的有限时宽序列，则的有限时宽序列，则 定义为定义为x1(n)与与x2(n)的离散卷积，记作的离散卷积，记作x1(n)* *x2(n)。 因为离散信号（有限时宽序列）被看作周期序列，因此因为离散信号（有限时宽序列）被看作周期序列，因此y(n)也具有周期特性，且周期为也具有周期特性，且周期为N，故离散卷积又称作循环，故离散卷积又称作循

58、环卷积。卷积。1-Nn0 )()()(1021Nmmnxmxny第第2章章 离散傅里叶变换离散傅里叶变换(DFT)642.3.2 循环卷积定理循环卷积定理若若x1(n) X1(k)， x2(n) X2(k)，则，则 x1(n)* *x2(n) X1(k)X2(k)或或 x1(n)x2(n) 1/N(X1(k)* *X2(k) 。卷积定理指出了相乘与卷积运算的关系，同时给出了卷卷积定理指出了相乘与卷积运算的关系，同时给出了卷积运算的另一途径，即积运算的另一途径，即由卷积定理也可以推论出由卷积定理也可以推论出x1(n)* *x2(n) 的周期为的周期为N。DFTDFTx1(n)x2(n)X1(k)

59、X2(k)x1(n)*x2(n)X1(k)X2(k)IDFT第第2章章 离散傅里叶变换离散傅里叶变换(DFT)652.3.3 循环卷积与线性卷积的关系循环卷积与线性卷积的关系设设x1(n)与与x2(n)是宽度分别为是宽度分别为N1、N2的有限时宽序列，则的有限时宽序列，则循环卷积：循环卷积：线性卷积：线性卷积：其中，循环卷积长度其中，循环卷积长度 N3=maxN1，N2 线性卷积长度线性卷积长度 N4=N1+N2-1 显然，显然，N3 N且与且与N数量级相同）；数量级相同）；. 对对h(n)与与xi(n)分别作分别作L(N+M-1)点的点的DFT，得到，得到H(k)与与Xi(k) ；(用用FF

60、T). 对对H(k)Xi(k)求出求出L点点IDFT得得h(n)* *xi(n)=yi(n)；(用用FFT). 对各段卷积求和，即对各段卷积求和，即注：该方法中，各段注：该方法中，各段yi(n)是以线性卷积计算的。是以线性卷积计算的。0)()(iinyny第第2章章 离散傅里叶变换离散傅里叶变换(DFT)76图图 3.4.4 重叠相加法卷积示意图重叠相加法卷积示意图 M0NMMx1(n)x0(n)x2(n)N M 1N M 1y0(n)y1(n)N M 1y2(n)2MM3M N 10N 1y(n) y0(n) y1(n) y2(n) nnnnnnh(n)第第2章章 离散傅里叶变换离散傅里叶变换(DF