第3章离散傅里叶变换(DFT)

1、第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.1 离散傅里叶变换的定义及物理意义离散傅里叶变换的定义及物理意义3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质3.3 频率域采样频率域采样3.4 DFT的应用举例的应用举例第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.1 离散傅里叶变换的定义离散傅里叶变换的定义及物理意义及物理意义 3.1.1 DFT （Discrete Fourier Transform）的定义）的定义 设设x(n)是一个长度为是一个长度为M的的有限长序列有限长序列，定义，定义x(n)的的N点点 离

2、散傅里叶变换离散傅里叶变换为：为： =0, 1, , N-1 10( )( ) ( ),NknNnxX kDFT x nkn W 离散傅里叶逆变换离散傅里叶逆变换为：为： =0, 1, , N-1 10( )( )( )1,NknNkWNx nIDFT X kXnk (3.1.1)(3.1.2)式中，式中， ，N称为称为DFT变换区间长度变换区间长度, NM2NjNeW 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）证明证明IDFTX(k)的唯一性的唯一性: 把把(3.1.1)式代入式代入(3.1.2)式有式有()( )()()1100110011NNmkknNNkmNNk m nNmk

3、IDFT X kx m WWNx mWN 11,()0,01Nm n MNMk m nNm n MNMkWN 所以，在变换区间上满足下式：所以，在变换区间上满足下式： IDFTX(k)=x(n) 0nN-1 由此可见，由此可见， (3.1.2)式定义的离散傅里叶逆变换是唯一的式定义的离散傅里叶逆变换是唯一的为整数为整数为整数为整数第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 例例 3.1.1 x(n)=R4(n) ，求，求x(n)的的4点、点、8点、点、16点点DFT 解：设变换区间解：设变换区间N=4，则，则( )( )sin(), ,sin()27388003820 178jknk

4、nnnj kX kx n Wekekk jj2j( )( )ee, ,eknknnnkkX kx n Wkk 23344002440101 2 31设变换区间设变换区间N=8，则，则第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）设变换区间设变换区间N=16， 则则( )( )sin(), ,sin()215316160031640 11516jknknnnjkX kx n Wekekk 由此可见，由此可见，x(n)的离散傅里叶变换结果与变换区间的离散傅里叶变换结果与变换区间长度长度N的取值有关。的取值有关。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 3.1.2 DFT与傅里叶变

5、换（与傅里叶变换（DTFT）和）和Z变换的关系变换的关系 设序列设序列x(n)长度为长度为M，其，其Z变换和变换和N(NM)点点DFT分别为：分别为：( ) ( )( )( ) ( )( )=0,1,N-1MnnNknNnX zZT x nx n zX kDFT x nx n Wk 1010比较上面二式可得关系式比较上面二式可得关系式( )( ),=0,1,N-1( )(),=0,1,N-1jkNz ejkNX kX zkX kX ek 22 (3.1.3)(3.1.4)第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）序列序列 x(n) 的的 N 点点 DFT（X(k)）是：是：u x(n

6、)的的Z变换变换在在单位圆单位圆上的上的N点点等间隔采样等间隔采样u x(n)的的傅里叶变换傅里叶变换在在区间区间0,20,2上的上的N点点等间隔采样等间隔采样=0,1,N-122( )( ),( )(),jkNjkz eNX kX zX kX ek ooooooooooo2X(ej)X(k)oRezjImzk1N00o第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 由此可见，由此可见，DFT的的变换区间长度变换区间长度N不同，表示对不同，表示对X(ej)在区间在区间0, 2上的上的采样间隔采样间隔和和采样点数采样点数不同，所以不同，所以DFT的变换结果不同。的变换结果不同。 上例中，上

7、例中，x(n)=R4(n)，DFT变换区间长度变换区间长度N分别取分别取4、8、16时，时，X(ej)和和X(k)的幅频特性曲线图如图的幅频特性曲线图如图3.1.1所示。所示。 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）图图 3.1.1 X(k)与与X(e j)的关系的关系 00.81.8201234(a)R4(n)的幅频特性图|X(ej)|00.511.522.533.54012345(b)4点DFT的幅频特性图|X(k)|012345678012345(c)8点DFT的幅频特性图|X(k)|0246810121416012345(d)16点D

8、FT的幅频特性图|X(k)|第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 3.1.3 DFT的隐含周期性的隐含周期性 前面定义的前面定义的DFT变换对中，变换对中，x(n)与与X(k)均为有限长均为有限长序列，但由于序列，但由于 的周期性，使离散傅里叶变换式中的的周期性，使离散傅里叶变换式中的x(n)与与X(k)隐含周期性，且周期均为隐含周期性，且周期均为N。对任意整数。对任意整数m， 总有总有()kk mNNNWW 所以所以 式中，式中， X(k)满足满足()()( )( )( )1010Nk mN nNnNknNnX kmNx n Wx n WX k knNWk，m为整数，为整数，

