数字信号处理离散傅里叶变换ppt课件

1、第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)第第3章章 离散傅里叶变换离散傅里叶变换(DFT)第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 本章作为全书的基础，主要学习本章作为全书的基础，主要学习: (1) DFT的定义；的定义； (2) DFT的物理意义；的物理意义； (3) DFT的基本性质以及频域采样；的基本性质以及频域采样； (4)DFT的应用举例等内容。的应用举例等内容。第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)离散傅里叶变换定义离散傅里叶变换定义计算机只能处理有限长离散序列，因而计算机只能处理有限长离散序列，因而无法直接

2、利用无法直接利用ZT与与FT进行数值计算。进行数值计算。针对有限长序列针对有限长序列, 还有一种更有用的数学还有一种更有用的数学变换变换, 即离散傅里叶变换即离散傅里叶变换Discrete Fourier Transform），使数字信号处理），使数字信号处理可以在频域采用数字运算的方法进行，可以在频域采用数字运算的方法进行，大大增加了数字信号处理的灵活性。大大增加了数字信号处理的灵活性。第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)DFT的实质：有限长序列傅里叶变换的的实质：有限长序列傅里叶变换的有限点离散采样，即频域离散化。有限点离散采样，即频域离散化。DFT有多种快速算

3、法有多种快速算法(Fast Fourier Transform), 因此不仅在理论上有重要意因此不仅在理论上有重要意义义, 在各种数字信号处理算法中亦起着核在各种数字信号处理算法中亦起着核心作用。从而使信号的实时处理和设备心作用。从而使信号的实时处理和设备的简化得以实现。的简化得以实现。第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)DFT DFT 的定义的定义 设设x(n)x(n)是一个长度为是一个长度为MM的有限长序的有限长序列，列， 则定义则定义x(n)x(n)的的NN点离散傅里叶点离散傅里叶变换为：变换为： N-1knNn=0X(k)= DFTx(n) =x(n)W,

4、k =0, 1,. , N -1 X(k)的离散傅里叶逆变换为：的离散傅里叶逆变换为：N-1-knNn=01x(n)=IDFTX(k)=X(k)W, n=0, 1, ., N-1 N第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 对式中，对式中，NN称为称为DFTDFT变换区间长度，变换区间长度，NMNM。通常称上述二式为离散傅里叶变换对。为了叙。通常称上述二式为离散傅里叶变换对。为了叙述简洁，常常用述简洁，常常用DFTDFTx(n)x(n)NN和和IDFTIDFTX(k)X(k)NN分别表示分别表示NN点离散傅里叶变换和点离散傅里叶变换和NN点离散傅里叶逆变点离散傅里叶逆变

5、换。换。2-jNNW= e第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)【例】【例】 x(n)=R4(n), x(n)=R4(n), 求求x(n)x(n)的的8 8点和点和1616点点DFTDFT。【解】（【解】（1 1设变换区间设变换区间N=8 N=8 时，那么：时，那么： ) ) , 0,1.,7kk 473knkn888kn=0n=081-WX(k)=x(n)W=W=1-W1-(-=1-(-sin()sin()2 2-j4k-j4k-jkjk-jk-jkjk-jk8 82222222 2-jk-jkjk-jk-jk-jkjk-jk888888883 3-jk-jk8 8

6、eeeeeeeeeeeeeeeek k2 2e ek k8 8第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) （2 2设变换区间设变换区间N=16 N=16 时，那么：时，那么：) ) , 0,1.,15kk 4153knkn161616kn=0n=0161 -WX(k) =x(n)W=W=1 -W1 -(-=1 -(-sin()sin()2 2- -j j4 4k k- -j jk kj jk k- -j jk k1 16 64 44 44 42 2- -j jk k- -j jk kj jk k- -j jk k1 16 61 16 61 16 61 16 63 3- -

7、j jk k1 16 6e ee ee ee ee ee ee ee ek k4 4e ek k1 16 6第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)X(n)X(n)的幅频的幅频特性曲线特性曲线(FT(FT曲线曲线) )X(n)X(n)的的8 8点点DFTDFT曲线曲线X(n)X(n)的的1616点点DFTDFT曲线曲线第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)结论结论: 由此例可见，由此例可见，x(n)x(n)的离散傅里叶变换结果与变换区的离散傅里叶变换结果与变换区间长度间长度NN的取值有关。在后面，对的取值有关。在后面，对DFTDFT与与Z Z变

