离散傅里叶变换（经典实用）

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 点离散傅里叶变换为 (3.1.1)1, 1 , 0)()()( 1 0 NkWnxnxDFTkX N n kn N 第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点离散傅里叶

4、逆变换。下面证明 IDFTX(k)的唯一性。 2 j e N N W 1, 1 , 0)( 1 )()( 1 0 NnWkX N kXIDFTnx N n kn N (3.1.2) 第3章 离散傅里叶变换(DFT) 把(3.1.1)式代入(3.1.2)式，有 由于 为整数 为整数 iiNnm iiNnm W N W N mx WWmx N kXIDFT N k nmk N N m N k nmk N nk N N k N m mk NN , 0 , 11 1 )( )( 1 )( 1 0 )( 1 0 1 0 )( 1 0 1 0 第3章 离散傅里叶变换(DFT) 所以，在变换区间上满足下式：

5、 IDFTX(k)N=x(n) 0nN-1 由此可见，(3.1.2)式定义的离散傅里叶逆变换是唯一的。 【例例3.1.1】 x(n)=R4(n), 求x(n)的4点和8点DFT。 解解设变换区间N=4，则 2 33 j 4 4 00 j2 2 j 4 ( )( )e 40 1 e 01,2,3 1 e kn kn nn k k X kx n W k k 第3章 离散傅里叶变换(DFT) 设变换区间N=8，则 由此例可见，x(n)的离散傅里叶变换结果与变换 区间长度N的取值有关。对DFT与Z变换和傅里叶变 换的关系及DFT的物理意义进行讨论后，上述问题 就会得到解释。 7 ,1 , 0, 8 s

6、in 2 sin )()( 8 3 7 0 3 0 8 2 8 k k k e eWnxkX kj nn knj kn 第3章 离散傅里叶变换(DFT) 3.1.2 DFT与傅里叶变换和与傅里叶变换和Z变换的关系变换的关系 设序列x(n)的长度为M，其Z变换和N(NM)点 DFT分别为 比较上面二式可得关系式 1 0 1 0 ( )ZT ( )( ) ( )DFT ( )( )0,1,1 M n n M kn NN n X zx nx n z X kx nx n WkN 1, 1 , 0,)()( 1, 1 , 0,)()( 2 2 NkeXkX NkzXkX k N j ez k N j (

7、3.1.3) 或 (3.1.4) 第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上的采样间隔和 采样点数不同，所以DFT的变换结果不同。上例中， x(n)=R4(n)，DFT变换区间长度N分别取8、16时，X(ej) 和X(k)的幅频特性曲线图如图3.1.1所示。由此容易得到 x(n)=R4(n)的4点DFT为X(k)=DF

8、Tx(n)4=4(k)，这一特 殊的结果在下面将得到进一步解释。 第3章 离散傅里叶变换(DFT) 图3.1.1 R4(n)的FT和DFT的幅度特性关系 第3章 离散傅里叶变换(DFT) kn N W 3.1.3 DFT的隐含周期性的隐含周期性 前面定义的DFT变换对中，x(n)与X(k)均为有限长 序列，但由于的周期性，使(3.1.1)和(3.1.2)式中的 X(k)隐含周期性，且周期均为N。对任意整数m，总有 所以(3.1.1)式中，X(k)满足： 实际上，任何周期为N的周期序列都可以看做 长度为N的有限长序列x(n)的周期延拓序列，而x(n)则是 的一个周期，即 () , kk mN N

9、N NWWk m 为整数, 为自然数， 11 () 00 ()( )( )( ) NN k mN nkn NN nn X kmNx n Wx n WX k )( nx )( nx 第3章 离散傅里叶变换(DFT) 上述关系如图3.1.2（a）和（b）所示。一般称周期 序列中从n=0到N1的第一个周期为的主值区 间，而主值区间上的序列称为的主值序列。因此 x(n)与的上述关系可叙述为：是x(n)的周期延拓 序列，x(n)是的主值序列。 (3.1.5) (3.1.6) ( )() m x nx nmN ( )( )( ) N x nx nRn )( nx)( nx )( nx )( nx)( nx

10、 )( 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 n 8 8, ( )( )Nx nx n 8 8 (8)(8)(0) (9)(9)(1) xxx xxx 第3章 离散傅里叶变换(DFT) 图3.1.2 x(n)及其周期延拓序列 第3章 离散傅里叶

11、变换(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，则可 写出的离散傅里叶级数表示式 N nxnx)()( (3.1.8) (3.1.9) 111 000 ( )( )( )( ) NNN knknkn NNNN nnn X kx n Wx nWx n W 11 00 11 ( )( )( ) NN knkn NN kk

12、x nX k WX k W NN 第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的第二种 物理解释（物理意义）。 ( )( )( ) N X kX k Rk (3.

13、1.10) ( )X k ( )X k )()( )(kRkXkX N ( )X k 第3章 离散傅里叶变换(DFT) 现在解释DFTR4(n)4=4(k)。根据DFT第二种物理 解释可知，DFTR4(n)4表示R4(n)以4为周期的周期延拓 序列R4(n)4的频谱特性，因为R4(n)4是一个直流序列， 只有直流成分（即零频率成分）。 第3章 离散傅里叶变换(DFT) 3.1.4 用用MATLAB计算序列的计算序列的DFT MATLAB提供了用快速傅里叶变换算法FFT(算法 见第4章介绍)计算DFT的函数fft，其调用格式如下: Xk = fft (xn, N)； 调用参数xn为被变换的时域序

14、列向量，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.1.2】 设x(n)=R4(n)，X(ej)=FTx(n)。分别计算 X(ej)在频率区间0，2上的16点和32点等间隔采样， 并绘制X(ej)采样的幅频特性图和相频特性图。 解解 由DFT与傅里叶变换的关系知道，X(ej)在频率区间 0，

15、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点DFT Xk32=fft(xn, 32); %计算xn的32点DFT %以下为绘图部分（省略，程序集中有） 程序运行结果如图3.1.3所示。 第3章 离散傅里叶变换(DFT) 图3.1.3 程序ep312.m 运行结果 第3章 离散傅里叶变换(DFT) 3.2 离散

16、傅里叶变换的基本性质离散傅里叶变换的基本性质 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点DFT。 第3章 离散傅里叶变换(DFT) 3.2.2 循环移位性质循环移位性质 1序列的循环移位序列的循环移位 设x(n)为有限长序列，长度为M，MN，则x(n)的循环 移位定义为 y(n)=x

17、(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所示。 N nxnx)()( )( nx)( mnx )( mnx 第3章 离散傅里叶变换(DFT) 显然，y(n)是长度为N的有限长序列。观察图 3.2.1可见，循环移位的实质是将x(n)左移m位，而移 出主值区(0nN-1)的序列值又依次从右侧进入主值 区。“循环移位”就是由此得名的。 由循环移位的定义可知，对同一序列x(n)和相同

18、的位移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章 离散傅里叶变换(DFT) 2 时域循环移位定理时域循环移位定理 设x(n)是长度为M(MN)的有限长序列，y(n)为x(n) 的循环移位，即 则 (3.2.3) 其中 )()()(kXWnyDFTkY km NN 10,)()(NknxDFTkX N )()()(nRmnxny NN 第3章 离散傅里叶变换(DFT) nk NNW nx ) ( 证明证明 令n+m

19、=n，则有 由于上式中求和项以N为周期，因此对其在任 一周期上的求和结果相同。将上式的求和区间改在主值 区，则得 11 00 ( )DFT ( )()( )() NN knkn NNNNNN nn Y ky nx nmRn Wx nmW 11 () ( )( )( ) NmNm k nmkmkn NNNNN nmnm Y kx nWWx nW 11 00 ( )( )( )( ) NN kmknkmknkm NNNNNN nn Y kWx nWWx n WWX k 第3章 离散傅里叶变换(DFT) 3 频域循环移位定理频域循环移位定理 如果 X(k)=DFTx(n)N 0kN-1 Y(k)=X

20、(k+l)NRN(k) 则 (3.2.4) (3.2.4)式的证明方法与时域循环移位定理类似，直接 对Y(k)=X(k+l)NRN(k)进行IDFT即得证。 ( )IDFT ( )( ) nl NN y nY kW x n 第3章 离散傅里叶变换(DFT) 3.2.3 循环卷积定理循环卷积定理 时域循环卷积定理是DFT中最重要的定理，具有很强 的实用性。已知系统输入和系统的单位脉冲响应，计算系 统的输出，以及FIR滤波器用FFT实现等，都是基于该定理 的。下面首先介绍循环卷积的概念和计算循环卷积的方法， 然后介绍循环卷积定理。 1 两个有限长序列的循环卷积两个有限长序列的循环卷积 设序列h(n

21、)和x(n)的长度分别为N和M。h(n)与x(n)的L 点循环卷积定义为 （3.2.5） 1 c 0 ( )( ) ()( ) L LL m y nh m x nmRn 第3章 离散傅里叶变换(DFT) 式中，L称为循环卷积区间长度，LmaxN，M。上式 显然与第1章介绍的线性卷积不同，为了区别线性卷积， 用 表示循环卷积，用表示L点循环卷积，即 yc(n)=h(n) x(n)。观察(3.2.5)式，x(nm)L是以L为周 期的周期信号，n和m的变化区间均是0, L-1，因此直 接计算该式比较麻烦。计算机中采用矩阵相乘或快速 傅里叶变换(FFT)的方法计算循环卷积。下面介绍用矩 阵计算循环卷积

22、的公式。 第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) , ( 1) , ( 2) , , (1) (0), (1), (2), , (1) LLLL xxxxL xx Lx Lx 第3章 离散傅里叶变换(DFT) 令n = 1, m =

23、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) , , (2) (1), (0), (1), , (2) LLLL xxxxL xxx Lx 第3章 离散傅里叶变换(DFT) （3.2.6） (0)(1)(2)(1) (1)(0)(1)

24、(2) (2)(1)(0)(3) (1)(2)(3)(0) xx Lx Lx xxx Lx xxxx x Lx Lx Lx 第3章 离散傅里叶变换(DFT) 上面矩阵称为x(n)的L点“循环卷积矩阵”，其特点是: （1） 第1行是序列x(0), x(1), , x(L1)的循环倒 相序列。注意，如果注意，如果x(n)的长度的长度ML，则需要在，则需要在x(n)末尾末尾 补补LM个零后，再形成第一行的循环倒相序列。个零后，再形成第一行的循环倒相序列。 （2） 第1行以后的各行均是前一行向右循环移1位形 成的。 （3） 矩阵的各主对角线上的序列值均相等。 有了上面介绍的循环卷积矩阵，就可以写出式(

25、3.2.5) 的矩阵形式如下: 第3章 离散傅里叶变换(DFT) （3.2.7） c c c c (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 Lxh yxxx Lxh yxxxxh y Lx Lx Lx Lxh L 第3章 离散傅里叶变换(DFT) 按照上式，可以在计算机上用矩阵相乘的方法计算两 个序列的循环卷积，这里关键是先形成循环卷积矩阵。 上式中如果如果h(n)的长度的长度NL，则需要在，则需要在h(n)末尾补末尾补L-N 个零。个零。 【例例3.2.1】 计算下面给

26、出的两个长度为4的序列 h(n)与x(n)的4点和8点循环卷积。 ( )(0), (1), (2), (3)1,2,3,4 ( )(0), (1), (2), (3)1,1,1,1 h nhhhh x nxxxx 第3章 离散傅里叶变换(DFT) 解解 按照式（3.2.21）写出h(n)与x(n)的4点循环 卷积矩阵形式为 h(n)与x(n)的8点循环卷积矩阵形式为 c c c c (0)1432110 (1)2143110 (2)3214110 (3)4321110 y y y y 第3章 离散傅里叶变换(DFT) h(n)和x(n)及其4点和8点循环卷积结果分别如图 3.2.2(a)、(b

27、)、(c)和(d)所示。请读者计算验证本例 的8点循环卷积结果等于h(n)与x(n)的线性卷积结果。 后面将证明，当循环卷积区间长度L大于等于y(n) = h(n)*x(n)的长度时，循环卷积结果就等于线性卷积。 第3章 离散傅里叶变换(DFT) 图3.2.2 序列及其循环卷积波形 第3章 离散傅里叶变换(DFT) 2. 环卷积定理环卷积定理 有限长序列x1(n)和x2(n)的长度分别为N1和N2，N= maxN1, N2， x1(n)和x2(n)的N点循环卷积为 则x(n)的N点DFT为 其中 2 ( )( )x nx n N 1 121 0 ( )( )()( ) N NN m x nx

28、m xnmRn 12 ( )DFT ( )( )( ) N X kx nX kXk（3.2.9） 1122 ( )DFT ( ) ,( )DFT( ) NN X kx nXkx n （3.2.8） 第3章 离散傅里叶变换(DFT) 证明证明 直接对(3.2.8)式两边进行DFT，则有 11 12 00 11 12 00 ( )DFT ( ) ( )()( ) ( )() N NN kn NNN nm NN kn NN mn X kx n x m xnmRn W x mxnmW 第3章 离散傅里叶变换(DFT) 令n-m=n，则有 因为上式中是以N为周期的，所以对其 在任一个周期上求和的结果不变

29、。因此 1 0 1 21 1 0 1 )( 21 )()( )()()( N m mN mn kn NN km N N m mN mn mnk NN WnxWmx WnxmxkX 2 )( kn NNW nx 第3章 离散傅里叶变换(DFT) 由于， 因此 即循环卷积亦满足交换律。 10)()( ) ()()( 21 1 0 1 0 21 NkkXkX WnxWmxkX N m N n kn N km N ， 1221 ( )DFT ( )( )( )( )( )X kx nX k XkXk X k 1 ( )IDFT( )( )x nX kx n 22 ( )( )x nx n 1( ) x

30、 n 第3章 离散傅里叶变换(DFT) 作为习题请读者证明以下频域循环卷积定理: 如果x(n)=x1(n)x2(n)，则 (3.2.10a) 1 1 ( )DFT ( )( ) N X kx nX k N 2( ) XkN 1 12 0 1 ( )()( ) N NN l X l XklRk N 第3章 离散傅里叶变换(DFT) 1 121 0 1 ( )( )()( ) N NN l X kXl XklRk N 或 (3.2.10b) 式中 相对频域循环卷积定理，称(3.2.9)式为时域循环卷积定 理。 2 1 ( )( )X kXk N N 11 22 ( )DFT ( ) 01 ( )D

31、FT( ) N N X kx n kN Xkx n 第3章 离散傅里叶变换(DFT) 3.2.4 复共轭序列的复共轭序列的DFT 设x*(n)是x(n)的复共轭序列，长度为N，X(k)=DFTx(n)N， 则 且X(N)=X(0)。 证明证明 根据DFT的唯一性，只要证明(3.2.11)式右边等于 左边即可。 * DFT( )()01 N x nXNkkN (3.2.11) 第3章 离散傅里叶变换(DFT) 又由X(k)的隐含周期性，有 X(N)=X(0) 用同样的方法可以证明 (3.2.12) 11 *()*() 00 1 * 0 ()( )( ) ( )DFT( ) NN N k nN k

32、 n NN nn N kn NN n XNkx n Wx n W x n Wx n * DFT ()( ) N x NnX k 第3章 离散傅里叶变换(DFT) 3.2.5 DFT的共轭对称性的共轭对称性 1 有限长共轭对称序列和共轭反对称序列有限长共轭对称序列和共轭反对称序列 为了区别于傅里叶变换中所定义的共轭对称 （或共轭反对称）序列，下面用xep(n)和xop(n)分别表 示有限长共轭对称序列和共轭反对称序列，则二者 满足如下关系式： (3.2.13a) (3.2.13b) * epep ( )() 01xnxNnnN * opop ( )() 01xnxNnnN 第3章 离散傅里叶变换

33、(DFT) 当N为偶数时，将上式中的n换成N/2n，可得到： 上式更清楚地说明了有限长序列共轭对称序列是关于 n=N/2点对称。容易证明，如同任何实函数都可以分解 成偶对称分量和奇对称分量一样，任何有限长序列x(n) 都可以表示成其共轭对称分量和共轭反对称分量之和， 即 * epep ()() 01 222 NNN xnxnn * epep ()() 01 222 NNN xnxnn 第3章 离散傅里叶变换(DFT) (3.2.14) 将上式中的n换成N-n，并取复共轭，再将(3.2.13a)式和 (3.2.13b)式代入，得到： (3.2.15) (3.2.14)式分别加减(3.2.15)式

34、，可得 (3.2.16a) (3.2.16b) epop ( )( )( )01x nxnxnnN * ep 1 ( ) ( )() 2 xnx nxNn * op 1 ( ) ( )() 2 xnx nxNn )()( )()()( nxnx nNxnNxnNx opep opep 第3章 离散傅里叶变换(DFT) 2 DFT的共轭对称性的共轭对称性 (1) 如果将x(n)表示为 x(n)=xr(n)+jxi(n) (3.2.17) 其中 那么，由(3.2.11)式和(3.2.16a)式可得 * r * i 1 ( )Re ( ) ( )( ) 2 1 j ( )jIm ( ) ( )( )

35、 2 x nx nx nx n x nx nx nx n 第3章 离散傅里叶变换(DFT) (3.2.18) 由(3.2.11)式和(3.2.16b)式可得 (3.2.19) * rep 11 DFT( )DFT ( )( )( )()( ) 22 x nx nx nX kXNkXk * iop 11 DFTj ( )DFT ( )( )( )()( ) 22 x nx nx nX kXNkXk 第3章 离散傅里叶变换(DFT) 由DFT的线性性质即可得 (3.2.20) 其中，Xop(k)=DFTxr(n)是X(k)的共轭对称分量， Xop(k)=DFTjxi(n)是X(k)的共轭反对称分量

36、。 (2) 如果将x(n)表示为 (3.2.21) epop ( )DFT ( )( )( )X kx nXkXk epop ( )( )( )01x nxnxnnN 第3章 离散傅里叶变换(DFT) 其中，是x(n)的共轭对称分量， 是x(n)的共轭反对称分量, 那么，由(3.2.12)式可得 * ep 1 ( ) ( )() 2 xnx nxNn * op 1 ( ) ( )() 2 xnx nxNn * ep 11 DFT( )DFT ( )()( )( )Re( ) 22 xnx nx NnX kXkX k * op 11 DFT( )DFT ( )()( )( )Im( ) 22 x

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

38、对称分量和共轭反对称分量的的共轭对称分量和共轭反对称分量的DFT分别为分别为X(k) 的实部和虚部乘以的实部和虚部乘以j。 另外，请读者根据上述共轭对称性证明有限长实序 列DFT的共轭对称性（见本章习题题7）。 设x(n)是长度为N的实序列，且X(k)=DFTx(n)N，则 X(k)满足如下对称性： 第3章 离散傅里叶变换(DFT) (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

39、)=-x(N-n)，则X(k) 纯虚奇对称，即 X(k)=-X(N-k) (3.2.25) 第3章 离散傅里叶变换(DFT) 实际中经常需要对实序列进行DFT，利用上述对称性 质，可减少DFT的运算量，提高运算效率。例如，计算实 序列的N点DFT时，当N=偶数时，只需计算X(k)的前面 N/2+1点，而N = 奇数时，只需计算X(k)的前面(N+1)/2点， 其他点按照(3.2.23)式即可求得。例如， X(N-1)=X*(1), X(N- 2)=X*(2), 这样可以减少近一半运算量。 【例例3.2.2】 利用DFT的共轭对称性，设计一种高效 算法，通过计算一个N点DFT，就可以计算出两个实

40、序列 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)和x2(n)的N点DFT： epop ( )DFT ( )( )( )X kx nXkXk * ep1 1 ( )DFT( )( )() 2 Xkx nX kXNk * op2 1 ( )DFTj( )( )() 2 Xkx nX kXNk )()( 2 1 )()( * 11 kNXkXnxDFTkX * 22 1 ( )DFT

41、( )j ( )() 2 Xkx nX kXNk 第3章 离散傅里叶变换(DFT) 3.3 频频 率率 域域 采采 样样 时域采样定理告诉我们，在一定条件下，可以由 时域离散采样信号恢复原来的连续信号。那么能不能 也由频域离散采样恢复原来的信号（或原连续频率函 数）？其条件是什么？内插公式又是什么形式？本节 就上述问题进行讨论。 设任意序列x(n)的Z变换为 且X(z)的收敛域包含单位圆(即x(n)存在傅里叶变换)。 在单位圆上对X(z)等间隔采样N点, 得到： n n znxzX)()( 第3章 离散傅里叶变换(DFT) 显然，(3.3.1)式表示在区间0, 2上对x(n)的傅里叶变换 X(

42、ej)的N点等间隔采样。将X(k)看做长度为N的有限长序 列xN(n)的DFT，即 下面推导序列xN(n)与原序列x(n)之间的关系，并导出频域 采样定理。 ( )IDFT ( )01 N x nX knN ， 10)()()()( 2 2 NkWnxenxzXkX kn N n kn N j n ez k N j (3.3.1) 第3章 离散傅里叶变换(DFT) 由DFT与DFS的关系可知，X(k)是xN(n)以N为周期的周 期延拓序列的离散傅里叶级数系数的主值序 列，即 ( )x n)( kX 1 0 1 0 ( )( )DFS ( ) ( )( )( ) ( )( )IDFS( ) 1

43、( ) 1 ( ) N N NN N kn N k N kn N k X kXkx n X kX k Rk x nxnX k X k W N X k W N 第3章 离散傅里叶变换(DFT) 将 (3.3.1) 式代入上式得 式中 1 () 0 11 0 N k m n N k mniNi W Nm ， 为整数 ，其他 m N k nmk N N km kn N km N W N mx WWmx N nx 1 0 )( 1 0 1 )( )( 1 )( 第3章 离散傅里叶变换(DFT) 因此 所以 ( )() i x nx niN ( )( )( )()( ) NNN i xnx n Rnx

44、n iN Rn (3.3.3) (3.3.2) 第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)，否则产生时域混 叠现象。 第3章 离散傅里叶变换(DFT) 满足频域采样定理时，频域采样序列X(k)的N点IDFT 是原序列x(n)，所以必然可以由X(k)恢复X(z)和X(ej)。下 面推导用频域采样

