离散傅里叶变换 (2)

1、第3章 离散傅里叶变换(DFT) 离散傅里叶变换第1页，共171页。第3章 离散傅里叶变换(DFT) 傅里叶变换和Z变换是数字信号处理中常用的重要数学变换。对于有限长序列，还有一种更为重要的数学变换，即本章要讨论的离散傅里叶变换(Discrete Fourier Transform，DFT)。DFT之所以更为重要，是因为其实质是有限长序列傅里叶变换的有限点离散采样，从而实现了频域离散化，使数字信号处理可以在频域采用数值运算的方法进行，这样就大大增加了数字信号处理的灵活性。更重要的是，DFT有多种快速算法，统称为快速傅里叶变换(Fast Fourier Transform，FFT)，从而使信号的

2、实时处理和设备的简化得以实现。第2页，共171页。第3章 离散傅里叶变换(DFT) 因此，时域离散系统的研究与应用在许多方面取代了传统的连续时间系统。所以说，DFT不仅在理论上有重要意义，而且在各种信号的处理中亦起着核心作用。 本章主要讨论本章主要讨论DFT的定义、物理意义、基本性质以及的定义、物理意义、基本性质以及频域采样和频域采样和DFT的应用举例等内容。的应用举例等内容。第3页，共171页。第3章 离散傅里叶变换(DFT) 3.1 离散傅里叶变换的定义及物理意义离散傅里叶变换的定义及物理意义3.1.1 DFT的定义的定义 设x(n)是一个长度为M的有限长序列，则定义x(n)的N点离散傅里

3、叶变换为(3.1.1)1, 1 , 0)()()(10NkWnxnxDFTkXNnknN第4页，共171页。第3章 离散傅里叶变换(DFT) X(k)的离散傅里叶逆变换(Inverse Discrete Fourier Transform, IDFT)为式中，N称为DFT变换区间长度，NM。通常称(3.1.1)式和(3.1.2)式为离散傅里叶变换对。为了叙述简洁，常常用DFTx(n)N和IDFTX(k)N分别表示N点离散傅里叶变换和N点离散傅里叶逆变换。下面证明IDFTX(k)的唯一性。2jeNNW1, 1 , 0)(1)()(10NnWkXNkXIDFTnxNnknN(3.1.2)第5页，共

4、171页。第3章 离散傅里叶变换(DFT) 把(3.1.1)式代入(3.1.2)式，有由于 为整数为整数iiNnmiiNnmWNWNmxWWmxNkXIDFTNknmkNNmNknmkNnkNNkNmmkNN, 0, 111)()(1)(10)(1010)(1010第6页，共171页。第3章 离散傅里叶变换(DFT) 所以，在变换区间上满足下式：IDFTX(k)N=x(n) 0nN-1由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。【例例3.1.1】 x(n)=R4(n), 求x(n)的4点和8点DFT。解解设变换区间N=4，则233j4400j22j4( )( )e401 e01,

5、2,31 eknknnnkkX kx n Wkk第7页，共171页。第3章 离散傅里叶变换(DFT) 设变换区间N=8，则 由此例可见，x(n)的离散傅里叶变换结果与变换区间长度N的取值有关。对DFT与Z变换和傅里叶变换的关系及DFT的物理意义进行讨论后，上述问题就会得到解释。 7 ,1 , 0,8sin2sin)()(837030828kkkeeWnxkXkjnnknjkn第8页，共171页。第3章 离散傅里叶变换(DFT) 3.1.2 DFT与傅里叶变换和与傅里叶变换和Z变换的关系变换的关系 设序列x(n)的长度为M，其Z变换和N(NM)点DFT分别为比较上面二式可得关系式 1010( )

6、ZT ( )( )( )DFT ( )( )0,1,1MnnMknNNnX zx nx n zX kx nx n WkN1, 1 , 0,)()(1, 1 , 0,)()(22NkeXkXNkzXkXkNjezkNj(3.1.3)或 (3.1.4)第9页，共171页。第3章 离散傅里叶变换(DFT) (3.1.3)式表明序列x(n)的N点DFT是x(n)的Z变换在单位圆上的N点等间隔采样。(3.1.4)式则说明X(k)为x(n)的傅里叶变换X(ej)在区间0, 2上的N点等间隔采样。这就是DFT的物理意义。由此可见，DFT的变换区间长度N不同，表示对X(ej)在区间0, 2上的采样间隔和采样点

7、数不同，所以DFT的变换结果不同。上例中， x(n)=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)，这一特殊的结果在下面将得到进一步解释。第10页，共171页。第3章 离散傅里叶变换(DFT) 图3.1.1 R4(n)的FT和DFT的幅度特性关系 第11页，共171页。第3章 离散傅里叶变换(DFT) knNW3.1.3 DFT的隐含周期性的隐含周期性 前面定义的DFT变换对中，x(n)与X(k)均为有限长序列，但由于的周期性，使(3.1.1)和(3.

8、1.2)式中的X(k)隐含周期性，且周期均为N。对任意整数m，总有所以(3.1.1)式中，X(k)满足： 实际上，任何周期为N的周期序列都可以看做长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是 的一个周期，即(),kk mNNNNWWk m为整数, 为自然数，11()00()( )( )( )NNk mN nknNNnnX kmNx n Wx n WX k)(nx)(nx第12页，共171页。第3章 离散傅里叶变换(DFT) 上述关系如图3.1.2（a）和（b）所示。一般称周期序列中从n=0到N1的第一个周期为的主值区间，而主值区间上的序列称为的主值序列。因此x(n)与的上述关系可

9、叙述为：是x(n)的周期延拓序列，x(n)是的主值序列。(3.1.5)(3.1.6)( )()mx nx nmN( )( )( )Nx nx nRn)(nx)(nx)(nx)(nx)(nx)(nx第13页，共171页。第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,

10、 ( )( )Nx nx n88(8)(8)(0)(9)(9)(1)xxxxxx第14页，共171页。第3章 离散傅里叶变换(DFT) 图3.1.2 x(n)及其周期延拓序列第15页，共171页。第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

11、)111000( )( )( )( )NNNknknknNNNNnnnX kx n Wx nWx n W110011( )( )( )NNknknNNkkx nX k WX k WNN第16页，共171页。第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

