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

1、3.3 3.3 频率域采样频率域采样 设任意序列设任意序列x(n)的的Z变换为：变换为：( )( )nnX zx n z 且且X(z)收敛域包含单位圆收敛域包含单位圆(即即x(n)存在傅里叶变换存在傅里叶变换)。22( )( )( ),0kN-1(3.3.1)jkNjknNz enX kX zx n e 上式表示在区间上式表示在区间0, 2上对上对x(n)的傅里叶变换的傅里叶变换X(ej)的的N点等间隔采样。点等间隔采样。在单位圆上对在单位圆上对X(z)等间隔采样等间隔采样N点得到点得到1 1. .由频域采样恢复序列由频域采样恢复序列第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DF

2、T) 由由DFT与与DFS的关系可知，的关系可知，X(k)是是xN(n)以以N为周期的周为周期的周期延拓序列的离散傅里叶级数系数的主值序期延拓序列的离散傅里叶级数系数的主值序列，即列，即( )x n)(kX)()(?nxnxN 将将X(k)看做长度为看做长度为N的有限长序列的有限长序列xN(n)的的DFT ,即即 xN(n)=IDFTX(k)， 0nN-1第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)101( )NknNkX k WN( )( )IDFS( )NNx nxnX k( )( )( )NX kX k Rk( )( )DFS ( )NX kXkx n101( )Nk

3、nNkX k WN 10)()1(NkknmNWN1 , m=n+iN0 , 其他其他m mNkknmNWNmx10)(1)( m)()(mkNWmxkX 10)(1NknkNmmkNWWmxN第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)l频域采样定理：频域采样定理：l 如果如果x(n)的长度为的长度为M， 则只有当频域采样点数则只有当频域采样点数NM时，时， 才有才有l xN(n)=IDFTX(k)=x(n)l即可由频域采样即可由频域采样X(k)恢复原序列恢复原序列x(n)，否则产生，否则产生时域混叠现象时域混叠现象。()()()()()()()iNNNixnxniNxn

4、xnRnxniNRn (3.3.2) (3.3.3)说明：X(z)在单位圆上的在单位圆上的N点等间隔采样点等间隔采样X(k)的的N点点IDFT是原序是原序列列x(n)以以N为周期的周期延拓序列的主值序列。为周期的周期延拓序列的主值序列。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)满足频域采样定理时，频域采样序列满足频域采样定理时，频域采样序列X(k)的的N点点IDFT是原序是原序列列x(n)，所以必然可以由，所以必然可以由X(k)恢复恢复X(z)和和X(ej)。101( )( )( )NknNkx nIDFT X kX k WN10( )( )NnnX zx n z因为满足

5、频域采样定理，所以因为满足频域采样定理，所以)(jeX2 2. .由由X(k)表达表达 X(z)X(z)与与 的问题的问题下面推导下面推导用频域采样用频域采样X(k)表示如何表示表示如何表示X(z)， 设序列设序列x(n)长度为长度为M， 在频域在频域02之间等间隔采样之间等间隔采样N点，点， NM， 则则有有 ：2( )( ),0,1,2,1jkNz eX kX zkN第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 将上式代入将上式代入X(z)的表示式中得的表示式中得11001( )NNknnNknX kWzN11001( )( )NNknnNnkX zX k WzN110

6、11( )1kNNNNkkNWzX kNWz 101111)()(NkkNNzWzNkXzX 10)()()(NkkzkXzX 1 kNNW内插函数内插函数:)(zk 内插公式内插公式第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 当z=ej时， 带入上式， 即10(2/)()( )( )11( )1Njkkj Nkjk NX eX keNe 进一步化简可得进一步化简可得 101()22()( ) ()1 sin(/2)( )sin(/2)NjkNjX eX kkNNeN (3.3.7) (3.3.8)频域内插公式频域内插公式频域内插函数频域内插函数第第3 3章章 离散傅里叶

7、变换离散傅里叶变换(DFT)(DFT)l解解 解题思想：解题思想： 先计算先计算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)波形图验证频域采样理论。波形图验证频域采样理论。161616( )IDFT( )xnXk323232( )IDFT( )xnXk【

