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

1、第三章第三章离散傅里叶变换（离散傅里叶变换（DFT）学习目标学习目标 掌握离散傅里叶变换的定义及性质掌握离散傅里叶变换的定义及性质 了解频率域采样理论了解频率域采样理论 了解了解DFT的应用的应用 离散傅里叶变换离散傅里叶变换 Discrete Fourier Transform 是研究是研究有限长序列有限长序列的一种重要工具的一种重要工具 重要作用：使数字信号处理可以在重要作用：使数字信号处理可以在频域频域采用采用数数字运算字运算的方法进行的方法进行 多种快速算法多种快速算法(FFT)3.1 DFT的定义的定义3.1.1 DFT的定义的定义 设设x(n)是一个长度为是一个长度为M的有限长序列

2、，的有限长序列， 则定义则定义x(n)的的N点点DFT为为X(k)的的IDFT为为1, 1 , 0,)()()(10N kWnxnxDFTkXNnknN1, 1 , 0,)(1)()(10N nWkXNkXIDFTnxNkknN变换区间长度为其中，DFTNeWNjN,27 , 0,)8sin()2sin()()(11)()(, 8DFT84)(),()(8388822244470827084 kkke eeeeeeee eWnxk XNnx nRn xkjkjkjkjkjkjkjkjkjnknjnkn解：点点和的求例注：注：x(x)的离散傅里叶变换结果与变换区间长度的离散傅里叶变换结果与变换区

3、间长度N的取值有关。的取值有关。3.1.2 DFT和和Z变换的关系变换的关系 设序列设序列x(n)的长度为的长度为N，其，其Z变换和变换和DFT分别为：分别为：1010( ) ( )( )( ) ( )( )0kN-1NnnNknNnX zZT x nx n zX kDFT x nx n W1.,1 , 0| )()(1,.,1 , 0| )()(22N keXkXN kzXkXkNjezkNj DFT的的物理性质物理性质： 序列序列x(n)的的N点点DFT是是x(n)的的z变换在变换在单单位圆位圆上的上的N点等间隔点等间隔采样。采样。 序列序列x(n)的的N点点DFT是是x(n)的的Four

4、ier变变换在区间换在区间0，2的的N点等间隔采样。点等间隔采样。图3.1.1 R4(n)的FT和DFT的幅度特性关系 Fourier变换的几种可能形式：变换的几种可能形式： 时间函数时间函数 频率函数频率函数 Fourier形式形式1.连续时间、连续频率连续时间、连续频率 傅里叶变换傅里叶变换(FT)2.连续时间、离散频率连续时间、离散频率 傅里叶级数傅里叶级数(DFS)3.离散时间、连续频率离散时间、连续频率 序列傅里叶变换序列傅里叶变换(DTFT)4.离散时间、离散频率离散时间、离散频率 离散傅里叶变换离散傅里叶变换(DFT)1 1、连续时间、连续频率、连续时间、连续频率傅里叶变换傅里叶

5、变换 时域时域连续连续造成频域造成频域是非周期是非周期的谱的谱 时域的时域的非周期非周期造成频域是造成频域是连连续续的谱密度函数。的谱密度函数。dejXtxdtetxjXtjtj)(21)()()(2、连续时间、离散频、连续时间、离散频率率傅里叶级数傅里叶级数 时域时域连续连续函数造成频域函数造成频域是是非周期非周期的谱的谱 频域的频域的离散离散对应时域的对应时域的周期周期函数函数ktjkTTtjkejkXtxdtetxTjkX0000)()()(1)(02/2/003、离散时间、连续频率、离散时间、连续频率序列的傅里叶变换序列的傅里叶变换 时域的时域的离散离散化造成频域的化造成频域的周期周期

6、延拓延拓 时域的时域的非周期非周期对应于频域对应于频域的的连续连续deeXtxenxeXnjjnnjj)(21)()()(4、离散时间、离散频、离散时间、离散频率率离散傅里叶离散傅里叶变换变换 一个域的一个域的离散离散造成造成另一个域的另一个域的周期周期延延拓拓102102)(1)()()(NnnkNjNnnkNjekXNnxenxkX四种傅里叶变换形式归纳四种傅里叶变换形式归纳3.1.3 DFT的隐含周期性的隐含周期性 因因WknN的周期性，使的周期性，使X(k)隐含周期性，且周期均隐含周期性，且周期均为为N。 对任意整数对任意整数m， 总有总有(),kk mNNNWWk m N均为整数 1

7、()010()( )( )( )Nk mN nNnNknNnX kmNx n Wx n WX k同理可证同理可证 x(n+mN)=x(n)为周期延拓序列以表示为周期延拓序列以表示的主值区间是的周期延拓是的关系和则的序列表示为周期为NkX kXkXNnx nxnxnxn xnRnxnxnxnx mNnxnxnxnx nxNNNNm)(,)()()(,)()()()(),()()()()(, )()(:)()(),( 周期周期序列的序列的离散傅里叶级数离散傅里叶级数( (DFSDFS) )的正反变的正反变换：换： 有限长序列有限长序列 的的DFT DFT ，正好是周期，正好是周期延拓序列延拓序列

8、的离散傅里叶级数系数的离散傅里叶级数系数 的主值序列。的主值序列。)()()(,)(1)(1)()()()()()()()(10101010kRkXkXWkXNWkXNnxnRnxnxWnxWnxnxDFSkXNNkknNNkknNNnkNNnnkNNnN，)(nx)(kXNnx)()(kX 用用Matlab计算序列的计算序列的DFT 调用函数：调用函数：Xk=fft(xn,N) 例子例子3.1.23.2 DFT的基本性质的基本性质1、线性性质、线性性质 若若x1(n)和和x2(n)是两个有限长序列，长度分别为是两个有限长序列，长度分别为N1和和N2。 y(n)=ax1(n)+bx2(n) 式

9、中式中a、 b为常数，为常数， 即即NmaxN1, N2，则则y(n)的的N点点DFT为为 Y(k)=DFTy(n)=aX1(k)+bX2(k), 0kN-1 其中其中X1(k)和和X2(k)分别为分别为x1(n)和和x2(n)的的N点点DFT。 2、循环移位性质、循环移位性质1)、序列的循环移位、序列的循环移位 设设x(n)为有限长序列，为有限长序列，长度为长度为N，则，则x(n)的循的循环移位定义为环移位定义为 )()()(nRmnxnyNN2)、时域循环移位定理、时域循环移位定理 设设x(n) 是长度为是长度为N的有限长序列，的有限长序列，y(n)为为x(n)的循的循环移位，环移位， 即

