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

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

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

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

4、里叶逆变换离散傅里叶逆变换为：为：N-1-knNn=01x(n)=IDFTX(k)=X(k)W,n=0,1,.,N-1 N5第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)对式中，对式中，N称为称为DFT变换变换区间长度，区间长度，NM。通常称上述二式为离散。通常称上述二式为离散傅里叶变换对。为了叙述简洁，常常用傅里叶变换对。为了叙述简洁，常常用DFTx(n)N和和IDFTX(k)N分别表示分别表示N点离散傅里叶变换和点离散傅里叶变换和N点离散傅里叶逆点离散傅里叶逆变换。变换。2-jNNW=e6第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)【例例】x(n)=R

5、4(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 8eeeeeeeeeeeeeeeek k2 2e ek k8 87第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)（2 2）设变换区间）设变换区间N=1

6、6 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-j jk k1 16 6e ee ee ee ee ee ee ee ek k4 4e ek k1 16 68第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)X(nX(n)的幅频的幅频特性曲线特性

7、曲线(FT(FT曲线曲线)X(nX(n)的的8 8点点DFTDFT曲线曲线X(nX(n)的的1616点点DFTDFT曲线曲线9第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)结论结论:由此例可见，由此例可见，x(nx(n)的离散傅里叶变换结果与的离散傅里叶变换结果与变换区间长度变换区间长度NN的取值有关。在后面，对的取值有关。在后面，对DFTDFT与与Z Z变换和傅里叶变换的关系及变换和傅里叶变换的关系及DFTDFT的物理意的物理意义进行讨论后，上述问题就会得到解释。义进行讨论后，上述问题就会得到解释。10第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)DFT与

8、傅里叶变换和与傅里叶变换和Z变换的关系变换的关系 设序列设序列x(n)的长度为的长度为M，其，其Z变换和变换和N(NM)点点DFT分别为：分别为：1010()ZT()()()DFT()()0,1,1MnnMknNNnX zx nx n zX kx nx nWkN11第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)上二式表明序列上二式表明序列x(n)的的N点点DFT是是x(n)的的Z变换在单位圆上的变换在单位圆上的N点等间隔采样。点等间隔采样。X(k)为为x(n)的傅里叶变换。的傅里叶变换。j2()(e)|0,1,1kNX kXkN比较上面二式可得关系式比较上面二式可得关系式 2

9、je()()0,1,1kNzX kX zkN或或12第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)DFT是是 X(ej)在区间在区间0,2上的上的N点等点等间隔采样。这就是间隔采样。这就是DFT的物理意义的物理意义。DFT的变换区间长度的变换区间长度N不同，表示对不同，表示对X(ej)在区间在区间0,2上的采样间隔和采样上的采样间隔和采样点数不同，所以点数不同，所以DFT的变换结果不同。的变换结果不同。DFT的物理意义的物理意义13第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)knNWDFT的隐含周期性的隐含周期性 在在DFT变换对中，变换对中，x(n)与与

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

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

12、里叶变换离散傅里叶变换(DFT)(DFT)为了以后叙述简洁，当为了以后叙述简洁，当N大于等于序列大于等于序列x(n)的长度时，将式的长度时，将式用如右形式表示：用如右形式表示：式中式中x(n)N表示表示x(n)以以N为周期的周期延拓序为周期的周期延拓序列，列，(n)N表示模表示模N对对n求余，即如果求余，即如果 n=MN+n1 0n1N1,M为整数为整数则则(n)N=n1 ()()Nx nx n()()mx nx nmN17第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)例如，例如，,则有则有所得结果符合下图所示的周期延拓规律。所得结果符合下图所示的周期延拓规律。88,()()

13、Nx nx n88(8)(8)(0)(9)(9)(1)xxxxxx18第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)如果如果x(n)的长度为的长度为N，且，则，且，则可写出的离散傅里叶级数表示式可写出的离散傅里叶级数表示式Nnxnx)()(111000()()()()NNNknknknNNNNnnnX kx n Wx nWx n W110011()()()NNknknNNkkx nX k WX k WNN)(nx式中式中()()()NX kX k Rk即即X(k)为的主值序列为的主值序列。()X k19第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)因此可知，

14、有限长序列因此可知，有限长序列x(n)的的N点离散傅里叶变点离散傅里叶变换换X(k)正好是正好是x(n)的周期延拓序列的周期延拓序列x(n)N的离散傅里的离散傅里叶级数系数的主值序列，即叶级数系数的主值序列，即 。后面要讨论的频域采样理论将会加深对这一关系的后面要讨论的频域采样理论将会加深对这一关系的理解。我们知道，周期延拓序列频谱完全由其离散理解。我们知道，周期延拓序列频谱完全由其离散傅里叶级数系数确定，因此，傅里叶级数系数确定，因此，X(k)实质上是实质上是x(n)的周期延拓序列的周期延拓序列x(n)N的频谱特性，这就是的频谱特性，这就是N点点DFT的物理意义。的物理意义。()X k)()

15、()(kRkXkXN()X k20第第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)和和X2(k)分别为分别为x1(n)和和x2(n)的的N点点DFT。21第第7 7讲讲 离散傅里叶变换离散傅里叶变换