8、MATLAB例例】 长度为26的三角形序列x(n)如图 (a)所示。编写MATLAB程序验证频域采样理论。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)MATLAB求解程序ep331.m如下：% 频域采样理论验证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=X32k(1:

9、2:N); %隔点抽取X32k得到X16(k)x16n=ifft(X16k, N/2); %16点IFFTX16(k)得到x16(n)以下绘图部分省略。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)本例中本例中x(n)的长度的长度M=26。从图中可以看出，当采样点数。从图中可以看出，当采样点数N=16M时，无时域混叠失真时，无时域混叠失真，x32(n)=IDFTX32(k)=x(n)。3.4 DFT3.4 DFT的应用举例的应用举例 DFT的快速算法的快速算法FFT的出现，的出现， 使使DFT在数在数字通信、字通信、 语言信号处理、语言信号处理、 图像处理、图像处理、 功率谱

10、功率谱估计、估计、 仿真、仿真、 系统分析、系统分析、 雷达理论、雷达理论、 光学、光学、 医学、医学、 地震以及数值分析等各个领域都得到广地震以及数值分析等各个领域都得到广泛应用。泛应用。 第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 3.4.1 用用DFT计算线性卷积计算线性卷积 1122( )( )( )( )X kDFT x nXkDFT x n0kL-1则由时域循环卷积定理有则由时域循环卷积定理有: Y(k)=DFTy(n)=X1(k)X2(k), 0kL-1112120( )( )( )( )()( )LLLmy nx nx nx m xnmR n如果如果1.D

11、FT1.DFT计算循环卷积计算循环卷积第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 由此可见，由此可见， 循环卷积既可在时域直接计算，循环卷积既可在时域直接计算， 也可也可以在频域计算。以在频域计算。 由于由于DFT有快速算法有快速算法FFT， 当当N很大很大时，时， 在频域计算的速度快得多，在频域计算的速度快得多， 因而常用因而常用DFT(FFT)计算循环卷积计算循环卷积, 其计算框图如图其计算框图如图3.4.1所示。所示。图 3.4.1 用DFT计算循环卷积 h(n) DFT DFTx(n)IDFTy(n)第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)

12、 在实际应用中，在实际应用中， 经常需要计算两个序列的线性卷积，经常需要计算两个序列的线性卷积， 与计算循环卷积一样，与计算循环卷积一样， 为了提高运算速度，为了提高运算速度， 也希望用也希望用DFT(FFT)计算线性卷积。计算线性卷积。 而而DFT只能直接用来计算循环只能直接用来计算循环卷积卷积， 为此为此导出线卷积和循环卷积之间的关系以及循环卷导出线卷积和循环卷积之间的关系以及循环卷积与线性卷积相等的条件积与线性卷积相等的条件。 2.2.循环卷积代替线性卷积的条件循环卷积代替线性卷积的条件 假设假设h(n)和和x(n)都是有限长序列，都是有限长序列， 长度分别是长度分别是N和和M。 它们的

13、线性卷积和循环卷积分别表示如下：它们的线性卷积和循环卷积分别表示如下： 第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)其中，其中， LmaxN, M 1010( )()()( )() ()( ) NcLmqNLqmynh mx nmqL Rnh m x nmqL Rn( )(),Lqx nx nqL( )()( )clLqy ny nqL Rn(3.4.3) (3.4.1) 10( )( )( )( ) ()Nlmy nh nx nh m x nm(3.4.2) 10( )( )( )( ) ()( )LcLLmy nh nx nh m x nmR n()ly n qL第第3