12、)实质上是x(n)的周期延拓序列x(n) N的频谱特性，这就是N点DFT的第二种物理解释（物理意义）。( )( )( )NX kX k Rk(3.1.10)( )X k( )X k)()()(kRkXkXN( )X k第17页，共171页。第3章 离散傅里叶变换(DFT) 现在解释DFTR4(n)4=4(k)。根据DFT第二种物理解释可知，DFTR4(n)4表示R4(n)以4为周期的周期延拓序列R4(n)4的频谱特性，因为R4(n)4是一个直流序列，只有直流成分（即零频率成分）。 第18页，共171页。第3章 离散傅里叶变换(DFT) 3.1.4 用用MATLAB计算序列的计算序列的DFTMA

13、TLAB提供了用快速傅里叶变换算法FFT(算法见第4章介绍)计算DFT的函数fft，其调用格式如下: 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文件。第19页，共171页。第3章 离散傅里叶变换(DFT) 【例例3.1.2】 设x(n)=R4(n)，X(ej)=FTx(n)。分别计

14、算X(ej)在频率区间0，2上的16点和32点等间隔采样，并绘制X(ej)采样的幅频特性图和相频特性图。解解 由DFT与傅里叶变换的关系知道，X(ej)在频率区间0，2上的16点和32点等间隔采样，分别是x(n)的16点和32点DFT。调用fft函数求解本例的程序ep312.m如下:第20页，共171页。第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); %计算xn的32点DFT%以下为绘图部分（省略

15、，程序集中有）程序运行结果如图3.1.3所示。第21页，共171页。第3章 离散傅里叶变换(DFT) 图3.1.3 程序ep312.m 运行结果 第22页，共171页。第3章 离散傅里叶变换(DFT) 3.2 离散傅里叶变换的基本性质离散傅里叶变换的基本性质3.2.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)N=aX1(k)+bX2(k) 0kN1 (3.2.1)其中X1(k)和X2(k)分别为x1(n)和x2(n)的N

