第3章离散傅里叶变换

1、第3章 离散傅里叶变换(DFT) 第第3章章 离散傅里叶变换离散傅里叶变换(DFT) 3.1 离散傅里叶变换的定义及物理意义离散傅里叶变换的定义及物理意义 3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质 3.3 频率域采样频率域采样 3.4 DFT的应用举例的应用举例 习题与上机题习题与上机题第3章 离散傅里叶变换(DFT) 傅里叶变换和Z变换是数字信号处理中常用的重要数学变换。对于有限长序列，还有一种更为重要的数学变换，即本章要讨论的离散傅里叶变换(Discrete Fourier Transform，DFT)。DFT之所以更为重要，是因为其实质是有限长序列傅里叶变换的有限点离散采

2、样，从而实现了频域离散化，使数字信号处理可以在频域采用数值运算的方法进行，这样就大大增加了数字信号处理的灵活性。更重要的是，DFT有多种快速算法，统称为快速傅里叶变换(Fast Fourier Transform，FFT)，从而使信号的实时处理和设备的简化得以实现。第3章 离散傅里叶变换(DFT) 因此，时域离散系统的研究与应用在许多方面取代了传统的连续时间系统。所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中亦起着核心作用。 本章主要讨论DFT的定义、物理意义、基本性质以及频域采样和DFT的应用举例等内容。第3章 离散傅里叶变换(DFT) 3.1 离散傅里叶变换的定义及物理意义离

3、散傅里叶变换的定义及物理意义3.1.1 DFT的定义的定义 设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里叶变换为10( )DFT ( )( )0,1,1NknNnX kx nx n WkN(3.1.1)2jeNNW第3章 离散傅里叶变换(DFT) X(k)的离散傅里叶逆变换(Inverse Discrete Fourier Transform, IDFT) 为2jeNNW式中，N称为DFT变换区间长度。通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。为了叙述简洁，常常用DFTx(n)N和IDFTX(k)N分别表示N点离散傅里叶变换和N点离散傅里叶逆变换。下面证

4、明IDFTX(k)的唯一性。101( )IDFT( )( )NknNkx nX kX k WN0,1,1nN(3.1.2)第3章 离散傅里叶变换(DFT) 把(3.1.1)式代入(3.1.2)式，有由于110011()001IDFT( )( )1( )NNmkknNNNkmNNk m nNmkX kx m WWNx mWN 为整数为整数，iiNnmiiNnmWNNknmkN01110)(所以，在变换区间上满足下式：IDFTX(k)=x(n) 0nN1由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。第3章 离散傅里叶变换(DFT) 例例3.1.1 已知序列x(n)=(n)，求它的N点D

5、FT。 解解 单位脉冲序列的DFT很容易由DFT的定义式（2-30）得到： 1001)()(NnNnkNWWnkX k=0, 1, , N-1 (n)的X(k)如图2-9。这是一个很特殊的例子，它表明对序列(n)来说，不论对它进行多少点的DFT，所得结果都是一个离散矩形序列。 第3章 离散傅里叶变换(DFT) 图2-9 序列(n)及其离散傅里叶变换 第3章 离散傅里叶变换(DFT) 例例 3.1.2 已知x(n)=cos(n/6)是一个长度N=12的有限长序列， 求它的N点DFT。 解解 由DFT的定义式（2-30） 110)1(122110)1(122110122661211021216co

6、s)(nknjnknjnnkjnjnjnkneeeeeWnkX 利用复正弦序列的正交特性（2-3）式，再考虑到k的取值区间，可得 11, 0,011, 16)(kkkkX其他第3章 离散傅里叶变换(DFT) 图 2-10 有限长序列及其DFT第3章 离散傅里叶变换(DFT) 例例 3.1.3 已知如下X(k):13)(kXk=0 1k9 求其10点IDFT。 解解 X(k)可以表示为 X(k)=1+2(k) 0k9 写成这种形式后，就可以很容易确定离散傅里叶反变换。 由于一个单位脉冲序列的DFT为常数： 111( )( )( )( )1x nnX kDFT x n第3章 离散傅里叶变换(DFT

7、) 同样，一个常数的DFT是一个单位脉冲序列： x2(n)=1 X2(k)=DFTx2(n)=N(k) 所以 )(51)(nnx第3章 离散傅里叶变换(DFT) 3.1.2 DFT与傅里叶变换和与傅里叶变换和Z变换的关系变换的关系 设序列x(n)的长度为M，其Z变换和N(NM)点DFT分别为比较上面二式可得关系式 (3.1.3)或1010( )ZT ( )( )( )DFT ( )( )0,1,1MnnMknNNnX zx nx n zX kx nx n WkN2je( )( )0,1,1kNzX kX zkNj2( )(e )|0,1,1kNX kXkN (3.1.4)第3章 离散傅里叶变换

8、(DFT) X(k)也可以看作序列也可以看作序列x(n)的傅里叶变换的傅里叶变换X(ej)在区间在区间0, 2上的上的N点等间隔采样，其采样间隔为点等间隔采样，其采样间隔为N=2/N， 这就是这就是DFT的物理意义的物理意义。显而易见，DFT的变换区间长度N不同， 表示对X(ej)在区间0, 2上的采样间隔和采样点数不同， 所以DFT的变换结果也不同。 第3章 离散傅里叶变换(DFT) X(ej)在区间0, 2上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对X(ej)在区间0, 2上的采样间隔和采样点数不同，所以DFT的变换结果不同。上例中， x(n)=

9、R4(n)，DFT变换区间长度N分别取8、16时，X(ej)和X(k)的幅频特性曲线图如图3.1.1所示。由此容易得到x(n)=R4(n)的4点DFT为X(k)=DFTx(n)4=4(k)，这一特殊的结果在下面将得到进一步解释。第3章 离散傅里叶变换(DFT) 图 3-1 DFT与序列傅里叶变换、Z变换的关系 第3章 离散傅里叶变换(DFT) knNW3.1.3 DFT的隐含周期性的隐含周期性 前面定义的DFT变换对中，x(n)与X(k)均为有限长序列，但由于的周期性，使(3.1.1)和(3.1.2)式中的X(k)隐含周期性，且周期均为N。对任意整数m，总有所以(3.1.1)式中，X（k)满足