14、 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)l因线性卷积取值长度为因线性卷积取值长度为NM-1，循环卷积计算循环卷积计算线性卷积的条件：线性卷积的条件：l LNM-1l 则可按照如图则可按照如图3.4.1所示的计算框图用所示的计算框图用DFT(FFT)计算线性卷积。其中计算线性卷积。其中DFT和和IDFT通常用快速算法通常用快速算法(FFT)来实现，故常称其为快速卷积。来实现，故常称其为快速卷积。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)图 3.4.2 线性卷积与循环卷积 0123451234h(n) x(n)nL 60123451234nL 867h(n)

15、 x(n)0123451234nL 1067h(n) x(n)（ d ）（ e ）( f )0123451234nN M1 867h(n) x(n)*nM 5012341x(n)nN 401231h(n)（ a ）（ b ）（ c ）89* * 189 10图 3.4.3 用DFT计算线性卷积框图 补L N个零点L点DFT补L M个零点L点DFTL点IDFTy(n)h(n)x(n)第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)实际上，经常遇到两个序列的长度相差很大的情况，实际上，经常遇到两个序列的长度相差很大的情况，例如例如MN。若仍选取。若仍选取LNM1，以，以L为循环卷积

16、区间，为循环卷积区间，并用上述方法计算线性卷积，则要求并用上述方法计算线性卷积，则要求对短序列补很多零对短序列补很多零点，而且长序列必须全部输入后才能进行快速计算。因点，而且长序列必须全部输入后才能进行快速计算。因此要求存储容量大，运算时间长，并使处理延时很大，此要求存储容量大，运算时间长，并使处理延时很大，不能实现实时处理不能实现实时处理。3. 3. 重叠相加法重叠相加法、重叠保留法重叠保留法况且在某些应用场合，序列长度不定或者认为是无况且在某些应用场合，序列长度不定或者认为是无限长，如电话系统中的语音信号和地震检测信号等。显限长，如电话系统中的语音信号和地震检测信号等。显然，在要求实时处理

17、时，直接套用上述方法是不行的。然，在要求实时处理时，直接套用上述方法是不行的。解决这个问题的方法是将长序列分段计算，这种分段处解决这个问题的方法是将长序列分段计算，这种分段处理方法有重叠相加法和重叠保留法两种理方法有重叠相加法和重叠保留法两种。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 设序列设序列h(n)长度为长度为N， x(n)为无限长序列为无限长序列.将将x(n)均均匀分段，匀分段， 每段长度取每段长度取M， 则则00( )( )( )( )kkkkh nx nh nx n0( )( )( )( )()kikMx nx nx nx nRnkM于是，于是， h(n)与

18、与x(n)的线性卷积可表示为的线性卷积可表示为( )( )( )y nh nx n)()()(nxnhnykk0( )( )kkh nx n(3.4.4) 0()()kky nyn1)1) 重叠相加法重叠相加法第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 说明计算说明计算h(n)h(n)与与x(n)x(n)的线性卷积时：的线性卷积时：l1 1）可先计算分段线性卷积）可先计算分段线性卷积y yk k(n)=h(n)(n)=h(n)* *x xk k(n)(n)。l2 2）把分段卷积结果叠加起来。）把分段卷积结果叠加起来。每一分段卷积每一分段卷积y yk k(n)(n)的长度为

19、的长度为N NM M1 1，因此相邻分段卷积，因此相邻分段卷积y yk k(n)(n)与与y yk k1 1(n)(n)有有N N1 1个点重叠，必须把重叠部分的个点重叠，必须把重叠部分的y yk k(n)(n)与与y yk k1 1(n)(n)相加，才能得到正确的卷积序列相加，才能得到正确的卷积序列y(n)y(n)。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)图 3.4.4 重叠相加法卷积示意图 M0NMMx1(n)x0(n)x2(n)N M 1N M 1y0(n)y1(n)N M 1y2(n)2MM3M N 10N 1y(n) y0(n) y1(n) y2(n) nnn