16、点DFT。 第23页，共171页。第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, m=2时，x(n)及其循环移位过程如图3.2.1所示。Nnxnx)()()(nx)(mnx)(mnx第24页，共171页。第3章 离散傅里叶变换(DFT) 显然，y(n)是长度为N的有

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

18、移位，即则(3.2.3)其中)()()(kXWnyDFTkYkmNN10,)()(NknxDFTkXN)()()(nRmnxnyNN第27页，共171页。第3章 离散傅里叶变换(DFT) nkNNWnx)(证明证明令n+m=n，则有由于上式中求和项以N为周期，因此对其在任一周期上的求和结果相同。将上式的求和区间改在主值区，则得1100( )DFT ( )()( )()NNknknNNNNNNnnY ky nx nmRn Wx nmW11()( )( )( )NmNmk nmkmknNNNNNnmnmY kx nWWx nW 1100( )( )( )( )NNkmknkmknkmNNNNNNn

19、nY kWx nWWx n WWX k第28页，共171页。第3章 离散傅里叶变换(DFT) 3 频域循环移位定理频域循环移位定理如果X(k)=DFTx(n)N 0kN-1 Y(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第29页，共171页。第3章 离散傅里叶变换(DFT) 3.2.3 循环卷积定理循环卷积定理 时域循环卷积定理是DFT中最重要的定理，具有很强的实用性。已知系统输入和系统的单位脉冲响应，计算系统的输出，以及F

20、IR滤波器用FFT实现等，都是基于该定理的。下面首先介绍循环卷积的概念和计算循环卷积的方法，然后介绍循环卷积定理。1 两个有限长序列的循环卷积两个有限长序列的循环卷积设序列h(n)和x(n)的长度分别为N和M。h(n)与x(n)的L点循环卷积定义为（3.2.5）1c0( )( ) ()( )LLLmy nh m x nmRn第30页，共171页。第3章 离散傅里叶变换(DFT) 式中，L称为循环卷积区间长度，LmaxN，M。上式显然与第1章介绍的线性卷积不同，为了区别线性卷积，用 表示循环卷积，用表示L点循环卷积，即yc(n)=h(n) x(n)。观察(3.2.5)式，x(nm)L是以L为周期

21、的周期信号，n和m的变化区间均是0, L-1，因此直接计算该式比较麻烦。计算机中采用矩阵相乘或快速傅里叶变换(FFT)的方法计算循环卷积。下面介绍用矩阵计算循环卷积的公式。 第31页，共171页。第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)不动，将后面的序列反转180再放在 x(0) 的后面。这样形成的序列称为x(n)的循环倒相序列。(0) , (

22、1) , ( 2) , , (1) (0), (1), (2), , (1)LLLLxxxxLxx Lx Lx 第32页，共171页。第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, , L-1，此时得到的序列又是上面的序列向右循环移1位。依次类推，当n和m均从0变化到L-1时，得到一个关于x(nm)L的矩阵如下： (1) , (0) , ( 1) , , (

23、2) (1), (0), (1), , (2)LLLLxxxxLxxx Lx第33页，共171页。第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第34页，共171页。第3章 离散傅里叶变换(DFT) 上面矩阵称为x(n)的L点“循环卷积矩阵”，其特点是:（1） 第1行是序列x(0), x(1), , x(L1)的循环倒相序列。注意，如果注意，如果x(n)的长度的长度ML，则需要在，则需要在x(n)末尾补末尾补LM个零后，个零后，再形成第一行

24、的循环倒相序列。再形成第一行的循环倒相序列。（2） 第1行以后的各行均是前一行向右循环移1位形成的。（3） 矩阵的各主对角线上的序列值均相等。有了上面介绍的循环卷积矩阵，就可以写出式(3.2.5)的矩阵形式如下:第35页，共171页。第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第36页，共171页。第3章 离散傅里叶变换(DFT) 按照上式，可以在计算机上用矩

25、阵相乘的方法计算两个序列的循环卷积，这里关键是先形成循环卷积矩阵。上式中如果如果h(n)的长度的长度NL，则需要在，则需要在h(n)末尾补末尾补L-N个零个零。【例例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第37页，共171页。第3章 离散傅里叶变换(DFT) 解解 按照式（3.2.21）写出h(n)与x(n)的4点循环卷积矩阵形式为h(n)与x(n)的8点循环卷积矩阵形式为cccc(0)1432110(1)

26、2143110(2)3214110(3)4321110yyyy 第38页，共171页。第3章 离散傅里叶变换(DFT) cccccccc(0)1110000432(1)1321000043(2)1632100004(3)110432100000904321000(4)0043210007(5)00043210(6)0400004321(7)0yyyyyyyy 0第39页，共171页。第3章 离散傅里叶变换(DFT) h(n)和x(n)及其4点和8点循环卷积结果分别如图3.2.2(a)、(b)、(c)和(d)所示。请读者计算验证本例的8点循环卷积结果等于h(n)与x(n)的线性卷积结果。后面将证

27、明，当循环卷积区间长度L大于等于y(n) = h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。 第40页，共171页。第3章 离散傅里叶变换(DFT) 图3.2.2 序列及其循环卷积波形第41页，共171页。第3章 离散傅里叶变换(DFT) 2. 环卷积定理环卷积定理 有限长序列x1(n)和x2(n)的长度分别为N1和N2，N= maxN1, N2， x1(n)和x2(n)的N点循环卷积为则x(n)的N点DFT为其中2( )( )x nx nN 11210( )( )()( )NNNmx nx m xnmRn12( )DFT ( )( )( )NX kx nX kXk（3.2.9）11

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

29、xmxkX2)(knNNWnx第44页，共171页。第3章 离散傅里叶变换(DFT) 由于，因此即循环卷积亦满足交换律。 10)()() ()()(21101021NkkXkXWnxWmxkXNmNnknNkmN，1221( )DFT ( )( )( )( )( )X kx nX k XkXk X k1( )IDFT( )( )x nX kx n22( )( )x nx n1( )x n第45页，共171页。第3章 离散傅里叶变换(DFT) 作为习题请读者证明以下频域循环卷积定理:如果x(n)=x1(n)x2(n)，则(3.2.10a) 11( )DFT ( )( )NX kx nX kN2(

30、 )XkN 11201( )()( )NNNlX l XklRkN第46页，共171页。第3章 离散傅里叶变换(DFT) 112101( )( )()( )NNNlX kXl XklRkN或(3.2.10b)式中相对频域循环卷积定理，称(3.2.9)式为时域循环卷积定理。 21( )( )X kXkNN 1122 ( )DFT ( )01( )DFT( )NNX kx nkNXkx n第47页，共171页。第3章 离散傅里叶变换(DFT) 3.2.4 复共轭序列的复共轭序列的DFT 设x*(n)是x(n)的复共轭序列，长度为N，X(k)=DFTx(n)N，则且X(N)=X(0)。 证明证明 根

31、据DFT的唯一性，只要证明(3.2.11)式右边等于左边即可。*DFT( )()01Nx nXNkkN(3.2.11)第48页，共171页。第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 ()( )Nx NnX k第49页，共171页。第3章 离散傅里叶变换(DFT) 3.2.5 DFT的共轭对称性的共轭对称性1 有限长共轭对称序列和共轭反对称序列有限长共轭对称序列和共轭

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

33、p()() 01222NNNxnxnn*epep()() 01222NNNxnxnn 第51页，共171页。第3章 离散傅里叶变换(DFT) (3.2.14) 将上式中的n换成N-n，并取复共轭，再将(3.2.13a)式和(3.2.13b)式代入，得到：(3.2.15)(3.2.14)式分别加减(3.2.15)式，可得(3.2.16a)(3.2.16b)epop( )( )( )01x nxnxnnN*ep1( ) ( )()2xnx nxNn*op1( ) ( )()2xnx nxNn)()()()()(nxnxnNxnNxnNxopepopep第52页，共171页。第3章 离散傅里叶变换(

34、DFT) 2 DFT的共轭对称性的共轭对称性 (1) 如果将x(n)表示为x(n)=xr(n)+jxi(n) (3.2.17)其中那么，由(3.2.11)式和(3.2.16a)式可得*r*i1( )Re ( ) ( )( )21j ( )jIm ( ) ( )( )2x nx nx nx nx nx nx nx n第53页，共171页。第3章 离散傅里叶变换(DFT) (3.2.18) 由(3.2.11)式和(3.2.16b)式可得 (3.2.19)*rep11DFT( )DFT ( )( )( )()( )22x nx nx nX kXNkXk*iop11DFTj ( )DFT ( )( )

35、( )()( )22x nx nx nX kXNkXk第54页，共171页。第3章 离散傅里叶变换(DFT) 由DFT的线性性质即可得 (3.2.20)其中，Xop(k)=DFTxr(n)是X(k)的共轭对称分量，Xop(k)=DFTjxi(n)是X(k)的共轭反对称分量。 (2) 如果将x(n)表示为(3.2.21) epop( )DFT ( )( )( )X kx nXkXkepop( )( )( )01x nxnxnnN第55页，共171页。第3章 离散傅里叶变换(DFT) 其中，是x(n)的共轭对称分量， 是x(n)的共轭反对称分量, 那么，由(3.2.12)式可得*ep1( ) (

36、)()2xnx nx Nn*op1( ) ( )()2xnx nxNn*ep11DFT( )DFT ( )()( )( )Re( )22xnx nx NnX kXkX k*op11DFT( )DFT ( )()( )( )Im( )22xnx nxNnX kXkjX k第56页，共171页。第3章 离散傅里叶变换(DFT) 因此 (3.2.22)其中RI( )DFT ( )( )j( )X kx nXkX kRep( )Re( )DFT()XkX kxIopj( )jIm( )( )X kX kDFT xn第57页，共171页。第3章 离散傅里叶变换(DFT) 综上所述，可总结出综上所述，可总

37、结出DFT的共轭对称性质：如果序列的共轭对称性质：如果序列x(n)的的DFT为为X(k)，则，则x(n)的实部和虚部（包括的实部和虚部（包括j）的）的DFT分别为分别为X(k)的共轭对称分量和共轭反对称分量；而的共轭对称分量和共轭反对称分量；而x(n)的共轭对称分量和共的共轭对称分量和共轭反对称分量的轭反对称分量的DFT分别为分别为X(k)的实部和虚部乘以的实部和虚部乘以j。另外，请读者根据上述共轭对称性证明有限长实序列DFT的共轭对称性（见本章习题题7）。 设x(n)是长度为N的实序列，且X(k)=DFTx(n)N，则X(k)满足如下对称性： 第58页，共171页。第3章 离散傅里叶变换(D

38、FT) (1) X(k)共轭对称，即X(k)=X*(N-k) k=0, 1, , N-1 (3.2.23) (2) 如果x(n)是偶对称序列，即x(n)=x(N-n)，则X(k)实偶对称，即X(k)=X(N-k) (3.2.24) (3) 如果是奇对称序列，即x(n)=-x(N-n)，则X(k)纯虚奇对称，即X(k)=-X(N-k) (3.2.25)第59页，共171页。第3章 离散傅里叶变换(DFT) 实际中经常需要对实序列进行DFT，利用上述对称性质，可减少DFT的运算量，提高运算效率。例如，计算实序列的N点DFT时，当N=偶数时，只需计算X(k)的前面N/2+1点，而N = 奇数时，只需

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

40、)( )( )X kx nXkXk*ep11( )DFT( )( )()2Xkx nX kXNk*op21( )DFTj( )( )()2Xkx nX kXNk)()(21)()(*11kNXkXnxDFTkX*221( )DFT( )j ( )()2Xkx nX kXNk 第61页，共171页。第3章 离散傅里叶变换(DFT) 3.3 频频 率率 域域 采采 样样 时域采样定理告诉我们，在一定条件下，可以由时域离散采样信号恢复原来的连续信号。那么能不能也由频域离散采样恢复原来的信号（或原连续频率函数）？其条件是什么？内插公式又是什么形式？本节就上述问题进行讨论。 设任意序列x(n)的Z变换为

41、且X(z)的收敛域包含单位圆(即x(n)存在傅里叶变换)。在单位圆上对X(z)等间隔采样N点, 得到：nnznxzX)()(第62页，共171页。第3章 离散傅里叶变换(DFT) 显然，(3.3.1)式表示在区间0, 2上对x(n)的傅里叶变换X(ej)的N点等间隔采样。将X(k)看做长度为N的有限长序列xN(n)的DFT，即下面推导序列xN(n)与原序列x(n)之间的关系，并导出频域采样定理。( )IDFT ( )01Nx nX knN ，10)()()()(22NkWnxenxzXkXknNnknNjnezkNj (3.3.1) 第63页，共171页。第3章 离散傅里叶变换(DFT) 由D

42、FT与DFS的关系可知，X(k)是xN(n)以N为周期的周期延拓序列的离散傅里叶级数系数的主值序列，即( )x n)(kX1010( )( )DFS ( )( )( )( )( )( )IDFS( )1( )1( )NNNNNknNkNknNkX kXkx nX kX k Rkx nxnX kX k WNX k WN第64页，共171页。第3章 离散傅里叶变换(DFT) 将 (3.3.1) 式代入上式得式中1()0110Nk m nNkmniNiWNm， 为整数，其他 mNknmkNNkmknNkmNWNmxWWmxNnx10)(101)()(1)(第65页，共171页。第3章 离散傅里叶变换

43、(DFT) 因此所以( )()ix nx niN( )( )( )()( )NNNixnx n Rnx n iN Rn(3.3.3)(3.3.2)第66页，共171页。第3章 离散傅里叶变换(DFT) 式(3.3.3)说明，X(z)在单位圆上的N点等间隔采样X(k)的N点IDFT是原序列x(n)以N为周期的周期延拓序列的主值序列。综上所述，可以总结出频域采样定理： 如果序列x(n)的长度为M，则只有当频域采样点数NM时，才有xN(n)=IDFTX(k)=x(n)即可由频域采样X(k)恢复原序列x(n)，否则产生时域混叠现象。第67页，共171页。第3章 离散傅里叶变换(DFT) 满足频域采样定

44、理时，频域采样序列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第68页，共171页。第3章 离散傅里叶变换(DFT) 因为满足频域采样定理，所以式中将上式代入X(z)的表示式中，得到:(3.3.4a) 1111000011011( )( )( )11 ( )1NNNNknnknnNNnkknkNNNNknnX zX k WzX kWzN

45、NWzX kNWz10)(1)()(NknkNWkXNkXIDFTnx第69页，共171页。第3章 离散傅里叶变换(DFT) 1kNNW式中，因此 (3.3.4b)令 (3.3.5)则(3.3.6) 10111)(1)(NkkNNzWzkXNzX1111)(zWzNzkNNk10)()()(NkkzkXzX第70页，共171页。第3章 离散傅里叶变换(DFT) 式(3.3.6)称为用X(k)表示X(z)的内插公式，k(z)称为内插函数。将z=ej代入(3.3.4a)式，并进行化简，可得 (3.3.7)(3.3.8) 在数字滤波器的结构与设计中，我们将会看到，频域采样理论及有关公式可提供一种有用

46、的滤波器结构和滤波器设计途径，(3.3.7)式有助于分析FIR滤波器频率采样设计法的逼近性能。10j)2()()e (NkkNkXX)21(je)2/sin()2/sin(1)(NNN第71页，共171页。第3章 离散傅里叶变换(DFT) 【例例3.3.1】 长度为26的三角形序列x(n)如图3.3.1(a)所示。编写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)