9、N为自然数为自然数10( )( )NknNnX kx n W 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 任何周期为任何周期为N的周期序列的周期序列 都可以看作长度为都可以看作长度为N的有限长序列的有限长序列x(n)的周期延拓序列，而的周期延拓序列，而x(n)则是则是 的的一个周期，即一个周期，即( )x n( )()( )( )( )mNx nx nmNx nx nRn ( )x n上述关系如图上述关系如图3.1.2(a)和和(b)所示。所示。 周期序列中从周期序列中从n=0到到N1的第一个周期为的第一个周期为的的主值区间主值区间，而主值区间上的序列称为，而主值区间上的序列称为 的

10、的主值序列主值序列。因此。因此 x(n) 与的关系可叙述为与的关系可叙述为： 是是 x(n) 的周期延拓序列的周期延拓序列 x(n)是是 的主值序列的主值序列)(nx)(nx)(nx( )x n( )x n)(nx第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 图图3.1.2 x(n)及其周期延拓序列及其周期延拓序列第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）设序列设序列 x(n) 长度为长度为M，当当NM时，时， 式可用如下形式表示：式可用如下形式表示： 式中式中 x(n)N ： x(n) 以以N为周期的周期延拓序列为周期的周期延拓序列 (n)N ：模模 N 对对 n 求余求余

11、即如果即如果 n=MN+n1 0n1N1, M为整数为整数则则(n)N = (n1) 例如，例如，, 则有则有( )( )Nx nx n 88, ( )( )Nx nx n88(8)(8)(0)(9)(9)(1)xxxxxx( )()mx nx nmN 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）？() 2186()()xx822()()( )xxx8226第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）)(nx 两式仅对两式仅对NM时成立。时成立。 图图3.1.2（a）中）中x(n)实际长度实际长度M=6，当延拓周期，当延拓周期N=4时，时， 如图如图3.1.2（c）所示。）所示

12、。 ( )()mx nx nmN 若若 x(n) 实际长度为实际长度为M，延拓周期为，延拓周期为N，则当，则当NM时，时，仍表示以仍表示以N为周期的周期序列，但为周期的周期序列，但( )( )( )Nx nx nRn( )( )Nx nx n 说明：说明：第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 图图3.1.2 x(n)及其周期延拓序列及其周期延拓序列第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 如果如果x(n)的长度为的长度为M，且，且，NM，则，则 的离散傅里叶级数：的离散傅里叶级数：( )( )( )NNknknNNkkx nX k WX k WNN 110011Nn

13、xnx)()()(nx( )( )( )( )NNNknknknNNNNnnnX kx n Wx nWx n W 111000 有限长序列有限长序列 x(n) 的的 N 点离散傅里叶变换点离散傅里叶变换 X(k) 正好是正好是x(n)的周期延拓序列的周期延拓序列 x(n)N 的离散傅里叶级数系数的离散傅里叶级数系数的主值序列。的主值序列。( )( )( )NX kX k Rk ( )X k( )X k式中式中即即 X(k) 为的为的主值序列主值序列第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 周期延拓序列频谱完全由其离散傅里叶级数系数周期延拓序列频谱完全由其离散傅里叶级数系数确定，因此

14、：确定，因此：( )X k观察观察 DFT R4(n) 4= 4(k)。 根据根据DFT第二种物理解释可知，第二种物理解释可知，DFT R4(n) 4 表示表示R4(n)以以4为周期的周期延拓序列为周期的周期延拓序列R4(n)4的频谱特性，因的频谱特性，因为为R4 (n)4是一个直流序列，只有直流成分（即零频率是一个直流序列，只有直流成分（即零频率成分），所以，成分），所以， DFT R4(n) 4 = 4(k) 。 X(k) 实质上实质上是是 x(n) 的周期延拓序列的周期延拓序列 x(n) N 的频谱特性的频谱特性第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.1.4 用用MATL

15、AB计算序列的计算序列的DFTMATLAB提供用快速傅里叶变换算法提供用快速傅里叶变换算法FFT计算计算DFT的函数的函数 fft，调用格式如下，调用格式如下: Xk = fft (xn, N) xn：被变换的时域序列向量：被变换的时域序列向量 N：DFT变换区间长度变换区间长度 当当N大于大于 xn 的长度时，的长度时，fft自动在自动在xn后面补零后面补零 Xk：返回的：返回的 xn 的的N点点DFT变换结果向量变换结果向量 当当N小于小于xn的长度时，的长度时，fft 函数计算函数计算xn的前面的前面N个元个元素构成的素构成的N长序列的长序列的N点点DFT，忽略，忽略xn后面的元素。后面

16、的元素。 ifft函数计算函数计算IDFT，其调用格式与，其调用格式与fft函数相同。函数相同。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）【例【例3.1.2】 设设x(n)=R4(n)，X(ej)=FTx(n)。分别计算。分别计算X(ej)在频率区间在频率区间0，2上的上的16点和点和32点等间隔采样，点等间隔采样，并绘制并绘制X(ej)采样的幅频特性图和相频特性图。采样的幅频特性图和相频特性图。解：解： 由由DFT与傅里叶变换的关系知道，与傅里叶变换的关系知道，X(ej)在频率区间在频率区间0，2上的上的16点和点和32点等间隔采样，分别是点等间隔采样，分别是x(n)的的16点点和

17、和32点点DFT。调用。调用 fft 函数的求解程序如下函数的求解程序如下:xn=1 1 1 1; %输入时域序列向量输入时域序列向量xn=R4(n)Xk16=fft(xn, 16); %计算计算xn的的16点点DFTXk32=fft(xn, 32); %计算计算xn的的32点点DFT %以下为绘图部分以下为绘图部分第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）k=0:15;wk=2*k/16; %产生产生16点点DFT对应的采样点频率对应的采样点频率(关于关于归一化值归一化值)subplot(2,2,1);h=stem(wk,abs(Xk16),o,fill); %绘制绘制16点点DF

18、T的幅频特性图的幅频特性图set(h,LineWidth,3)title(a)16点点DFT的幅频特性图的幅频特性图,fontsize,25);xlabel(/,fontsize,25);ylabel(幅度幅度,fontsize,25)subplot(2,2,3);h=stem(wk,angle(Xk16),o,fill); %绘制绘制16点点DFT的相频特性图的相频特性图set(h,LineWidth,3)line(0,2,0,0);title(b)16点点DFT的相频特性图的相频特性图,fontsize,25)xlabel(/,fontsize,25);ylabel(相位相位,fontsi

19、ze,25);axis(0,2,-3.5,3.5)第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）k=0:31;wk=2*k/32; %产生产生32点点DFT对应的采样点频率对应的采样点频率(关于关于归一化值归一化值)subplot(2,2,2);h=stem(wk,abs(Xk32),o,fill); %绘制绘制32点点DFT的幅频特性图的幅频特性图set(h,LineWidth,3)title(c)32点点DFT的幅频特性图的幅频特性图,fontsize,25);xlabel(/,fontsize,25);ylabel(幅度幅度,fontsize,25)subplot(2,2,4);h