8、换和傅里变换和傅里叶变换的关系及叶变换的关系及DFTDFT的物理意义进行讨论后，上述问的物理意义进行讨论后，上述问题就会得到解释。题就会得到解释。 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)DFT与傅里叶变换和与傅里叶变换和Z变换的关系变换的关系 设序列设序列x(n)的长度为的长度为M，其，其Z变换变换和和N(NM)点点DFT分别为：分别为：1010( )ZT ( )( )( )DFT ( )( )0,1,1MnnMknNNnX zx nx n zX kx nx nWkN第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 上二式表明序列x(n)的N点DFT是

9、x(n)的Z变换在单位圆上的N点等间隔采样。X(k)为x(n)的傅里叶变换。j2( )(e )|0,1,1kNX kXkN比较上面二式可得关系式比较上面二式可得关系式 2je( )( )0,1,1kNzX kX zkN或或第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) DFT是 X(ej)在区间0, 2上的N点等间隔采样。这就是DFT的物理意义。 DFT的变换区间长度N不同，表示对X(ej)在区间0, 2上的采样间隔和采样点数不同，所以DFT的变换结果不同。DFT的物理意义的物理意义第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)knNWDFT的隐含周期性的隐

10、含周期性 在在DFT变换对中，变换对中，x(n)与与X(k)均为有限均为有限长序列，但由于的周期性，使长序列，但由于的周期性，使DFT和和IDFT式中的式中的X(k)隐含周期性，且周期均为隐含周期性，且周期均为N。对任意整数对任意整数m，总有，总有 在在DFT式中，式中，Xk)满足：满足： (),kkmNNNNWWk m为整数,为自然数，11()00()( )( )( )NNkmN nknNNnnX kmNx n Wx n WX k第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)实际上，任何周期为实际上，任何周期为NN的周期序列都可的周期序列都可以看做长度为以看做长度为NN的有

11、限长序列的有限长序列x(n)x(n)的周期延的周期延拓序列，而拓序列，而x(n)x(n)则是的一个周期，即则是的一个周期，即( )()mx nx nmN( )( )( )Nx nx nRn( )x n( )x n第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)一般称周期序列中从n=0到N1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列。因此x(n)与的上述关系可叙述为：是x(n)的周期延拓序列，x(n)是的主值序列。)(nx)(nx)(nx)(nx)(nx)(nx第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)为了以后叙述简洁，当N大于等于序列x(n

12、)的长度时，将式用如右形式表示： 式中x(n) N表示x(n)以N为周期的周期延拓序列，(n)N表示模N对n求余，即如果 n=MN+n1 0n1N1, M为整数那么(n)N=n1 ( )( )Nx nx n( )()mx nx nmN第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)例如，例如，, 则有则有所得结果符合下图所示的周期延拓规律。所得结果符合下图所示的周期延拓规律。88, ( )( )Nx nx n88(8)(8)(0)(9)(9)(1)xxxxxx第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 如果x(n)的长度为N，且，则可写出的离散傅里叶级数表

13、示式Nnxnx)()(111000( )( )( )( )NNNknknknNNNNnnnX kx n Wx nWx n W110011( )( )( )NNknknNNkkx nX k WX k WNN)(nx式中式中( )( )( )NX kX k Rk即即X(k)为的主值序列。为的主值序列。( )X k第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 因此可知，有限长序列x(n)的N点离散傅里叶变换X(k)正好是x(n)的周期延拓序列x(n)N的离散傅里叶级数系数的主值序列，即 。后面要讨论的频域采样理论将会加深对这一关系的理解。我们知道，周期延拓序列频谱完全由其离散傅里

14、叶级数系数确定，因此，X(k)实质上是x(n)的周期延拓序列x(n) N的频谱特性，这就是N点DFT的物理意义。( )X k)()()(kRkXkXN( )X k第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)离散傅里叶变换的基本性质1 线性性质线性性质 如果如果x1(n)和和x2(n)是两个有限长序列，是两个有限长序列， 长度分别为长度分别为N1和和N2,且且 y(n)=ax1(n)+bx2(n)式中式中a、 b为常数，为常数， 即即N=maxN1, N2， 则则y(n)的的N点点DFT为为 Y(k)=DFTy(n)=aX1(k)+bX2(k), 0kN-1其中其中X1(k)