10、：(),kk mNNNNWWk m为整数, 为自然数，11()00( )( )( )()NNknk mN nNNnnX kx n Wx n WX kmN11()0011( )( )( )()NNknk n mNNNkkx nX k WX k Wx nmNNN第3章 离散傅里叶变换(DFT) (3.1.5)(3.1.6)( )()mx nx nmN( )( )( )Nx nx nRn上述关系如图3.1.2（a）和（b）所示。一般称周期序列中从n=0到N1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列。因此x(n)与的上述关系可叙述为：是x(n)的周期延拓序列，x(n)是的主值序列。)

11、(nx)(nx)(nx)(nx)(nx)(nx实际上，任何周期为N的周期序列都可以看做长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是 的一个周期，即)(nx)(nx第3章 离散傅里叶变换(DFT) 为了以后叙述简洁，当N大于等于序列x(n)的长度时，将(3.1.5)式用如下形式表示：(3.1.7)式中x(n) N表示x(n)以N为周期的周期延拓序列，(n)N表示模N对n求余，即如果n=MN+n1 0n1N1, M为整数则(n)N=n1 例如，, 则有所得结果符合图3.1.2（a）和（b）所示的周期延拓规律。( )( )Nx nx n88, ( )( )Nx nx n88(8)(8)

12、(0)(9)(9)(1)xxxxxx第3章 离散傅里叶变换(DFT) 图3.1.2 x(n)及其周期延拓序列第3章 离散傅里叶变换(DFT) )(nx)(nx应当说明，若x(n)实际长度为M，延拓周期为N，则当NM时，(3.1.5)式仍表示以N为周期的周期序列，但(3.1.6)和 (3.1.7)式仅对NM时成立。图3.1.2（a）中x(n)实际长度M=6，当延拓周期N=4时，如图3.1.2（c）所示。 如果x(n)的长度为M，且，NM，则可写出的离散傅里叶级数表示式Nnxnx)()(3.1.8)(3.1.9)111000( )( )( )( )NNNknknknNNNNnnnX kx n Wx

13、 nWx n W110011( )( )( )NNknknNNkkx nX k WX k WNN第3章 离散傅里叶变换(DFT) 式中即X(k)为的主值序列。将(3.1.8)和(3.1.9)式与DFT的定义(3.1.1)和(3.1.2)式相比较可知，有限长序列x(n)的N点离散傅里叶变换X(k)正好是x(n)的周期延拓序列x(n)N的离散傅里叶级数系数的主值序列，即。后面要讨论的频域采样理论将会加深对这一关系的理解。我们知道，周期延拓序列频谱完全由其离散傅里叶级数系数确定，因此，X(k)实质上是x(n)的周期延拓序列x(n) N的频谱特性，这就是这就是N点点DFT的第二种的第二种物理解释（物理

14、意义）。物理解释（物理意义）。( )( )( )NX kX k Rk(3.1.10)( )X k( )X k)()()(kRkXkXN( )X k第3章 离散傅里叶变换(DFT) 例例 3.1.4 有限长序列x(n)为 01)(nx0n4 其余n 求其N=5 点离散傅里叶变换X(k)。 解解 序列x(n)如图2-12（a）所示。在确定DFT时，我们可以将x(n)看作是一个长度N5的任意有限长序列。首先我们以N=5 为周期将x(n)延拓成周期序列 ，如图2-12（b）， 的DFS与x(n)的DFT相对应。因为在图2-12（ b）中的序列在区间0nN-1 上为常数值，所以可以得出 )(nx011)