20、=stem(wk,angle(Xk32),o,fill); %绘制绘制32点点DFT的相频特性图的相频特性图set(h,LineWidth,3)line(0,2,0,0);title(d)32点点DFT的相频特性图的相频特性图,fontsize,25);xlabel(/,fontsize,25);ylabel(相位相位,fontsize,25);axis(0,2,-3.5,3.5)第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）图图3.1.3 例例3.1.2程序运行结果程序运行结果 00.81.8200.511.522.533.54(a)16点DFT的

21、幅频特性图/幅度00.81.82-3-2-10123(b)16点DFT的相频特性图/相位00.81.8200.511.522.533.54(c)32点DFT的幅频特性图/幅度00.81.82-3-2-10123(d)32点DFT的相频特性图/相位第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）DFT的矩阵方程表示的矩阵方程表示(0)(0)(1)(1),(1)(1)XxXxX Nx NXxxWXN)1()1()1(2)1()1(2421111111111NNNNNNNNNNNNN

22、NNWWWWWWWWWNW =0, 1, , N-1 10( )( ) ( ),NknNnxX kDFT x nkn W 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）IDFT的矩阵方程表示的矩阵方程表示1001NmknkkNmnWWmnNNNNNW WIxW X第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质3.2.1 3.2.1 线性性质线性性质若若x1(n)、x2(n)是两个有限长序列，长度为是两个有限长序列，长度为N1、N2，且，且y(n)=ax1(n)+bx2(n) a、b为常数，取为常数，取N=max N1, N2

23、，则，则 y(n) 的的 N 点点DFT为为Y(k) = DFT y(n) N = aX1(k)+bX2(k) 0kN1 其中其中 X1(k) 和和 X2(k) 分别为分别为 x1(n) 和和 x2(n) 的的N点点DFT 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.2.2 3.2.2 循环移位性质循环移位性质1序列的循环移位序列的循环移位 设设x(n)为有限长序列，长度为为有限长序列，长度为M，MN，则，则x(n)的循环的循环移位定义为移位定义为: y(n)=x(n+m) NRN(n) x(n) 的循环移位过程：的循环移位过程：（1）将）将 x(n) 以以N为周期进行周期延拓得到

24、为周期进行周期延拓得到（2）再将左移）再将左移 m 得到得到 ，（3）最后取）最后取 的主值序列的主值序列 x(n+m) NRN(n) 得到有限长序列得到有限长序列 x(n) 的循环移位序列的循环移位序列 y(n)。( )( )Nx nx n ( )x n()x nm ()x nm 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）M=6, N=8, m=2时，时，x(n)及其循环移位过程如下图。及其循环移位过程如下图。 循环移位的实质是将循环移位的实质是将 x(n) 左移左移m位，而移出主值区位，而移出主值区(0nN1)的序列值又依次从右侧进入主值区。的序列值又依次从右侧进入主值区。“循环

25、移位循环移位”由此得名。由此得名。由循环移位的定义可知，对同一序列由循环移位的定义可知，对同一序列 x(n) 和相同的位移和相同的位移m，当延拓周期，当延拓周期N不同时，不同时，y(n)=x(n+m)NRn(n)不同。不同。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）2时域循环移位定理时域循环移位定理 设设 x(n) 是长度为是长度为M（MN）的有限长序列，）的有限长序列，y(n)为为 x(n) 的循环移位，即的循环移位，即y(n)=x(n+m)NRN(n) 则则 其中其中X(k)= DFT x(n) N 0kN1 即：即：时域位移，频域相移时域位移，频域相移( )DFT ( )( )

26、kmNNY ky nWX k 00 ()()j njFT x nneX e ZT00 ()( ),|nxxx nnzX zRz R 对照：对照：第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）nkNNWnx)(令令n+m=n，则有，则有由于上式中求和项由于上式中求和项以以N为周期，因此对其在为周期，因此对其在任一周期上的求和结果相同。将上式的求和区间改在主任一周期上的求和结果相同。将上式的求和区间改在主值区，则得值区，则得1100( )DFT ( )()( )()NNknknNNNNNNnnY ky nx nmRn Wx nmW11()( )( )( )NmNmk nmkmknNNNNNn

27、mnmY kx nWWx nW 1100( )( )( )( )NNkmknkmknkmNNNNNNnnY kWx nWWx n WWX k证明：证明：第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3 频域循环移位定理频域循环移位定理如果如果 X(k) = DFT x(n) N 0kN1 Y(k) = X(k+l)NRN(k)则则即：即：频域位移（频谱搬移），时域调制。频域位移（频谱搬移），时域调制。IDFT( ) ( )( )nlNNy nY kWx n 对照：对照： 设设 X(ej)=FTx(n)，那么那么00()()( )jjnIFT X eex n 第第3章章 离散傅里叶变换（离

28、散傅里叶变换（DFT）作作 业业第三章第三章习题与上机题习题与上机题课本第课本第105、106页页1、2、（题目有误）、（题目有误）第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.2.3 3.2.3 循环卷积定理循环卷积定理1 两个有限长序列的两个有限长序列的循环卷积循环卷积 设序列设序列 h(n) 和和 x(n) 的长度分别为的长度分别为 N 和和 M。h(n)与与x(n)的的L点循环卷积点循环卷积定义为：定义为：c( )() ()( )LLLmy nh m x nmRn 10 L称为循环卷积区间长度，称为循环卷积区间长度，LmaxN，M。用用 * * 表线性卷积：表线性卷积：用用

29、表循环卷积，用表表循环卷积，用表L点循环卷积：点循环卷积：计算机中采用矩阵相乘或计算机中采用矩阵相乘或FFT的方法计算循环卷积。的方法计算循环卷积。 对比对比 h(n) 与与 x(n) 的的线性卷积：线性卷积：( )() ()my nh m x nm ( )( )( )y nh nx n( )( )( )y nh nx n 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）当当n = 0, 1, 2, , L1时，由时，由x(n)形成的序列为形成的序列为:令令n=0, m=0, 1, , L1，由由x(n-m)L形成形成x(n)的循环倒相序列为：的循环倒相序列为：x(n)的循环倒相序列形成过

30、程：的循环倒相序列形成过程： 将第一个序列值将第一个序列值x(0)不动，将后面的序列反转不动，将后面的序列反转180再放在再放在 x(0) 的后面。的后面。 ( ) , () , () , , () ( ), (), (), , ( )LLLLxxxxLxx Lx Lx 01210121用矩阵计算循环卷积：用矩阵计算循环卷积：c( )() ()( )LLLmy nh m x nmRn 10 ( ), ( ), ( ), , ()xxxx L 0121第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）令令n = 1, m = 0, 1, , L-1，由由x(n-m)L形成的序列为形成的序列为上

31、式等号右端序列相当于上式等号右端序列相当于x(n)的循环倒相序列向右循环的循环倒相序列向右循环移一位，即向右移移一位，即向右移1位，移出区间位，移出区间0, L1的序列值的序列值再从左边移进。再从左边移进。再令再令n = 2, m = 0, 1, , L1，此时得到的序列又，此时得到的序列又是上面的序列向右循环移是上面的序列向右循环移1位。依次类推，当位。依次类推，当n和和m均从均从0变化到变化到L-1时，得到一个关于时，得到一个关于x(nm)L的矩阵如下：的矩阵如下： ( ) , ( ) , () , , () ( ), ( ), (), , ( )LLLLxxxxLxxx Lx 10121

32、012c( )() ()( )LLLmy nh m x nmRn 10第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）(0)(1)(2)(1)(1)(0)(1)(2)(2)(1)(0)(3)(1)(2)(3)(0)xx Lx Lxxxx Lxxxxxx Lx Lx Lx上面矩阵称为上面矩阵称为x(n)的的L点点“循环卷积矩阵循环卷积矩阵”，特点，特点:（1） 第第1行是序列行是序列x(0), x(1), , x(L1)的循环倒相序列。的循环倒相序列。如果如果x(n)的长度的长度ML，则需要在，则需要在x(n)末尾补末尾补LM个零后，个零后，再形成第一行的循环倒相序列。再形成第一行的循环倒相

33、序列。（2） 第第1行以后的各行均是前一行向右循环移行以后的各行均是前一行向右循环移1位形成的。位形成的。（3） 矩阵的各主对角线上的序列值均相等。矩阵的各主对角线上的序列值均相等。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）cccc( )( )()()( )( )( )( )( )()( )( )( )( )( )( )( )( )()()()()( )()yxx Lx Lxhyxxx Lxhyxxxxhy Lx Lx Lx Lxh L 001210110121221032112301 有了循环卷积矩阵，就可以写出上式的矩阵形式有了循环卷积矩阵，就可以写出上式的矩阵形式:c( )()

34、 ()( )LLLmy nh m x nmRn 10 按照上式可在计算机上用矩阵相乘的方法计算两个序按照上式可在计算机上用矩阵相乘的方法计算两个序列的循环卷积，关键是先形成循环卷积矩阵。列的循环卷积，关键是先形成循环卷积矩阵。 如果如果h(n)的长度的长度NL，则需要在，则需要在h(n)末尾补末尾补LN个零。个零。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）【例【例3.2.1】 计算下面给出的两个长度为计算下面给出的两个长度为4的序列的序列h(n)与与x(n)的的4点和点和8点循环卷积。点循环卷积。 ( )(0), (1), (2), (3)1,2,3,4( )(0), (1), (2

35、), (3)1,1,1,1h nhhhhx nxxxx解：解： h(n)与与x(n)的的4点循环卷积矩阵为：点循环卷积矩阵为：cccc(0)1432110(1)2143110(2)3214110(3)4321110yyyy 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）cccccccc(0)1110000432(1)1321000043(2)1632100004(3)110432100000904321000(4)0043210007(5)00043210(6)0400004321(7)0yyyyyyyy 0h(n)与与x(n)的的8点循环卷积矩阵形式为：点循环卷积矩阵形式为：h(n)和

36、和x(n)及其及其4点和点和8点循环卷积结果分别如图点循环卷积结果分别如图3.2.2所示所示可以证明：可以证明： 当循环卷积区间长度当循环卷积区间长度L大于等于大于等于y(n) = h(n)*x(n)的长的长度时，循环卷积结果就等于线性卷积。度时，循环卷积结果就等于线性卷积。 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 图图3.2.2 序列及其循环卷积波形序列及其循环卷积波形01234567800.511.522.533.544.55nx(n)(a) x(n)01234567800.511.5nh(n)(b) h(n)01234567801234567891011nyc(n)(c)

37、4点循环卷积01234567801234567891011nyc(n)(d) 8点循环卷积第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）2. 循环卷积定理循环卷积定理 有限长序列有限长序列x1(n)和和x2(n)的长度分别为的长度分别为N1和和N2，N=maxN1, N2，x1(n)和和x2(n)的的N点循环卷积为点循环卷积为（3.2.8）则则x(n)的的N点点DFT为为其中其中2( )( )x nx nN 11210( )( )()( )NNNmx nx m xnmRn12( )DFT ( )( )( )NX kx nX kXk1122( )DFT( ) ,( )DFT( )NNX k

38、x nXkx n第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）证明证明 直接对直接对(3.2.8)式两边进行式两边进行DFT，则有，则有111200111200( )DFT ( )( )()( )( )()NNNknNNNnmNNknNNmnX kx nx m xnmRn Wx mxnmW 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）令令nm=n，则有，则有因为上式中因为上式中是以是以N为周期的，所以对其为周期的，所以对其在任一个周期上求和的结果不变。因此在任一个周期上求和的结果不变。因此10121101)(21)()()()()(NmmNmnknNNkmNNmmNmnmnkNN

39、WnxWmxWnxmxkX2)(knNNWnx第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）由于，由于，因此因此即循环卷积亦满足交换律。即循环卷积亦满足交换律。 10)()() ()()(21101021NkkXkXWnxWmxkXNmNnknNkmN，1221( )DFT ( )( )( )( )( )X kx nX k XkXk X k1( )IDFT( )( )x nX kx n22( )( )x nx n1( )x n第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）频域循环卷积定理频域循环卷积定理:如果如果x(n)=x1(n)x2(n)，则，则11( )DFT ( )( )N

40、X kx nX kN2( )XkN 11201( )()( )NNNlX l XklRkN112101( )( )()( )NNNlX kXl XklRkN或或式中式中21( )( )X kXkNN 1122( )DFT( )01( )DFT( )NNX kx nkNXkx n第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.2.4 复共轭序列的复共轭序列的DFT 设设x*(n)是是x(n)的复共轭序列，长度为的复共轭序列，长度为N， X(k)=DFTx(n)N，则，则且且X(N)=X(0)。*DFT( )()01Nx nXNkkN(3.2.11)第第3章章 离散傅里叶变换（离散傅里叶变

41、换（DFT）又由又由X(k)的隐含周期性，有的隐含周期性，有X(N)=X(0)用同样的方法可以证明用同样的方法可以证明 11*()*()001*0()( )( )( )DFT( )NNN k nN k nNNnnNknNNnXNkx n Wx n Wx n Wx n*DFT()( )NxNnXk证明证明 根据根据DFT的唯一性，只要证明的唯一性，只要证明(3.2.11)式右边等于式右边等于左边即可。左边即可。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.2.5 DFTDFT的共轭对称性的共轭对称性 序列傅里叶变换（序列傅里叶变换（DTFT）满足共轭对称性，）满足共轭对称性，其对称是关

42、于坐标原点的纵坐标对称，其对称是关于坐标原点的纵坐标对称，DFT也有类也有类似的对称性，是关于似的对称性，是关于N/2点对称。点对称。1有限长共轭对称序列和共轭反对称序列有限长共轭对称序列和共轭反对称序列为了区别于傅里叶变换中所定义的共轭对称为了区别于傅里叶变换中所定义的共轭对称（或共轭反对称）序列，用（或共轭反对称）序列，用xep(n)和和xop(n)分别表示分别表示有限长共轭对称序列和共轭反对称序列，二者满足有限长共轭对称序列和共轭反对称序列，二者满足如下关系式：如下关系式：*epep( )() 01xnxNnnN*opop( )() 01xnxNnnN (3.2.13a)(3.2.13b

43、)第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）当当N为偶数时，将上式中的为偶数时，将上式中的n换成换成N/2n，可得到：，可得到：可以清楚地看出有限长共轭对称序列是关于可以清楚地看出有限长共轭对称序列是关于n=N/2点对称。点对称。容易证明：容易证明： 任何有限长序列任何有限长序列x(n)都可以表示成其共轭对称分量和都可以表示成其共轭对称分量和共轭反对称分量之和共轭反对称分量之和，即，即 *epep()()01222NNNxnxnn*opop()()01222NNNxnxnn 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）(3.2.14) 将上式中的将上式中的n换成换成Nn，并取

44、复共轭，再将，并取复共轭，再将(3.2.13a)式和式和(3.2.13b)式代入，得到：式代入，得到：(3.2.15)(3.2.14)式分别加减式分别加减(3.2.15)式，可得式，可得epop( )( )( )01x nxnxnnN*epopepop()()()( )( )xNnxNnxNmxnxn*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn(3.2.16a)(3.2.16b)第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）2 DFT的共轭对称性的共轭对称性(1) 如果将如果将x(n)表示为表示为x(n)=xr(n)+jxi(n) 其中其中由由

45、(3.2.11)式和式和(3.2.16a)式可得式可得*r*i1( )Re ( ) ( )( )21j ( )jIm ( ) ( )( )2x nx nx nx nx nx nx nx n由由(3.2.11)式和式和(3.2.16b)式可得式可得*rep11DFT( )DFT ( )( )( )()( )22x nx nx nX kXNkXk*iop11DFTj ( )DFT ( )( )( )()( )22x nx nx nX kXNkXk第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）由由DFT的线性性质即可得的线性性质即可得其中：其中： Xep(k)=DFTxr(n)是是X(k)的共

46、轭对称分量，的共轭对称分量， Xop(k)=DFTjxi(n)是是X(k)的共轭反对称分量。的共轭反对称分量。epop( )DFT ( )( )( )X kx nXkXk第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）其中，其中，是是x(n)的共轭对称分量，的共轭对称分量， 是是x(n)的共轭反对称分量的共轭反对称分量, 那么，由式那么，由式 可得可得*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn*ep11DFT( )DFT ( )()( )( )Re( )22xnx nxNnX kXkX k*op11DFT( )DFT ( )()( )( )Im

47、( )22xnx nxNnX kXkjX k(2) 如果将如果将x(n)表示为表示为epop( )( )( )01x nxnxnnN*DFT()( )NxNnXk第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）因此因此其中其中RI( )DFT ( )( )j( )X kx nXkX kRep( )Re( )DFT( )XkX kxnIopj( )jIm( )DFT( )X kX kxn 综上所述，综上所述，DFT的共轭对称性质：的共轭对称性质：（1）如果序列）如果序列x(n)的的DFT为为X(k)，则，则x(n)的实部和虚部的实部和虚部 （包括（包括j）的）的DFT分别为分别为X(k)的共

48、轭对称分量和共轭的共轭对称分量和共轭 反对称分量；反对称分量；（2）x(n)的共轭对称分量和共轭反对称分量的的共轭对称分量和共轭反对称分量的DFT分别分别 为为X(k)的实部和虚部乘以的实部和虚部乘以j。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）(1) X(k)共轭对称共轭对称: X(k)=X*(N-k) k=0, 1, , N-1(2) 若若x(n)是偶对称，即是偶对称，即 x(n) = x(Nn)，则，则 X(k)实偶对称，即实偶对称，即 X(k) = X(Nk)(3) 若若x(n)是奇对称，即是奇对称，即 x(n) = x(Nn)，则，则 X(k)纯虚奇对称，即纯虚奇对称，即

49、X(k) = X(Nk) 有限长实序列有限长实序列DFT的共轭对称性：的共轭对称性： 设设x(n)是长度为是长度为N的实序列，则的实序列，则:利用对称性质，可减少利用对称性质，可减少DFT的运算量，提高运算效率。的运算量，提高运算效率。 当当N = 偶数时，只需计算偶数时，只需计算 X(k) 的前面的前面 N/2+1 点；点； 当当N = 奇数时，只需计算奇数时，只需计算 X(k) 的前面的前面 (N+1)/2 点，点， 其他点按照其他点按照 X(k) = X*(N-k) 式即可求得。式即可求得。 例如，例如，X(N1)=X*(1), X(N2)=X*(2), 第第3章章 离散傅里叶变换（离散

50、傅里叶变换（DFT）所以，由所以，由X(k)可以求得两个实序列可以求得两个实序列x1(n)和和x2(n)的的N点点DFT：epop( )DFT ( )( )( )X kx nXkXk*ep11( )DFT( )( )()2Xkx nX kXNk*op21( )DFTj( )( )()2Xkx nX kXNk)()(21)()(*11kNXkXnxDFTkX*221( )DFT( )j ( )()2Xkx nX kXNk 【例【例3.2.2】 利用利用DFT的共轭对称性设计一种算法，通过计算的共轭对称性设计一种算法，通过计算一个一个N点点DFT，就可计算出两个实序列，就可计算出两个实序列x1(n

51、)和和x2(n)的的N点点DFT解解:构造新序列构造新序列x(n)=x1(n)+jx2(n)，对，对x(n)进行进行DFT，得到：，得到：由由DFT的共轭对称性可得：的共轭对称性可得：第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）3.3 频频 率率 域域 采采 样样 时域采样定理：时域采样定理： 设连续信号设连续信号xa(t)属带限信号，最高截止频率为属带限信号，最高截止频率为c，如果采样角频率如果采样角频率s2c，那么让采样信号通过一个增，那么让采样信号通过一个增益为益为T，截止频率为，截止频率为s/2的理想低通滤波器，可以唯一的理想低通滤波器，可以唯一地恢复出原连续信号地恢复出原连续

52、信号xa(t)。 问题问题： 能否由频域离散采样恢复原来的信号（或原连续频能否由频域离散采样恢复原来的信号（或原连续频率函数）？其条件是什么？内插公式是什么？率函数）？其条件是什么？内插公式是什么？ 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）上式表示在区间上式表示在区间0, 2上对上对x(n)的傅里叶变换的傅里叶变换X(ej)的的N点等间隔采样。将点等间隔采样。将X(k)看做长度为看做长度为N的有限长序列的有限长序列xN(n)的的DFT，即，即目的：推导序列目的：推导序列 xN(n) 与原序列与原序列 x(n) 之间的关系之间的关系2jje( )( )|( )e( ) kNknknN

53、NznnX kX zx nx n WkN 201=( )IDFT( )01NxnX knN，设任意序列设任意序列x(n)的的Z变换为变换为且且X(z)的收敛域包含单位圆（即的收敛域包含单位圆（即x(n)存在傅里叶变换）。存在傅里叶变换）。在单位圆上对在单位圆上对X(z)等间隔采样等间隔采样N点点, 得到：得到：nnznxzX)()(第第3章章 离散傅里叶变换（离散傅里叶变换（DFT） 由由DFT与与DFS的关系可知，的关系可知，X(k)是是xN(n)以以N为周期的周为周期的周期延拓序列的离散傅里叶级数系数的主值序期延拓序列的离散傅里叶级数系数的主值序列，即列，即( )x n)(kX1010(

54、)( )DFS ( )( )( )( )( )( )IDFS( )1( )1( )NNNNNknNkNknNkX kXkx nX kX k Rkx nxnX kX k WNX k WN第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）将式将式 代入上式得代入上式得式中式中()Nk m nNkmniNiWmN 10110， 为整数，其他 mNknmkNNkmknNkmNWNmxWWmxNnx10)(101)()(1)( )( ) knNnX kx n W 第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）因此因此所以所以( )()ix nx niN( )( )( )()( )NNNixnx