10、即 则则 证明：证明：)()()()()(10),()(),()()()()()(10)(110kXWWixW Wixm n iWmnxmnxDFSNk nxDFTkXkXWnyDFTkYnRmnxnymkNkiNNimkNmikNmNminkNNnkmNNN令其中3)、频域循环移位定理、频域循环移位定理)()()()()()()()(10)()(nxWDFTlk X nxWkYIDFTn ykRlkXk YNk nxDFTk XnlNnlNNN或则若3、循环卷积定理、循环卷积定理1012102121221121212121)()()()()()()()()()()()()()()()()()

11、()(,max,),()(NmNNNmNNnRmnxmxkXIDFTn xnRmnxmxkXIDFTn xkXkXk XnxDFTk XnxDFTk XDFTNnxnxNNNNNnxnx或则如果分别为：点的和长度分别为和有限长序列1) 1)、时域循环卷积定理、时域循环卷积定理 结论：结论： 循环卷积过程中，要求对循环卷积过程中，要求对x2(m)循环循环反转，反转，循循环环移位移位 两个两个N长的序列的循环卷积长度仍为长的序列的循环卷积长度仍为N。 显然与一般的线性卷积不同，显然与一般的线性卷积不同， 故称之为故称之为循环循环卷积卷积， 记为记为1221( )( )( )( )( )( )x n