15、()/2210)/2(NeeekXNkjkjNnnNkj（k=0, N, 2N, 其他 (2-35)第3章 离散傅里叶变换(DFT) 也就是说，只有在k=0 和k=N 的整数倍处才有非零的DFS系数 值。这些DFS系数如图2-12（c）所示。为了说明傅里叶级数 与x(n)的频谱X(ej)间的关系，在图2-12（c）中也画出了傅里叶变换的幅值|X（ej)|。显然， 就是X(ej)在频率k=2k/N 处的样本序列。按照式（2-29），x(n)的DFT对应于取 的一个周期而得到的有限长序列X(k)。这样，x(n)的5点DFT如图2-12（d）所示。 )(kx)(kX)(kX)(kX0511)()(5

16、2215052kjkjnnkjeeenxkX k=0, 1, 2, 3, 4 k=0 k=0, 1, 2, 3, 4 第3章 离散傅里叶变换(DFT) 图 3-3DFT的举例说明（a） 有限长序列x(n); （b）由x(n)形成的周期N=10的周期序列x(n); （c） DFT的幅值 第3章 离散傅里叶变换(DFT) 图 3-2 DFT的举例说明（a） 有限长序列x(n); （b） 由x(n)形成的周期N=5的周期序列; （c） 对应于 的傅里叶级数 和x(n)的傅里叶变换的幅度特性|X(ej)|; （d） x(n)的DFT X(k) )(nx)(kX第3章 离散傅里叶变换(DFT) 【例例3

17、.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点和32点DFT。调用fft函数求解本例的程序ep312.m如下:第3章 离散傅里叶变换(DFT) % 例3.1.2程序ep312.m% DFT的MATLB计算xn=1 1 1 1; %输入时域序列向量xn=R4(n)Xk16=fft(xn, 16); %计算xn的16点DFTXk32=fft(xn, 32);

18、%计算xn的32点DFT%以下为绘图部分（省略，程序集中有）程序运行结果如图3.1.3所示。第3章 离散傅里叶变换(DFT) 图3.1.3 程序ep312.m 运行结果 第3章 离散傅里叶变换(DFT) 现在解释DFTR5(n)5=5(k)。根据DFT第二种物理解释可知，DFTR5(n)5表示R5(n)以5为周期的周期延拓序列R5(n)5的频谱特性，因为R5(n)5是一个直流序列，只有直流成分（即零频率成分）。 第3章 离散傅里叶变换(DFT) 3.1.4 用用MATLAB计算序列的计算序列的DFTMATLAB提供了用快速傅里叶变换算法FFT(算法见第4章介绍)计算DFT的函数fft，其调用格

19、式如下: Xk = fft (xn, N)；调用参数xn为被变换的时域序列向量，N是DFT变换区间长度，当N大于xn的长度时，fft函数自动在xn后面补零。函数返回xn的N点DFT变换结果向量Xk。当N小于xn的长度时，fft函数计算xn的前面N个元素构成的N长序列的N点DFT，忽略xn后面的元素。 Ifft函数计算IDFT，其调用格式与fft函数相同，可参考help文件。第3章 离散傅里叶变换(DFT) 3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质3.2.1 线性性质线性性质如果x1(n)和x2(n)是两个有限长序列，长度分别为N1和N2，且y(n)=ax1(n)+bx2(n)式

20、中，a、b为常数，取N=maxN1, N2, 则y(n)的N点DFT为Y(k)=DFTy(n)N=aX1(k)+bX2(k) 0kN1 (3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT。 第3章 离散傅里叶变换(DFT) 3.2.2 循环移位性质循环移位性质1序列的循环移位序列的循环移位 设x(n)为有限长序列，长度为M，MN，则x(n)的循环移位定义为y(n)=x(n+m) NRn(n) (3.2.2)(3.2.2)式表明，将x(n)以N为周期进行周期延拓得到，再将左移m得到，最后取的主值序列则得到有限长序列x(n)的循环移位序列y(n)。 M=6, N=8,

21、 m=2时，x(n)及其循环移位过程如图3.2.1所示。Nnxnx)()()(nx)(mnx)(mnx第3章 离散傅里叶变换(DFT) 显然，y(n)是长度为N的有限长序列。观察图3.2.1可见，循环移位的实质是将x(n)左移m位，而移出主值区(0nN1)的序列值又依次从右侧进入主值区。“循环移位”就是由此得名的。由循环移位的定义可知，对同一序列x(n)和相同的位移m，当延拓周期N不同时，y(n)=x(n+m)NRn(n)则不同。请读者画出N = M=6，m=2时，x(n)的循环移位序列y(n)波形图。第3章 离散傅里叶变换(DFT) 图3.2.1 x(n)及其循环移位过程第3章 离散傅里叶变

22、换(DFT) (e)x(n)21n 0N1N2on 0N1N221n 0N2N1( f )( g )210 x(n)n0n)(nxNnxnx)2()2(0n)()2(nRnxNN0N1n(a)(b)(c)(d )N1N1N1第3章 离散傅里叶变换(DFT) 2 时域循环移位定理时域循环移位定理 设x(n)是长度为M（MN）的有限长序列，y(n)为x(n)的循环移位，即y(n)=x(n+m)NRn(n)则(3.2.3)其中X(k)=DFTx(n)N 0kN1( )DFT ( )( )kmNNY ky nWX k第3章 离散傅里叶变换(DFT) nkNNWnx)(证明证明1令n+m=n，则有由于上

23、式中求和项以N为周期，因此对其在任一周期上的求和结果相同。将上式的求和区间改在主值区，则得1100( )DFT ( )()( )()NNknknNNNNNNnnY ky nx nmRn Wx nmW11()( )( )( )NmNmk nmkmknNNNNNnmnmY kx nWWx nW 1100( )( )( )( )NNkmknkmknkmNNNNNNnnY kWx nWWx n WWX k第3章 离散傅里叶变换(DFT) 证明证明2)()()(kXWmnxDFSmnxDFSmkNN ()( ) ()( ) ()( )( )( )( )NNNNmkNNmkNDFT x nmRnDFT x

24、 nm RnDFS x nm RnWX k RkWX k第3章 离散傅里叶变换(DFT) 3 频域循环移位定理频域循环移位定理如果X(k)=DFTx(n)N 0kN1Y(k)=X(k+l)NRN(k)则(3.2.4)(3.2.4)式的证明方法与时域循环移位定理类似，直接对Y(k)=X(k+l)NRN(k)进行IDFT即得证。( )IDFT ( )( )nlNNy nY kW x n第3章 离散傅里叶变换(DFT) 说 明 本 性 质 与 时 域 移 位 性 质 成 对 偶 关 系. 本 性 质 又 称 调 制 特 性, 时 域 序 列 的 调 制 等 效 于 频 域 移 位. 注 意 是 圆

25、周 移 位 . 由 此 性 质 可 得 出 以 下 两 个 公 式:第3章 离散傅里叶变换(DFT) 3.2.3 循环卷积定理循环卷积定理时域循环卷积定理是DFT中最重要的定理，具有很强的实用性。已知系统输入和系统的单位脉冲响应，计算系统的输出，以及FIR滤波器用FFT实现等，都是基于该定理的。下面首先介绍循环卷积的概念和计算循环卷积的方法，然后介绍循环卷积定理。1 两个有限长序列的两个有限长序列的循环卷积循环卷积设序列h(n)和x(n)的长度分别为N1和N2 。h(n)与x(n)的N点循环卷积定义为（3.2.5）1c0( )( ) ()( )NNNmy nh m x nmRn第3章 离散傅里

26、叶变换(DFT) 式中，L称为循环卷积区间长度，LmaxN，M。上式显然与第1章介绍的线性卷积不同，为了区别线性卷积，用 *表示循环卷积，用表示L点循环卷积，即yc(n)=h(n)x(n)。观察（3.2.5）式，x(nm)L是以L为周期的周期信号，n和m的变化区间均是0, L1，第3章 离散傅里叶变换(DFT) 1 1、 圆圆 周周 卷卷 积积 定定 义义2 2、圆、圆 周周 卷卷 积积 的的 实实 现现 步步 骤骤圆周卷积圆周卷积第3章 离散傅里叶变换(DFT) 卷积过程可以用图3-15来表示。圆周卷积过程中，求和变量为m, n为参变量。先将x2(m)周期化，形成x2(m)N，再反转形成x2

27、(-m)N，取主值序列则得到x2(-m)NRN(m)，通常称之为x2(m)的圆周反转。对x2(m)的圆周反转序列圆周右移n，形成x2(n-m)NRN(m)，当n=0,1,2,N-1时，分别将x1(m)与x2(n-m)NRN(m)相乘，并在m=0 到N-1 区间内求和，便得到圆周卷积y(n)。 可以看出,它和周期卷积过程是一样的，只不过这里要取主值序列。特别要注意，两个长度小于等于N的序列的N点圆周卷积长度仍为N，这与一般的线性卷积不同。圆周卷积用符号来表示。 圆周内的N表示所作的是N点圆周卷积。 N第3章 离散傅里叶变换(DFT) 图图 3-15 圆周卷积过程示意图圆周卷积过程示意图 x1(n

28、)1N1nx2(n)1N1nx2(0 m)NRN(m)1N1mooo第3章 离散傅里叶变换(DFT) 图图 3-15 圆周卷积过程示意图圆周卷积过程示意图 x2(1 m)NRN(m)1N1mx2(2 m)NRN(m)1N1my(n) x1(n) x2(n)233211N1noooN第3章 离散傅里叶变换(DFT) 当n = 0, 1, 2, , L1时，由x(n)形成的序列为: x(0), x(1), , x(L1)。令n=0, m=0, 1, , L1，由式（3.2.5）中x(n-m)L形成x(n)的循环倒相序列为与序列x(n)进行对比，相当于将第一个序列值x(0)不动，将后面的序列反转18

29、0再放在 x(0) 的后面。这样形成的序列称为x(n)的循环倒相序列。(0) , ( 1) , ( 2) , , (1) (0), (1), (2), , (1)LLLLxxxxLxx Lx Lx直接计算该式比较麻烦。计算机中采用矩阵相乘或快速傅里叶变换（FFT）的方法计算循环卷积。第3章 离散傅里叶变换(DFT) 令n = 1, m = 0, 1, , L-1，由式（3.2.5）中x(n-m)L形成的序列为观察上式等号右端序列，它相当于x(n)的循环倒相序列向右循环移一位，即向右移1位，移出区间0, L1的序列值再从左边移进。再令n = 2, m = 0, 1, , L1，此时得到的序列又是

30、上面的序列向右循环移1位。依次类推，当n和m均从0变化到L-1时，得到一个关于x(nm)L的矩阵如下： (1) , (0) , ( 1) , , (2) (1), (0), (1), , (2)LLLLxxxxLxxx Lx第3章 离散傅里叶变换(DFT) （3.2.6） (0)(1)(2)(1)(1)(0)(1)(2)(2)(1)(0)(3)(1)(2)(3)(0)xx Lx Lxxxx Lxxxxxx Lx Lx Lx第3章 离散傅里叶变换(DFT) 上面矩阵称为x(n)的L点“循环卷积矩阵”，其特点是:（1） 第1行是序列x(0), x(1), , x(L1)的循环倒相序列。注意，如果x

31、(n)的长度ML，则需要在x(n)末尾补LM个零后，再形成第一行的循环倒相序列。（2） 第1行以后的各行均是前一行向右循环移1位形成的。（3） 矩阵的各主对角线上的序列值均相等。有了上面介绍的循环卷积矩阵，就可以写出式（3.2.5）的矩阵形式如下:第3章 离散傅里叶变换(DFT) （3.2.7） 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 Lxhyxxxxhy Lx Lx Lx Lxh L按照上式，可以在计算机上用矩阵相乘的方法计算两个序列的循环卷积，这里关

32、键是先形成循环卷积矩阵。上式中如果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), (3)1,1,1,1h nhhhhx nxxxx解解 按照式（3.2.21）写出h(n)与x(n)的4点循环卷积矩阵形式为cccc(0)1432110(1)2143110(2)3214110(3)4321110yyyy 第3章 离散傅里叶变换(DFT) cccccccc(0)111000043

33、2(1)1321000043(2)1632100004(3)110432100000904321000(4)0043210007(5)00043210(6)0400004321(7)0yyyyyyyy 0h(n)与x(n)的8点循环卷积矩阵形式为第3章 离散傅里叶变换(DFT) h(n)和x(n)及其4点和8点循环卷积结果分别如图3.2.2(a)、(b)、(c)和(d)所示。请读者计算验证本例的8点循环卷积结果等于h(n)与x(n)的线性卷积结果。后面将证明，当循环卷积区间长度L大于等于y(n) = h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。 第3章 离散傅里叶变换(DFT) 图

34、3.2.2 序列及其循环卷积波形第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 kXk（3.2.9）1122( )DFT( ) ,( )DFT( )NNX kx nXkx n第3章 离散傅里叶变换(DFT) 证明证明 直接对(3.2.8)式两边进行DFT，则有1112001

35、11200( )DFT ( )( )()( )( )()NNNknNNNnmNNknNNmnX kx nx m xnmRn Wx mxnmW 第3章 离散傅里叶变换(DFT) 令nm=n，则有因为上式中是以N为周期的，所以对其在任一个周期上求和的结果不变。因此10121101)(21)()()()()(NmmNmnknNNkmNNmmNmnmnkNNWnxWmxWnxmxkX2)(knNNWnx第3章 离散傅里叶变换(DFT) 由于，因此即循环卷积亦满足交换律。 10)()() ()()(21101021NkkXkXWnxWmxkXNmNnknNkmN，1221( )DFT ( )( )( )

36、( )( )X kx nX k XkXk X k1221( )IDFT( )( )( )( )( )x nX kx nx nx nx n第3章 离散傅里叶变换(DFT) 作为习题请读者证明以下频域循环卷积定理:如果x(n)=x1(n)x2(n)，则(3.2.10a) 11( )DFT ( )( )NX kx nX kN2( )XkN 11201( )()( )NNNlX l XklRkN第3章 离散傅里叶变换(DFT) 112101( )( )()( )NNNlX kXl XklRkN或(3.2.10b)式中相对频域循环卷积定理，称(3.2.9)式为时域循环卷积定理。 21( )( )X kX

37、kNN 1122 ( )DFT ( )01( )DFT( )NNX kx nkNXkx n第3章 离散傅里叶变换(DFT) 补充：循环反褶性质补充：循环反褶性质11)(0)0()()(11)(0)0()(NkkNXkXkXnxDFTNkkNxkxnxNNN第3章 离散傅里叶变换(DFT) 补充：补充： 有限长序列的线性卷积与圆周卷积有限长序列的线性卷积与圆周卷积 时域圆周卷积在频域上相当于两序列的DFT的乘积，而计算DFT可以采用它的快速算法快速傅里叶变换（FFT）（见第4章）， 因此圆周卷积与线性卷积相比，计算速度可以大大加快。 但是实际问题大多总是要求解线性卷积。例如，信号通过线性时不变系

38、统，其输出就是输入信号与系统的单位脉冲响应的线性卷积， 如果信号以及系统的单位脉冲响应都是有限长序列， 那么是否能用圆周卷积运算来代替线性卷积运算而不失真呢？下面就来讨论这个问题。 设x1(n)是N1点的有限长序列（0nN1-1），x2(n)是N2点的有限长序列（0nN2-1）。 第3章 离散傅里叶变换(DFT) （1）先看它们的线性卷积 1021212111)()()()()()()(Nmmmnxmxmnxmxnxnxnyx1(m)的非零区间为 0mN1-1 x2(n-m)的非零区间为 0n-mN2-1 (2-43)第3章 离散傅里叶变换(DFT) 将两个不等式相加，得到 0nN1+N2-2

39、 在上述区间外，不是x1(m)=0就是x2(n-m)=0，因而y1(n)=0。所以y1(n)是N1+N2-1 点有限长序列，即线性卷积的长度等于参与卷积的两序列的长度之和减1。第3章 离散傅里叶变换(DFT) （2）我们再来看x1(n)与x2(n)的圆周卷积。先假设进行L点的圆周卷积，再讨论L取何值时，圆周卷积才能代表线性卷积。 设y(n)=x1(n)x2(n)是两序列的L点圆周卷积，LmaxN1, N2，这就要将x1(n)与x2(n)都看成是L点的序列。在这L个序列值中，x1(n)只有前N1个是非零值，后L-N1个均为补充的零值。同样， x2(n)只有前N2个是非零值，后L-N2个均为补充的

40、零值。则 L102121)()()()()()(LmLLnRmnxmxnxnxnyL（2-44） 第3章 离散傅里叶变换(DFT) 为了分析其圆周卷积，我们先将序列x1(n)与x2(n)以L为周期进行周期延拓 )()()()()()(222111rLnxnxnxkLnxnxnxrLkL它们的周期卷积序列为 )()()()()()()()(1210121012101rLnymrLnxmxmrLnxmxmnxmxnyrLmrrLmLLm（2-45） 第3章 离散傅里叶变换(DFT) 前面已经分析了y1(n)具有N1+N2-1个非零值。因此可以看到， 如果周期卷积的周期LN1+N2-1，那么y1(n

41、)的周期延拓就必然有一部分非零序列值要交叠起来，从而出现混叠现象。只有在LN1+N2-1 时，才没有交叠现象。这时, 在y1(n)的周期延拓 中， 每一个周期L内，前N1+N2-1个序列值正好是y1(n)的全部非零序列值，而剩下的L-(N1+N2-1)个点上的序列值则是补充的零值。 圆周卷积正是周期卷积取主值序列 )(1ny)()()(1nRrLnynyLr)()()()()(21nRnynxnxnyLL因此 (2-46)第3章 离散傅里叶变换(DFT) 所以要使圆周卷积等于线性卷积而不产生混叠的必要条件为 121NNL（2-47） 满足此条件后就有 )()(1nyny即 x1(n) x2(n

42、)=x1(n)*x2(n) L 下图（d）、（e）、（f）正反映了（2-46）式的圆周卷积与线性卷积的关系。在图2-16（d）中，L=6小于N1+N2-1=8，这时产生混叠现象，其圆周卷积不等于线性卷积；而在图2-16（e）、（f）中, L=8和L=10，这时圆周卷积结果与线性卷积相同，所得y(n)的前8点序列值正好代表线性卷积结果。 所以只要LN1+N2-1，圆周卷积结果就能完全代表线性卷积。 第3章 离散傅里叶变换(DFT) 图 线性卷积与圆周卷积第3章 离散傅里叶变换(DFT) 例例 一个有限长序列为 )5(2)()(nnnx（1） 计算序列x(n)的10点离散傅里叶变换。（2） 若序列

43、y(n)的DFT为 )()(1022kXekYkj式中，X(k)是x(n)的10点离散傅里叶变换，求序列y(n)。 第3章 离散傅里叶变换(DFT) （3）若10点序列y(n)的10点离散傅里叶变换是 )()()(kWkXkY式中, X(k)是序列x(n)的10点DFT，W(k)是序列w(n)的10点DFT 01)(nw0n6 其他 求序列y(n)。 第3章 离散傅里叶变换(DFT) 解解 （1） 由式（2-30）可求得x(n)的10点DFT kkjknkNnnnkNeWWnnWnxkX) 1(212121)5(2)()()(510251010101100 （2）X(k)乘以一个WNkm形式的

44、复指数相当于是x(n)圆周移位m点。 本题中m=-2, x(n)向左圆周移位了2点， 就有 y(n)=x(n+2)10R10(n)=2(n-3)+(n-8) 90 k第3章 离散傅里叶变换(DFT) （3）X(k)乘以W(k)相当于x(n)与w(n)的圆周卷积。为了进行圆周卷积，可以先计算线性卷积再将结果周期延拓并取主值序列。 x(n)与w(n)的线性卷积为z(n)=x(n)*w(n)=1, 1, 1, 1, 1, 3, 3, 2, 2, 2, 2, 2圆周卷积为 )()10()(10nRrnznyr 在 0n9 求和中，仅有序列z(n)和z(n+10)有非零值，用表列出z(n)和z(n+10

45、)的值，对n=0, 1, 2, , 9求和，得到： 第3章 离散傅里叶变换(DFT) n0 1 2 3 4 5 6 7 8 910 11Z(n)z(n+10) 1 1 1 1 1 3 3 2 2 22 2 0 0 0 0 0 0 0 02 20 0y(n)3 3 1 1 1 3 3 2 2 2_ _所以10点圆周卷积为 y(n)=3, 3, 1, 1， 1, 3, 3, 2, 2, 2 第3章 离散傅里叶变换(DFT) 2.5.5 共轭对称性共轭对称性 设x*(n)为x(n)的共轭复序列，则 DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0kN-1

46、且 X(N)=X(0) （2-48） 证证 )(*)()(*)()()()(*)()()()(*)(*10)(10*10kNXkRkNXkRWnxkRkXkRWnxkRWnxnxDFTNNNNnnkNNNNNnNNnnkNNnkN0kN-1 第3章 离散傅里叶变换(DFT) 3.2.4 复共轭序列的复共轭序列的DFT 设x*(n)是x(n)的复共轭序列，长度为N，X(k)=DFTx(n)N，则(3.2.11)且X(N)=X(0)。证明证明 根据DFT的唯一性，只要证明(3.2.11)式右边等于左边即可。DFTx*(n)=X*(-k)NRN(k)=X*(N-k)NRN(k) =X*(N-k) 0

47、kN-1 第3章 离散傅里叶变换(DFT) 又由X(k)的隐含周期性，有X(N)=X(0)用同样的方法可以证明 (3.2.12)11*()*()001*0()( )( )( )DFT( )NNN k nN k nNNnnNknNNnXNkx n Wx n Wx n Wx n*DFT()( )NxNnXk122njnNNjnNNeeW这里利用了 第3章 离散傅里叶变换(DFT) 3.2.5 DFT的共轭对称性的共轭对称性1 有限长共轭对称序列和共轭反对称序列有限长共轭对称序列和共轭反对称序列为了区别于傅里叶变换中所定义的共轭对称（或共轭反对称）序列，下面用xep(n)和xop(n)分别表示有限长

48、共轭对称序列和共轭反对称序列，则二者满足如下关系式：(3.2.13a)(3.2.13b)*epep( )() 01xnxNnnN*opop( )() 01xnxNnnN 第3章 离散傅里叶变换(DFT) 当N为偶数时，将上式中的n换成N/2n，可得到：上式更清楚地说明了有限长序列共轭对称序列是关于n=N/2点对称。容易证明，如同任何实函数都可以分解成偶对称分量和奇对称分量一样，任何有限长序列x(n)都可以表示成其共轭对称分量和共轭反对称分量之和，即 *epep()() 01222NNNxnxnn*opop()() 01222NNNxnxnn 第3章 离散傅里叶变换(DFT) (3.2.14)

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

50、可得*r*i1( )Re ( ) ( )( )21j ( )jIm ( ) ( )( )2x nx nx nx nx nx nx nx n第3章 离散傅里叶变换(DFT) (3.2.18) 由(3.2.11)式和(3.2.16b)式可得 (3.2.19)*rep11DFT( )DFT ( )( )( )()( )22x nx nx nX kXNkXk*iop11DFTj ( )DFT ( )( )( )()( )22x nx nx nX kXNkXk第3章 离散傅里叶变换(DFT) 由DFT的线性性质即可得 (3.2.20)其中，Xop(k)=DFTxr(n)是X(k)的共轭对称分量，Xop(

51、k)=DFTjxi(n)是X(k)的共轭反对称分量。 (2) 如果将x(n)表示为(3.2.21) epop( )DFT ( )( )( )X kx nXkXkepop( )( )( )01x nxnxnnN第3章 离散傅里叶变换(DFT) 其中，是x(n)的共轭对称分量，是x(n)的共轭反对称分量, 那么，由(3.2.12)式可得*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn*ep11DFT( )DFT ( )()( )( )Re( )22xnx nxNnX kXkX k*op11DFT( )DFT ( )()( )( )Im( )22xnx nxN

52、nX kXkjX k第3章 离散傅里叶变换(DFT) 因此 (3.2.22)其中RI( )DFT ( )( )j( )X kx nXkX kRep( )Re( )DFT()XkX kxIopj( )jIm( )( )X kX kDFT xn第3章 离散傅里叶变换(DFT) 综上所述，可总结出DFT的共轭对称性质：如果序列x(n)的DFT为X(k)，则x(n)的实部和虚部（包括j）的DFT分别为X(k)的共轭对称分量和共轭反对称分量；而x(n)的共轭对称分量和共轭反对称分量的DFT别为X(k)的实部和虚部乘以j。第3章 离散傅里叶变换(DFT) 共轭对称性第3章 离散傅里叶变换(DFT) 第3章

53、 离散傅里叶变换(DFT) XX10-23第3章 离散傅里叶变换(DFT) 另外，请读者根据上述共轭对称性证明有限长实序列另外，请读者根据上述共轭对称性证明有限长实序列DFT的共轭对称性（见本章习题题的共轭对称性（见本章习题题7）。 设x(n)是长度为N的实序列，且X(k)=DFTx(n)N，*( )()( )( )( )()( )NNNDFT x nXkx nx nX kXkRk NNNNkXkXkXkXsequenceoddcircularkNXkXsequenceevencircularkXkX)()(|)(| )(|: )(Im)(Im: )(Re)(Re第3章 离散傅里叶变换(DFT

54、) 设x(n)是长度为N的实序列，且X(k)=DFTx(n)N，则X(k)满足如下对称性： (1) X(k)共轭对称，即X(k)=X*(N-k) k=0, 1, , N-1 (3.2.23) (2) 如果x(n)是偶对称序列，即x(n)=x(Nn)，则X(k)实偶对称，即X(k)=X(Nk) (3.2.24) (3) 如果是奇对称序列，即x(n)=x(Nn)，则X(k)纯虚奇对称，即X(k)=X(Nk) (3.2.25)第3章 离散傅里叶变换(DFT) 奇奇 偶偶 虚虚 实实 关关 系系 表表 奇奇 - - 指序列是指序列是圆周圆周奇对称序列奇对称序列 偶偶 - - 指序列是指序列是圆周圆周偶

55、对称序列偶对称序列虚虚 - - 指序列是纯虚序列指序列是纯虚序列实实 - - 指序列是实序列指序列是实序列圆周圆周奇对称序列奇对称序列圆周圆周偶对称序列偶对称序列1)1)各序列都是有限长序列各序列都是有限长序列( (隐含周期性隐含周期性) )2) 2) 根据时域根据时域, ,频域的对偶性质频域的对偶性质, , 上表的时域与频域可以互调上表的时域与频域可以互调第3章 离散傅里叶变换(DFT) 实际中经常需要对实序列进行DFT，利用上述对称性质，可减少DFT的运算量，提高运算效率。例如，计算实序列的N点DFT时，当N=偶数时，只需计算X(k)的前面N/2+1点，而N = 奇数时，只需计算X(k)的