16、(DFT)(DFT)2 循环移位性质：循环移位性质：(1)序列的循环移位序列的循环移位 设设x(n)为有限长序列，为有限长序列，长度为长度为N，则则x(n)的循环移位定义为的循环移位定义为 y(n)=x(n+m)NRN(N)循环移位过程如下图所示循环移位过程如下图所示:22第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)循环移位过程示意图循环移位过程示意图 23第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)(2)时域循环移位定理：时域循环移位定理：设设x(n)是长度为是长度为N的有限长序列，的有限长序列，y(n)为为x(n)的循环移位，的循环移位，即即 y(n

17、)=x(n+m)NRN(n)则则 Y(k)=DFTy(n)其中其中 X(k)=DFTx(n),0kN-1。()kmNWX k24第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)（3）频域循环移位定理，如果）频域循环移位定理，如果 X(k)=DFTx(n),0kN-1 Y(k)=X(k+l)NRN(k)则则 y(n)=IDFTY(k)n()lNWx n25第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)3 循环卷积定理循环卷积定理 有限长序列有限长序列x1(n)和和x2(n)，长度分别为长度分别为N1和和N2，N=maxN1,N2。x1(n)和和x2(n)的的N点

18、点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或或上式所表示的运算称为上式所表示的运算称为x x1 1(n)(n)与与x x2 2(n)(n)的循环卷积。的循环卷积。26第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)循环卷积过程中，循环卷积过程中，要求对要求对x2(m)循环反循环反转，转，循环移位，循环移位，特别是两个特别是两个N长的序列的

19、长的序列的循环卷积长度仍为循环卷积长度仍为N。显然与一般的线性显然与一般的线性卷积不同，卷积不同，故称之为循环卷积，故称之为循环卷积，记为记为 121120()()()()()()NNNmx nx nx nx m xnmRn27第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)1221()()()()()()X kDFT x nX kXkXkX k由于由于 所以所以 1221()()()()()()x nIDFT X kx nx nx nx n即循环卷积亦满足交换律。即循环卷积亦满足交换律。28第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)频域循环卷积定理：频域

20、循环卷积定理：如果如果 x(n)=x1(n)x2(n)则则1211202112101()()()()1()()()1()()()1()()()NNNlNNNlX kDFT x nX kXkNX l XklRkNX kXkX kNXl XklRkN或29第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)直接计算循环卷积较麻烦。计算机中直接计算循环卷积较麻烦。计算机中采用矩阵相乘或快速傅里叶变换（采用矩阵相乘或快速傅里叶变换（FFT）的方法计算循环卷积。下面介绍用矩阵的方法计算循环卷积。下面介绍用矩阵计算循环卷积的公式。计算循环卷积的公式。30第第7 7讲讲 离散傅里叶变换离散傅里叶

21、变换(DFT)(DFT)(0)(1)(2)(1)(1)(0)(1)(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)。循环移位后可得下面的矩阵：31第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)上面矩阵称为上面矩阵称为x(n)的的L点点“循环卷积矩阵循环卷积矩阵”，其特点，其特点是是:（1）第第1行是序列行是序列x(0),x(1),x(L1)的循的循环倒相序列。注意，如果环倒相序列。注意，如果x(n)的长度的长度ML，则需要在，则需要在

22、x(n)末尾补末尾补LM个零后，再形成第一行的循环倒相个零后，再形成第一行的循环倒相序列。序列。（2）第第1行以后的各行均是前一行向右循环移行以后的各行均是前一行向右循环移1位形成的。位形成的。（3）矩阵的各主对角线上的序列值均相等。矩阵的各主对角线上的序列值均相等。有了上面介绍的循环卷积矩阵，就可以写出有了上面介绍的循环卷积矩阵，就可以写出y(n)c的矩阵形式如下的矩阵形式如下:32第第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)(

23、1)yxx Lx Lxhyxxx Lxhyxxxxhy Lx Lx Lx LxhL 33第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)按照上式，可以在计算机上用矩阵相乘的方法按照上式，可以在计算机上用矩阵相乘的方法计算两个序列的循环卷积，这里关键是先形成计算两个序列的循环卷积，这里关键是先形成循环卷积矩阵。上式中如果循环卷积矩阵。上式中如果h(n)的长度的长度NL，则需要在则需要在h(n)末尾补末尾补LN个零。个零。【例例】计算下面给出的两个长度为计算下面给出的两个长度为4的序列的序列h(n)与与x(n)的的4点和点和8点循环卷积。点循环卷积。()(0),(1),(2),(3

24、)1,2,3,4()(0),(1),(2),(3)1,1,1,1h nhhhhx nxxxx34第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)【解解】按照上式写出按照上式写出h(n)与与x(n)的的4点循环点循环卷积矩阵形式为卷积矩阵形式为h(n)与与x(n)的的8点循环卷积矩阵形式为点循环卷积矩阵形式为cccc(0)1432110(1)2143110(2)3214110(3)4321110yyyy 35第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)cccccccc(0)1110000432(1)1321000043(2)1632100004(3)110432100000904321000(4)0043210007(5)00043210(6)0400004321(7)0yyyyyyyy 036第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)作业作业第第3章习题章习题1、2、337第第7 7讲讲 离散傅里叶变换离散傅里叶变换(DFT)(DFT)38