20、nnnh(n) 这种方法不要求大的这种方法不要求大的存储容量，且运算量和存储容量，且运算量和延时大大减少，最大延延时大大减少，最大延时时TDmax=2MTs+To，Ts是是系统采样间隔，系统采样间隔，To是计是计算算1个分段卷积所需时间，个分段卷积所需时间，一般要求一般要求ToMTs。这样，。这样，可边输入边计算边输出，可边输入边计算边输出，可以实现实时处理。可以实现实时处理。用用DFT计算分段卷积计算分段卷积yk(n)的方法步骤的方法步骤：(4)( )()( )IDFT ( )ikLiLy ny nkM R nY k(1) i=0；L=NM1；计算并保存；计算并保存H(k)=DFTh(n)L

21、 (3) ( )( )( )iiY kH k X k，n = 0,1,2,L1； ( )DFT ( ) ;iiLX kx n ( )()( )kkMx nx nkM Rn(2) 读入读入xk(n)=x(n)RM(nkM)，构造变换区间，构造变换区间0，L1上上 的序列，实际中就是将的序列，实际中就是将xi(n)的的M个值个值存放在长度为存放在长度为M的数组中的数组中, 并计算并计算102511()( ), ( ) () ( ), iiiyMny nnNy iMny nNnM 重叠区相加重叠区相加非重叠区不加非重叠区不加(6) i =i1，返回，返回(2)。说明，一般说明，一般x(n)是因果序列

22、，假设初始条件是因果序列，假设初始条件y1(n)=0。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)【例例】 假设假设h(n)=R5(n)，x(n)=cos(n/10) +cos(2n/5)u(n)，用重，用重叠相加法计算叠相加法计算y(n)=h(n)*x(n)，并画出，并画出h(n)、x(n)和和y(n)的波形。的波形。MATLAB中重叠相加法实现线性卷积的计算的函数中重叠相加法实现线性卷积的计算的函数l y=fftfilt(h, x，M)l 式中式中, h是系统单位脉冲响应向量；是系统单位脉冲响应向量；x是输入序列向量；是输入序列向量；y是是系统的输出序列向量（系统的输出

23、序列向量（h与与x的卷积结果）；的卷积结果）；M是由用户选择的输是由用户选择的输入序列入序列x的分段长度，缺省的分段长度，缺省M时，默认输入序列时，默认输入序列x的分段长度的分段长度M=512。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)解：解： h(n)的长度为的长度为N=5, 对对x(n)进行分段，每段长度为进行分段，每段长度为M=10。计算。计算h(n)和和x(n)的线性卷积的的线性卷积的MATLAB程序如下：程序如下：%例重叠相加法的例重叠相加法的MATLAB实现程序实现程序 Lx=41; N=5; M=10; %Lx为信号序列为信号序列x(n)长度长度 hn=on

24、es(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, xn, M); %调用调用fftfilt用重叠相加法计算卷积用重叠相加法计算卷积 %= %以下为绘图部分以下为绘图部分, 省略省略运行程序画出h(n)、x(n)和y(n)的波形如图所示。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)图3.4.4 MATLAB求解程序运行结果051015202530

25、35404500.51h(n)051015202530354045-202x(n)n051015202530354045-505ny(n)第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)051015202530354045-505y2(n)051015202530354045-505y3(n)051015202530354045-505y0+y1+y2+y305101520253035404500.51h(n)051015202530354045-202x(n)051015202530354045-202x0(n)051015202530354045-202x1(n)05101

26、5202530354045-202x2(n)051015202530354045-202x3(n)051015202530354045-505y0(n)051015202530354045-505y1(n)重叠相加法时域波形重叠相加法时域波形 此方法与上述方法稍有不同。先将此方法与上述方法稍有不同。先将x(n)分段，每段分段，每段N个点，个点，这是相同的。这是相同的。 不同之处是，序列中补零处不补零，而在每一段不同之处是，序列中补零处不补零，而在每一段的前边补上前一段保留下来的（的前边补上前一段保留下来的（M-1）个输入序列值，）个输入序列值， 组成组成N+M-1点序列点序列xi(n)，如图（