56、前面(N+1)/2点，其他点按照(3.2.22)式即可求得。例如， X(N1)=X*(1), X(N2)=X*(2), 这样可以减少近一半运算量。X(k)=X*(N-k) k=0, 1, , N-1 第3章 离散傅里叶变换(DFT) 【例例3.2.2】 利用DFT的共轭对称性，设计一种高效算法，通过计算一个N点DFT，就可以计算出两个实序列x1(n)和x2(n)的N点DFT。解解构造新序列x(n)=x1(n)+jx2(n)，对x(n)进行DFT，得到：第3章 离散傅里叶变换(DFT) 由(3.2.17)、(3.2.18)和(3.2.19)式得到：所以，由X(k)可以求得两个实序列x1(n)和x

57、2(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章 离散傅里叶变换(DFT) 补充. Parsevals relation:102102| )(|1| )(|NkNnxkXNnxE1010*)(*)(1)()(NkNnkYkXNnynx*111*000111*0001( )( )( )( )11( )( )( )( )

58、NNNknNnnkNNNknNknnx n y nx nYk WNYkx n WX k YkNN第3章 离散傅里叶变换(DFT) 补充.Duality(对偶性)-补充第3章 离散傅里叶变换(DFT) 第3章 离散傅里叶变换(DFT) 3.频域采样理论频域采样理论 首先，考虑一个任意的绝对可和的非周期序列x(n)，它的Z变换为 nnznxzX)()(由于绝对可和，所以其傅里叶变换存在且连续，故Z变换收敛域包括单位圆。如果我们对X(z)在单位圆上进行N点等距采样： 1, 1 , 0)()()(NkWnxzXkXnkNnWzkN（3-64） 第3章 离散傅里叶变换(DFT) 问题在于，这样采样以后是

59、否仍能不失真地恢复出原序列x(n)。 也就是说，频率采样后从X(k)的反变换中所获得的有限长序列， 即xN(n)=IDFTX(k)，能不能代表原序列x(n)？为此，我们先来分析X(k)的周期延拓序列 的离散傅里叶级数的反变换， 令其为 。)(kX)(nxNnkNNknkNNkNWkXNWkXNkXIDFSnx1010)(1)(1)()( mNkknmNnkNNkmmkNNWNmxWWmxNnx10)(101)()(1)(将式（3-64）代入此式，可得 第3章 离散傅里叶变换(DFT) 由于 10)(011NkknmNWNm=n+rN, r为任意整数 其他m 所以 rNrNnxnx)()(（3-

60、65） 这说明由 得到的周期序列 是原非周期序列x(n)的周期延拓，其时域周期为频域采样点数N。已经知道，时域采样造成频域的周期延拓，这里又看到一个对称的特性，即频域采样同样会造成时域的周期延拓。 )(kX)(nxN第3章 离散傅里叶变换(DFT) （1） 如果x(n)是有限长序列，点数为M，则当频域采样不够密，即当NM时，x(n)以N为周期进行延拓，就会造成混叠。这时，从 就不能不失真地恢复出原信号x(n)来。因此，对于M点的有限长序列x(n) )(nxN0)()(nxnx0nM-1 其他n 频域采样不失真的条件是频域采样点数N要大于或等于时域采样点数M（时域序列长度），即满足 NM （3-