47、求IDFT, 得到：绘制x16(n)和x32(n)波形图验证频域采样理论。161616( )IDFT( )xnXk323232( )IDFT( )xnXk第72页，共171页。第3章 离散傅里叶变换(DFT) MATLAB求解程序ep331.m如下：%数字信号处理(第三版）第3章例3.3.1程序ep331.% 频域采样理论验证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)x3

48、2n=ifft(X32k); %32点IFFTX32(k)得到x32(n)X16k=X32k(1:2:N); %隔点抽取X32k得到X16(k)x16n=ifft(X16k, N/2); %16点IFFTX16(k)得到x16(n)以下绘图部分省略。第73页，共171页。第3章 离散傅里叶变换(DFT) 程序运行结果如图3.3.1所示。图3.3.1(a)和(b)分别为X(ej)和x(n)的波形；图3.3.1(c)和(d)分别为X(ej)的16点采样|X16(k)|和x16(n)=IDFTX16(k)16波形图；图3.3.1(e)和(f)分别为X(ej)的32点采样|X32(k)|和x32(n)

49、=IDFTX32(k)32波形图；由于实序列的DFT满足共轭对称性，因此频域图仅画出0，上的幅频特性波形。本例中x(n)的长度M=26。从图中可以看出，当采样点数N=16M时，无时域混叠失真，x32(n)=IDFTX32(k)=x(n)。第74页，共171页。第3章 离散傅里叶变换(DFT) 图3.3.1 频域采样定理验证第75页，共171页。第3章 离散傅里叶变换(DFT) 3.4 DFT的应用举例的应用举例3.4.1 用用DFT计算线性卷积计算线性卷积用DFT计算循环卷积很简单。设h(n)和x(n)的长度分别为N和M, 其L点循环卷积为c( )( )y nh n且L 10( )( ) ()