55、n Rnx niNRn上式说明：上式说明： X(z)在单位圆上的在单位圆上的N点等间隔采样点等间隔采样X(k)的的N点点IDFT是原序列是原序列x(n)以以N为周期的周期延拓序列的主值序列。为周期的周期延拓序列的主值序列。 频域采样定理频域采样定理： 如果序列如果序列x(n)的长度为的长度为M，则只有当频域采样点数，则只有当频域采样点数NM 时，才有时，才有xN(n)=IDFTX(k)= x(n)，即可由频，即可由频域采样域采样 X(k) 恢复原序列恢复原序列 x(n)，否则产生，否则产生时域混叠时域混叠现象。现象。第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）满足频域采样定理时，频域采

56、样序列满足频域采样定理时，频域采样序列X(k)的的N点点IDFT是原序列是原序列x(n)，所以必然可以由，所以必然可以由X(k)恢复恢复X(z)和和X(ej)。 用频域采样用频域采样X(k)表示表示X(z)和和X(ej)的的内插公式内插公式和和内插函数内插函数： 设序列设序列x(n)长度为长度为M，在频域，在频域0, 2上等间隔采样上等间隔采样N点，点，NM，则有，则有1, 2, 1, 0| )()()()(2je10NkzXkXznxzXkNzNnn第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）因为满足频域采样定理，所以式中因为满足频域采样定理，所以式中将上式代入将上式代入X(z)的表

57、示式中，得到的表示式中，得到:(3.3.4a) 101( )IDFT( )( )NknNkx nX kX k WN1111000011011( )( )( )11 ( )1NNNNknnknnNNnkknkNNNNknnX zX k WzX kWzNNWzX kNWz第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）式中，因此式中，因此 (3.3.4b)令令 则则10111)(1)(NkkNNzWzkXNzX1111)(zWzNzkNNk10)()()(NkkzkXzX1kNNW上式上式 即为用即为用 X(k) 表示表示 X(z) 的的内插公式内插公式k(z)称为称为内插函数内插函数第第3章

58、章 离散傅里叶变换（离散傅里叶变换（DFT） 将将z=ej代入代入(3.3.4a)式，并进行化简，可得式，并进行化简，可得 (3.3.7) 在数字滤波器的结构与设计中，我们将会看到，频在数字滤波器的结构与设计中，我们将会看到，频域采样理论及有关公式可提供一种有用的滤波器结构和域采样理论及有关公式可提供一种有用的滤波器结构和滤波器设计途径，滤波器设计途径，(3.3.7)式有助于分析式有助于分析FIR滤波器频率滤波器频率采样设计法的逼近性能。采样设计法的逼近性能。10j)2()()e (NkkNkXX)21(je)2/sin()2/sin(1)(NNN(3.3.8)第第3章章 离散傅里叶变换（离散

59、傅里叶变换（DFT）【例【例3.3.1】 长度为长度为26的三角形序列的三角形序列x(n)如图如图3.3.1(b)所所示。编写示。编写MATLAB程序验证频域采样理论。程序验证频域采样理论。解：先计算解：先计算x(n)的的32点点DFT，得到其频谱函数，得到其频谱函数X(ej)在频在频率区间率区间0，2上等间隔上等间隔32点采样点采样X32(k)，再对，再对X32(k)隔点抽取，得到隔点抽取，得到X(ej)在频率区间在频率区间0，2上等间隔上等间隔16点采样点采样X16(k)。最后分别对。最后分别对X16(k)和和X32(k)求求IDFT, 得到：得到：绘制绘制x16(n)和和x32(n)波形

60、图验证频域采样理论。波形图验证频域采样理论。161616( )IDFT( )xnXk323232( )IDFT( )xnXk第第3章章 离散傅里叶变换（离散傅里叶变换（DFT）% 频域采样理论验证频域采样理论验证M=26; N=32; n=0:M; xa=0:M/2; xb= ceil(M/2)-1:-1:0; xn=xa, xb; %产生产生M长三角波序列长三角波序列x(n)Xk=fft(xn, 512); %512点点FFTx(n)X32k=fft(xn, 32); %32点点FFTx(n)x32n=ifft(X32k); %32点点IFFTX32(k)得到得到x32(n)X16k=X32