27、，如图（a）所示。如果）所示。如果N+M-12m， 则可在则可在每段序列末端补零值点，补到长度为每段序列末端补零值点，补到长度为2m，这时如果用，这时如果用DFT实实现现h(n)和和xi(n)循环卷积，则其每段循环卷积结果的前（循环卷积，则其每段循环卷积结果的前（M-1）个）个点的值不等于线性卷积值，必须舍去。点的值不等于线性卷积值，必须舍去。 1) 重叠保留法重叠保留法第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)图图3.4.5重叠保留法示意图重叠保留法示意图 nN1M2N1LM2L0 x0(n)x1(n)0nx2(n)N1nLM20(a)第第3 3章章 离散傅里叶变换离散

28、傅里叶变换(DFT)(DFT)图3.4.6重叠保留法示意图 y0(n)0M2M1N1ny1(n)0M1M2N1y2(n)M2M1N1nn(b)第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)3.4.2 用用DFT对信号进行谱分析对信号进行谱分析 工程实际中，经常遇到连续信号工程实际中，经常遇到连续信号xa(t)，其频谱函数，其频谱函数Xa(j)也是连续函数。为了利用也是连续函数。为了利用DFT对对xa(t)进行频谱分进行频谱分析，析，先对先对xa(t)进行时域采样，得到进行时域采样，得到x(n)=xa(nT)，再对，再对x(n)进行进行DFT，得到的，得到的X(k)则是则是x(

29、n)的傅里叶变换的傅里叶变换X(ej)在频在频率区间率区间0，2上的上的N点等间隔采样点等间隔采样。这里。这里x(n)和和X(k)均为有限长序列。均为有限长序列。 1 用用DFT对连续信号进行谱分析对连续信号进行谱分析第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)1 1）方法）方法 然而，若信号持续时间有限长，则其频谱无限宽；然而，若信号持续时间有限长，则其频谱无限宽；若信号的频谱有限宽，则其持续时间必然为无限长。若信号的频谱有限宽，则其持续时间必然为无限长。所以严格地讲，持续时间有限的带限信号是不存在的。所以严格地讲，持续时间有限的带限信号是不存在的。因此，按采样定理采样时

30、，上述两种情况下的采样序因此，按采样定理采样时，上述两种情况下的采样序列列x(n)=xa(nT)均应为无限长，不满足均应为无限长，不满足DFT的变换条件。的变换条件。实际上对频谱很宽的信号，实际上对频谱很宽的信号，为防止时域采样后产生频为防止时域采样后产生频谱混叠失真，可用预滤波器滤除幅度较小的高频成分，谱混叠失真，可用预滤波器滤除幅度较小的高频成分，使连续信号的带宽小于折叠频率使连续信号的带宽小于折叠频率。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)对于持续时间很长的信号，采样点数太多对于持续时间很长的信号，采样点数太多, 以致无法以致无法存储和计算，只好截取有限点进行存

31、储和计算，只好截取有限点进行DFT。由上述可见，。由上述可见，用用DFT对连续信号进行频谱分析必然是近似的，其近似对连续信号进行频谱分析必然是近似的，其近似程度与信号带宽、采样频率和截取长度有关。程度与信号带宽、采样频率和截取长度有关。实际上从实际上从工程角度看，滤除幅度很小的高频成分和截去幅度很小工程角度看，滤除幅度很小的高频成分和截去幅度很小的部分时间信号是允许的的部分时间信号是允许的。因此，在下面分析中，假设因此，在下面分析中，假设xa(t)是经过预滤波和截取处理的有限长是经过预滤波和截取处理的有限长带限信号带限信号。第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT) 设连续信号设连续信号xa(t)持续时间持续时间Tp， 最高频率为最高频率为fc， 对对xa(t)进行时域采样进行时域采样得 x(n) Xa(nT)， x(n)长度N为：第第3 3章章 离散傅里叶变换离散傅里叶变换(DFT)(DFT)2 2