12、IDFT X kx nx nx nx n2)、频域循环卷积定理、频域循环卷积定理10,)()()()() )()()(1)()(1)()()()()(1)()(1)()()()()(221110121210212121Nk nxDFTkX nxDFTk X kRlkXlXN kXkXNnxDFTk XkRlkXlXN kXkXNnxDFTk Xnxnxn xNlNNNlNN式中或则如果50211021215241)()()()()()()(6),() 1()(),()(mNmmnxmx mnxmxny nxnxnRnnxnRnx解：卷积和。求两个周期序列的循环，和周期延拓成周期序列将序列以周期

13、为分别例：已知序列4、复共轭序列的、复共轭序列的DFT)()()0()()(10),()()()()()(*kXnNx DFTXN XkX Nk kNXnx DFTnxDFTk XNnxnx同理：的隐含周期性由于且则的复共轭序列，长度为是设5、DFT 的共轭对称性的共轭对称性1)、有限长共轭对称序列和共轭反对称序列、有限长共轭对称序列和共轭反对称序列有限长共轭对称序列：有限长共轭对称序列：有限长共轭反对称序列：有限长共轭反对称序列：10),()(10),()(*Nn nNxnxNn nNxnxopopepep120),2()2(120),2()2(*Nn nNxnNxNn nNxnNxopop

14、epep5、DFT的共轭对称性的共轭对称性序列的序列的Fourier变换的对称性质中提到：变换的对称性质中提到：)()(21)()()()(21)()()()()(*nxnxnxn xnxnxnxn xnxnxn xooeeoe其中：分量之和：对称分量和共轭反对称任意序列可表示成共轭)()(21)()()()(21)()(10),()()(*nNxnxnNxn xnNxnxnNxn xNn nxnxn xopopepepopep同理：2)、DFT的共轭对称性的共轭对称性)()()()()()()()()()(21)(Im)()()(21)(Re)()()()(1*kXkXnxDFTk XkXn

15、jx DFTkXnx DFTnxnxnxjn jxnxnxnxn xnjxnxn xopepopiepririr则其中）如果（2)、DFT的共轭对称性的共轭对称性)()()()()(Im)()(Re)()()(21)()()(21)(10),()()(2*kjXkXnxDFTk XkXjnx DFTkXnx DFTnNxnxn xnNxnxn xNn nxnxn xIRopepopepopep则其中）如果（ DFT的共轭对称性：的共轭对称性： 实数序列实数序列DFT的共轭对称性：的共轭对称性： 纯虚序列纯虚序列DFT的共轭对称性：的共轭对称性：设设 x ( n ) 是 长 度 为是 长 度 为

16、 N 的 实 序 列 ， 且的 实 序 列 ， 且X(k)=DFTx(n)， 则则(1) X(k)共轭对称共轭对称，即，即 X(k)=X*(N-k),0kN-1(2) 如果如果 x(n)=x(N-n)，则，则X(k)实偶对称实偶对称， 即即 X(k)=X(N-k)(3) 如果如果x(n)=-x(N-n)，则，则X(k)纯虚奇对称纯虚奇对称， 即即 X(k)=-X(N-k) 对实序列进行对实序列进行DFT，利用上述性质，可减，利用上述性质，可减少少DFT运算量。运算量。 例：设例：设x1(n)和和x2(n)都是都是N点的实数序列，点的实数序列，试用试用N点点DFT运算来计算他们各自的运算来计算他

17、们各自的DFT)()(21)()()(21)()()()()(*2*1kNXkXjk XkNXkXk X kXkXnxDFTk Xopep又)()()()()()()()()()()()()()()(212121212211kjXkX nxjDFTnxDFT njxnxDFTnxDFTk Xnjxnxnx kXnx DFTkXnxDFT则个复序列：解：利用两序列构成一3.3 频率域采样频率域采样 时域采样定理：在满足来奎斯特定理条件时域采样定理：在满足来奎斯特定理条件下，时域抽样信号可以不失真地还原连续下，时域抽样信号可以不失真地还原连续信号信号 频域采样呢？采样条件？内插公式？频域采样呢？采

18、样条件？内插公式？ 任意绝对可和的非周期序列任意绝对可和的非周期序列x(n)，其，其z变换变换?)()()(| )()()()()( nxkXWnxzXkX NzXznxzXnkNnWznnkN分析：序列：点等间隔采样，得周期在单位圆上对 m rrNn mWN rNnx WNmx WWmxN WkXNkXIDFSnxIDFSkXnxNkknmNrmNkknmNNknkNmmkNNknkNNN其他为任意整数：的为令0,11)(1)()(1)(1)()()()(10)(10)(1010 结论结论1：由频域采样序列由频域采样序列 还原得到的周期序还原得到的周期序列是原非周期序列列是原非周期序列 的周

19、期延拓序列，的周期延拓序列，其周期为频域采样点数其周期为频域采样点数 N。 结论结论2：时域采样造成频域周期延拓时域采样造成频域周期延拓频域采样造成时域周期延拓频域采样造成时域周期延拓)(kX)(nx 结论结论3：混叠失真不失真为有限长序列，长度为混叠失真为无限长序列 M N M N Mnxnx,)2,) 1)()( 频率采样定理：频率采样定理： 若序列长度为若序列长度为M，则只有当频域采样点数：，则只有当频域采样点数： 时，才有时，才有 即可由频域采样即可由频域采样X(k)不失真地恢复原信号不失真地恢复原信号x(n),否则产生时域混叠现象。否则产生时域混叠现象。MN )()()()()(nx

20、nRkXIDFSnRnxNNn内插公式内插公式 用频域采样用频域采样 X(k) 表示表示 X(z) 的内插公式的内插公式1011011010101010101)(111)(1)(1)(1)()()(),(NkkNNNkkNNNkNNknNnnkNNnnNknkNNnnMnnzWkXNzzWzWkXN zWkXN zWkXN znxznxzXMNNnxM点等间隔采样，且频域点有限长序列阶极点：零点：则内插公式简化为：内插函数：内插公式：) 1(0,1, 1 , 0,)()()(111)(1)(1)(22101101N e zN re zzkXzXzWzNz zWkXNzzXkNjrNjkNkkN

21、NkNkkNN内插公式内插公式 用频域采样用频域采样 X(k) 表示表示 X(ejw) 的内插公式的内插公式10)21(21)1(10)2()()()2sin()2sin(1)()2sin()2(sin1| )()()()(| )()(NkjNjNjNNkjezkjkNkjkezjkNkXeXeNNeekNkNNNzeekXzXeXjj内插公式：内插函数：3.4 DFT的应用举例的应用举例主要应用：主要应用：1. 用用DFT计算卷积和相关系数计算卷积和相关系数2. 用用DFT对连续信号和序列进行谱分析对连续信号和序列进行谱分析3.4.1 用用DFT计算线性卷积计算线性卷积10),()()()(

22、10,)()()()()()()()()()(212211102121Lk kXkXnyDFTk YLk nxDFTk XnxDFTk XnRmnxmxnxnxn yLmLL有：则由时域循环卷积定理且如果 线性卷积和循环卷积之间的关系？线性卷积和循环卷积之间的关系？ 循环卷积与线性卷积相等的条件？循环卷积与线性卷积相等的条件？ 设设h(n)和和x(n)都是有限长序列，长度分别是都是有限长序列，长度分别是N和和M。它们的线性卷积和循环卷积分别为。它们的线性卷积和循环卷积分别为： 其中，其中， LmaxN, M 1010( )( )( )( ) ()( )( )( )( ) ()( )NlmLcL

23、Lmy nh nx nh m x nmy nh nx nh m x nmR n( )(),Lqx nx nqL1010( )( )()( )( ) ()( )NcLmqNLqmy nh mx nmqL R nh m x nmqL R n 对照线性卷积的表达式可以看出线性卷积对照线性卷积的表达式可以看出线性卷积和循环卷积之间的关系：和循环卷积之间的关系： 10( ) ()()( )()( )NlmclLqh m x nqLMy nqLy ny nqL R n 线性卷积和循环卷积相等的条件：线性卷积和循环卷积相等的条件：1MNL0123451234h(n) x(n)nL 60123451234nL

24、 867h(n) 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补L N个零点L点DFT补L M个零点L点DFTL点IDFTy(n)h(n)x(n)若遇到两个序列长度相差很大的情况，将若遇到两个序列长度相差很大的情况，将长序列分段计算，采用重叠相加法。长序列分段计算，采用重叠相加法。 设序列设序列h(n)长度为长度为N，x(n)为无限长序列。为无限长序列。将将x(n)均匀分段，每段长度取

25、均匀分段，每段长度取M， 则则0( )( )( )( )()kikMx nx nx nx nRnkMh(n)与x(n)的线性卷积可表示为：000( )( )( )( )( )( )( )( )kkkkkkky nh nx nh nx nh nx ny nM0NMMx1(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) nnnnnnh(n)3.4.2 用用DFT进行谱分析进行谱分析 信号的频谱分析：计算信号的傅立叶变换信号的频谱分析：计算信号的傅立叶变换3.4.2 用用DFT进行谱分析进行谱

26、分析1、用、用DFT对连续信号进行谱分析对连续信号进行谱分析 设设连续信号连续信号xa(t)持续时间和持续时间和Tp，最高频率，最高频率为为fh。 xa(t)的傅里叶变换为的傅里叶变换为 对对xa(t)以采样间隔以采样间隔T1/2fh(即即fs=1/T2fh)采采样样得得a(t)=Xa(nT)。设共采样。设共采样N点，并对点，并对Xa(jf)作零阶近似作零阶近似(t=nT, dt=T)得得2()( )( )jfaaaXifFT x tx t etdt120()()NjfnTanX ifTx nT e Xa(jf)是是f的的连续周期函数连续周期函数，对，对 X(jf)在区在区间间0, fs上等间

27、隔采样上等间隔采样N点，采样间隔为点，采样间隔为F参数参数fs 、 Tp、 N和和F满足如下关系式：满足如下关系式： 11spfFNNTFT由于由于NT=Tp， 所以所以 210()()NjknNanX jkFTx nT e 0kN-1 ( )(), ( )()aaXkX jkfx nx nT令 则 21010210( )( ) ( )2( )()( )1( )1( )NjknNanNnNejknNanaXkTx n eT DFT x nx nXa nTFXa k ejknNFNXkNIDFT XkT 频率响应的混叠失真及参数的选择频率响应的混叠失真及参数的选择 谱分析范围：谱分析范围：已知信

28、号的最高频率已知信号的最高频率fh 频率分辨率：频率分辨率：即频率采样间隔即频率采样间隔F0000/12FfTTNTFffshs频率抽样：时域抽样： 信号最高频率和频率分辨率之间的矛盾信号最高频率和频率分辨率之间的矛盾.1000000NffTNFTFFNffFfTTNhsshs采样点数和频率分辨率，需增加同时提高信号最高频率必，要不产生混叠，给定，当，则要提高频率分辨率，即，即分辨率必给定，当，则要增加信号最高频率 信号最高频率信号最高频率fh的确定的确定 时域变化越快，高频分量越丰富时域变化越快，高频分量越丰富002112/tTfTthhh例例 对实信号进行谱分析，要求谱分辨率对实信号进行谱

29、分析，要求谱分辨率F10 Hz，信号最高频率信号最高频率fc=2.5 kHz， 试确定最小记录时试确定最小记录时间间TPmin，最大的采样间隔，最大的采样间隔Tmax，最少的采样点，最少的采样点数数Nmin。如果。如果fc不变，要求谱分辨率增加一倍，不变，要求谱分辨率增加一倍，最少的采样点数和最小的记录时间是多少最少的采样点数和最小的记录时间是多少? 解：解： 因此因此TPmin=0.1 s，因为，因为fs2fc， 所以所以 110.110PTsF3maxmin110.2 1022250022250050010ccTsffNF为使频率分辨率提高一倍，为使频率分辨率提高一倍， F=5 HzF=5 Hz， 要求要求minmin225001000510.25pNTs2、用、用DFT对序列进行谱分析对序列进行谱分析 因为：因为：已知单位圆上的已知单位圆上的Z变换就是序列傅里叶变变换就是序列傅里叶变换，换， 即即X(k)是单位圆上的是单位圆上的N点等间隔采样点等间隔采样 所以：序列的所以：序列的FT可以利用可以利用DFT计算。计算。()( )jjz eX eX z 对周期对周期N的周期序列的周期序列 ，其频谱函数为，其频谱函数为 根据根据DFT的隐含周