15、和和X2(k)分别为分别为x1(n)和和x2(n)的的N点点DFT。 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)2 循环移位性质：循环移位性质： (1) 序列的循环移位序列的循环移位 设设x(n)为有限长序列，为有限长序列， 长度为长度为N， 则则x(n)的循环移位定义为的循环移位定义为 y(n)=x(n+m)NRN(N) 循环移位过程如下图所示循环移位过程如下图所示: 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)循环移位过程示意图循环移位过程示意图 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) (2) 时域循环移位定理： 设x(n

16、) 是长度为N的有限长序列， y(n)为x(n)的循环移位， 即 y(n)=x(n+m)NRN(n) 那么 Y(k)=DFTy(n) 其中 X(k)=DFTx(n), 0kN-1。 ( )kmNWX k第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)（3频域循环移位定理，假设频域循环移位定理，假设 X(k)=DFTx(n), 0kN-1 Y(k)=X(k+l)NRN(k) 那么那么 y(n)=IDFTY(k)n( )lNWx n第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)3 循环卷积定理循环卷积定理 有限长序列有限长序列x1(n)和和x2(n)， 长度分别长

17、度分别为为N1和和N2， N=maxN1, N2。 x1(n)和和x2(n)的的N点点DFT分别为：分别为： X1(k)=DFTx1(n) X2(k)=DFTx2(n) 假设假设 X(k)=X1(k)X2(k) 那么那么1120( ) ( )( ) ()( )NNNmx nIDFT X kx m xn mR n1210( ) ( )( ) ()( )NNNmx nIDFT X kx m x n mR n或或上式所表示的运算称为上式所表示的运算称为x1(n)x1(n)与与x2(n)x2(n)的循环卷积。的循环卷积。第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 循环卷积过程中，

18、 要求对x2(m)循环反转， 循环移位， 特别是两个N长的序列的循环卷积长度仍为N。 显然与一般的线性卷积不同， 故称之为循环卷积， 记为 121120( )( )( ) ( )()( )NNNmx nx nx nx m xnmRn第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)1221( ) ( )( )( )( )( )X kDFT x nX kXkXkX k由于由于 所以所以 1221( )( )( )( )( )( )x nIDFT X kx nx nx nx n即循环卷积亦满足交换律。即循环卷积亦满足交换律。 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(D

19、FT)频域循环卷积定理：频域循环卷积定理： 假设假设 x(n)=x1(n)x2(n) 那么那么1211202112101( ) ( )( )( )1( )()( )1( )( )( )1( )()( )NNNlNNNlX kDFT x nX kXkNX l XklRkNX kXkX kNXl XklRkN或第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 直接计算循环卷积较麻烦。计算机中采用矩阵相乘或快速傅里叶变换FFT的方法计算循环卷积。下面介绍用矩阵计算循环卷积的公式。 第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)(0)(1)(2)(1)(1)(0)(1

20、)(2)(2)(1)(0)(3)(1)(2)(3)(0)xx Lx Lxxxx Lxxxxxx Lx Lx Lx 当n = 0, 1, 2, , L1时，由x(n)形成的序列为： x(0), x(1), , x(L1)。循环移位后可得下面的矩阵：第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)上面矩阵称为上面矩阵称为x(n)的的L点点“循环卷积矩阵循环卷积矩阵”，其特点，其特点是是:（1） 第第1行是序列行是序列x(0), x(1), , x(L1)的的循环倒相序列。留意，如果循环倒相序列。留意，如果x(n)的长度的长度ML，则需，则需要在要在x(n)末尾补末尾补LM个零后，再

21、形成第一行的循环个零后，再形成第一行的循环倒相序列。倒相序列。（2） 第第1行以后的各行均是前一行向右循环移行以后的各行均是前一行向右循环移1位形成的。位形成的。（3） 矩阵的各主对角线上的序列值均相等。矩阵的各主对角线上的序列值均相等。有了上面介绍的循环卷积矩阵，就可以写出有了上面介绍的循环卷积矩阵，就可以写出y(n)c的矩阵形式如下的矩阵形式如下:第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)cccc(0)(0)(1)(2)(1)(0)(1)(1)(0)(1)(2)(1)(2)(2)(1)(0)(3)(2)(1)(1)(2)(3)(0)(1)yxx Lx Lxhyxxx Lxhyxxxxh