50、( )LLLmx nh m x nmR n10)()()()(LknxDFTkXnhDFTkHLL第76页，共171页。第3章 离散傅里叶变换(DFT) 则由DFT的时域循环卷积定理有由此可见，循环卷积既可以在时域直接计算，也可以按照图3.4.1所示的计算框图在频域计算。由于DFT有快速算法，当L很大时，在频域计算循环卷积的速度快得多，因而常用DFT(FFT)计算循环卷积。cc( )DFT( )( )( )01LY ky nH k X kkL第77页，共171页。第3章 离散傅里叶变换(DFT) 图3.4.1 用DFT计算循环卷积的原理框图第78页，共171页。第3章 离散傅里叶变换(DFT)

51、 在实际应用中，为了分析时域离散线性时不变系统或者对序列进行滤波处理等，需要计算两个序列的线性卷积。与计算循环卷积一样，为了提高运算速度，也希望用DFT(FFT)计算线性卷积。而DFT只能直接用来计算循环卷积，因此，下面先导出线性卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件，最后得出用图3.4.1线性卷积的条件。第79页，共171页。第3章 离散傅里叶变换(DFT) 假设h(n)和x(n)都是有限长序列，长度分别是N和M。它们的线性卷积和循环卷积分别表示如下：其中所以10l)()()()()(Nmmnxmhnxnhnyc( )( )y nh n10( )( ) ()( )LLLmx

52、 nh m x nmR n(3.4.1)(3.4.2)L Lmax, ( )()iLN Mx nx niL第80页，共171页。第3章 离散傅里叶变换(DFT) 对照(3.4.1)式可以看出，上式中即 (3.4.3)1c010( )( )()( ) ()( )NLmiNLimy nh mx nmiL Rh m x niLm R n)()()(l10iLnymiLnxmhNmiLnRiLnyny)()()(lc第81页，共171页。第3章 离散傅里叶变换(DFT) (3.4.3)式说明，yc(n)等于yl(n)以L为周期的周期延拓序列的主值序列。我们知道，yl(n)长度为NM1，因此只有当循环卷

53、积长度LNM1时，yl(n)以L为周期进行周期延拓时才无时域混叠现象。此时取其主值序列显然满足yc(n)=yl(n)。由此证明了循环卷积等于线性卷积的条件是LNM1。图3.4.2中画出了h(n)、x(n)、h(n)*x(n)以及L分别取6、8、10时h(n) L x(n)的波形。由于h(n)长度N=4，x(n)长度M=5，NM1=8，因此只有L8时，h(n) L x(n)波形才与h(n)*x(n)相同。第82页，共171页。第3章 离散傅里叶变换(DFT) 图3.4.2 线性卷积与循环卷积波形图第83页，共171页。第3章 离散傅里叶变换(DFT) 综上所述，取LNM1，则可按照如图3.4.1

54、所示的计算框图用DFT(FFT)计算线性卷积。其中DFT和IDFT通常用快速算法(FFT)来实现，故常称其为快速卷积。实际上，经常遇到两个序列的长度相差很大的情况，例如MN。若仍选取LNM1，以L为循环卷积区间，并用上述快速卷积法计算线性卷积，则要求对短序列补很多零点，而且长序列必须全部输入后才能进行快速计算。因此要求存储容量大，运算时间长，并使处理延时很大，不能实现实时处理。第84页，共171页。第3章 离散傅里叶变换(DFT) 况且在某些应用场合，序列长度不定或者认为是无限长，如电话系统中的语音信号和地震检测信号等。显然，在要求实时处理时，直接套用上述方法是不行的。解决这个问题的方法是将长

55、序列分段计算，这种分段处理方法有重叠相加法和重叠保留法两种。下面只介绍重叠相加法，重叠保留法作为本章习题题21，留给读者讨论。设序列h(n)长度为N，x(n)为无限长序列。将x(n)等长分段，每段长度取M，则第85页，共171页。第3章 离散傅里叶变换(DFT) （3.4.4a）0)()(kknxnx( )( )()kMx nx n RnkM于是，h(n)与x(n)的线性卷积可表示为（3.4.4b）式中)()()(nxnhnykk000( )( )( )( )( )( )( )( )kkkkkky nh nx nh nx nh nx ny n第86页，共171页。第3章 离散傅里叶变换(DFT

56、) (3.4.4b)式说明，计算h(n)与x(n)的线性卷积时，可先计算分段线性卷积yk(n)=h(n)*xk(n)，然后把分段卷积结果叠加起来即可，如图3.4.3所示。每一分段卷积yk(n)的长度为NM1，因此相邻分段卷积yk(n)与yk1(n)有N1个点重叠，必须把重叠部分的yk(n)与yk1(n)相加，才能得到正确的卷积序列y(n)。第87页，共171页。第3章 离散傅里叶变换(DFT) 显然, 可用图3.4.1所示的快速卷积法计算分段卷积yk(n)， 其中L=NM1。由图3.4.3可以看出，当第二个分段卷积y1(n)计算完后，叠加重叠点便可得输出序列y(n)的前2M个值；同样道理，分段

57、卷积yi(n)计算完后，就可得到y(n)第i段的M个序列值。因此，这种方法不要求大的存储容量，且运算量和延时也大大减少，最大延时TDmax=2MTs+To，Ts是系统采样间隔，To是计算1个分段卷积所需时间，一般要求ToMTs。这样，就实现了边输入边计算边输出，如果计算机的运算速度快，可以实现实时处理。第88页，共171页。第3章 离散傅里叶变换(DFT) 图3.4.3 用重叠相加法计算 线性卷积时域关系示意图 第89页，共171页。第3章 离散傅里叶变换(DFT) 用DFT计算分段卷积yk(n)的方法如下：(1) i=0；L=NM1；计算并保存H(k)=DFTh(n)L; (2) 读入xk(

58、n)=x(n)RM(nkM)，构造变换区间0，L1上的序列，实际中就是将xi(n)的M个值存放在长度为M的数组中, 并计算(3) ；(4) ，n = 0,1,2,L1； ( )()( )kkMx nx nkM Rn ( )DFT ( ) ;iiLX kx n( )( )( )iiY kH k X k ( )()( )IDFT ( )ikLiLy ny nkM R nY k第90页，共171页。第3章 离散傅里叶变换(DFT) (5) 计算： (6) i =i1，返回(2)。应当说明，一般x(n)是因果序列，假设初始条件y1(n)=0。1()( ),02 ()() ( ),11 ()iiiyMn

59、y nnNy iMny nNnM 重叠区相加非重叠区不加第91页，共171页。第3章 离散傅里叶变换(DFT) MATLAB信号处理工具箱中提供了一个函数fftfilt，该函数用重叠相加法实现线性卷积的计算。调用格式为：y=fftfilt(h, x，M)。式中, h是系统单位脉冲响应向量；x是输入序列向量；y是系统的输出序列向量（h与x的卷积结果）；M是由用户选择的输入序列x的分段长度，缺省M时，默认输入序列x的分段长度M=512。【例例3.4.1】 假设h(n)=R5(n)，x(n)=cos(n/10)+cos(2n/5)u(n)，用重叠相加法计算y(n)=h(n)*x(n)，并画出h(n)

60、、x(n)和y(n)的波形。第92页，共171页。第3章 离散傅里叶变换(DFT) 解解 h(n)的长度为N=5, 对x(n)进行分段，每段长度为M=10。计算h(n)和x(n)的线性卷积的MATLAB程序如下：%例3.4.1 重叠相加法的MATLAB实现程序：ep341.m Lx=41; N=5; M=10; %Lx为信号序列x(n)长度 hn=ones(1, N); hn1=hn zeros(1, Lx-N); %产生h(n)，其后补零是为了绘图好看 n=0:L-1; xn=cos(pi*n/10)+cos(2*pi*n/5); %产生x(n)的Lx个样值 yn=fftfilt(hn, x