45、X(k)表示X(z)和X(ej)的内插公式和内 插函数。设序列x(n)长度为M，在频域0, 2上等间隔 采样N点，NM，则有 1, 2, 1, 0)()( )()( 2 j e 1 0 NkzXkX znxzX k N z N n n 第3章 离散傅里叶变换(DFT) 因为满足频域采样定理，所以式中 将上式代入X(z)的表示式中，得到: (3.3.4a) 1111 0000 1 1 0 11 ( )( )( ) 11 ( ) 1 NNNN knnknn NN nkkn kNN N N k n n X zX k WzX kWz NN Wz X k NWz 1 0 )( 1 )()( N k nk

46、 N WkX N kXIDFTnx 第3章 离散傅里叶变换(DFT) 1 kN N W式中，因此 (3.3.4b) 令 (3.3.5) 则 (3.3.6) 1 0 1 1 1 )( 1 )( N k k N N zW z kX N zX 1 1 11 )( zW z N z k N N k 1 0 )()()( N k k zkXzX 第3章 离散傅里叶变换(DFT) 式(3.3.6)称为用X(k)表示X(z)的内插公式，k(z)称为内插 函数。将z=ej代入(3.3.4a)式，并进行化简，可得 (3.3.7) (3.3.8) 在数字滤波器的结构与设计中，我们将会看到，频 域采样理论及有关公式

47、可提供一种有用的滤波器结构和 滤波器设计途径，(3.3.7)式有助于分析FIR滤波器频率采 样设计法的逼近性能。 1 0 j ) 2 ()()e ( N k k N kXX ) 2 1 (j e )2/sin( )2/sin(1 )( N N N 第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点采

48、样X16(k)。最后分别对X16(k)和X32(k)求IDFT, 得到： 绘制x16(n)和x32(n)波形图验证频域采样理论。 161616 ( )IDFT( )xnXk 323232 ( )IDFT( )xnXk 第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=

49、fft(xn, 32); %32点FFTx(n) x32n=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) 以下绘图部分省略。 第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(e

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

51、 L 1 0 ( )( ) ()( ) L LL m x nh m x nmR n 10 )()( )()( Lk nxDFTkX nhDFTkH L L 第3章 离散傅里叶变换(DFT) 则由DFT的时域循环卷积定理有 由此可见，循环卷积既可以在时域直接计算，也可以 按照图3.4.1所示的计算框图在频域计算。由于DFT有 快速算法，当L很大时，在频域计算循环卷积的速度快 得多，因而常用DFT(FFT)计算循环卷积。 cc ( )DFT( )( )( )01 L Y ky nH k X kkL 第3章 离散傅里叶变换(DFT) 图3.4.1 用DFT计算循环卷积的原理框图 第3章 离散傅里叶变

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

53、( )( ) ()( ) L LL m x nh m x nmRn (3.4.1) (3.4.2)L L max, ( )() i LN Mx nx niL 第3章 离散傅里叶变换(DFT) 对照(3.4.1)式可以看出，上式中 即 (3.4.3) 1 c 0 1 0 ( )( )() ( ) ()( ) N L mi N L im y nh mx nmiL R h m x niLm R n )()()( l 1 0 iLnymiLnxmh N m i L nRiLnyny)()()( lc 第3章 离散傅里叶变换(DFT) (3.4.3)式说明，yc(n)等于yl(n)以L为周期的周期延拓序

54、列 的主值序列。我们知道，yl(n)长度为NM1，因此 只有当循环卷积长度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)相同。 第3章 离散傅里叶变换(DFT) 图3.4.2 线性卷积与循环卷积波形图 第3章 离散傅里叶变换(DFT) 综上

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

56、述方法是不行的。 解决这个问题的方法是将长序列分段计算，这种分段处 理方法有重叠相加法和重叠保留法两种。下面只介绍重 叠相加法，重叠保留法作为本章习题题21，留给读者讨 论。 设序列h(n)长度为N，x(n)为无限长序列。将x(n)等长 分段，每段长度取M，则 第3章 离散傅里叶变换(DFT) （3.4.4a） 0 )()( k k nxnx( )( )() kM x nx n RnkM 于是，h(n)与x(n)的线性卷积可表示为 （3.4.4b） 式中 )()()(nxnhny kk 000 ( )( )( )( )( )( )( )( ) kkk kkk y nh nx nh nx nh

57、nx ny n 第3章 离散傅里叶变换(DFT) (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)。 第3章 离散傅里叶变换(DFT) 显然, 可用图3.4.1所示的快速卷积法计算分段卷积 yk(n)， 其中L=NM1。由图3.4.3可以看出，当第二 个分段卷积y1(n)计算完后，叠加重叠点便可得输出

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

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

60、 () ( ), 11 () ii i yMny nnN y iMn y nNnM 重叠区相加 非重叠区不加 第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)，用重叠相加法计