sp-5 离散时间信号的傅里叶分析

1、第五章 离散时间信号的傅里叶分析引言n本章主要讨论DTFT，DFT及其快速算FFTn离散化处理对信号的的真实频谱造成的影响n离散化时，信号原有的信息是否受损离散化时，信号原有的信息是否受损n如何计算抽样信号的频谱？如何计算抽样信号的频谱？n信号截断时，信号的频谱会如何改变？信号截断时，信号的频谱会如何改变？ n如何利用离散信号的抽样值直接计算离散信号的谱如何利用离散信号的抽样值直接计算离散信号的谱值呢？值呢？ n利用有限数目的离散谱值，如何恢复抽样信号？利用有限数目的离散谱值，如何恢复抽样信号？n如何解决编程实现中的大计算量问题？如何解决编程实现中的大计算量问题？抽样信号的频谱与连续时间信号的

2、频谱的关系 n用离散信号的频谱来分析研究连续信号的频谱（可认为是对连续信号频谱的第一次近似）n设连续时间信号设连续时间信号x(t)的频谱函数为的频谱函数为X(f)，对信号按时间间隔，对信号按时间间隔T抽样，得如下抽样信号：抽样，得如下抽样信号：n利用每二章学过的知识，对上面的信号进行傅里叶变换，得利用每二章学过的知识，对上面的信号进行傅里叶变换，得n nn即：信号时域抽样（离散化），将使得频谱周期重复，抽样即：信号时域抽样（离散化），将使得频谱周期重复，抽样信号的频谱等于原连续时间信号的频谱倍乘信号的频谱等于原连续时间信号的频谱倍乘fs后周期重复。后周期重复。n抽样定理 fs2fcn在奈奎斯特

3、区间内，模拟信号的频谱可以n（1）满足抽样定理时，用抽样信号的频谱来还原；）满足抽样定理时，用抽样信号的频谱来还原；n（2）若不满足，则用抽样信号的频谱来近似。）若不满足，则用抽样信号的频谱来近似。抽样信号的频谱与连续时间信号的频谱的关系 5.1 抽样信号频谱的数值计算 离散时间傅里叶变换DTFTn从抽样信号我们获得了信号的一些离散值n如何利用抽样信号来计算抽样信号的频谱 n具体的数值计算方法 用离散序列值计算抽样信号的频谱 （傅里叶变换定（傅里叶变换定义式，赫兹域）义式，赫兹域） （将抽样信号的（将抽样信号的表达式代入）表达式代入） （将积分与求和（将积分与求和的次序互换）的次序互换） （冲

4、激函数的特（冲激函数的特性）性）n式中，式中， 是理想抽样后各冲激点冲激信是理想抽样后各冲激点冲激信号的冲激强度值序列。因此，只要有了连续时间信号号的冲激强度值序列。因此，只要有了连续时间信号的抽样序列，就能通过上式计算出抽样信号的频谱来！的抽样序列，就能通过上式计算出抽样信号的频谱来！即即n n这就是序列这就是序列x(nT)的的离散时间傅里叶变换离散时间傅里叶变换，记为，记为DTFT用离散序列值计算抽样信号的频谱 关于DTFT公式的几点说明：（1） 抽样信号的频谱仅从抽样值x(nT)即可算出。（2） 是f的周期函数，周期为fs。即 因此，在进行频谱分析的时候，可以只关心奈奎斯特频率区间-fs

5、/2，fs/2。 （3） 如何求DTFT的逆变换？ （4） 数值近似问题。 （5） 工程近似问题。 （a）在时域，只能保留x(nT)有限数目的值，如L个样本，n=0,1L-1。所以要用截断求和来近似上式： （b）在频域，也只能保留有限的频谱值，即只在一些离散的频率处对 取样，用有限的离散值来近似原来的周期连续频谱(离散傅里叶变换DFT)。（6） Z变换。从上式可以导出Z变换与DTFT的关系。令 ，则 关于DTFT公式的几点说明：频率归一的DTFT n用抽样序列的DTFT所得的频谱，是一个以抽样频率fs为周期的周期频谱。为了研究方便，我们对这个周期频谱进行频率归一化，用归一频率 作为新的频率变量

6、，于是 如果用角频率来表示就是如果用角频率来表示就是 用归一化频谱求时域序列的逆变换的公式如下：用归一化频谱求时域序列的逆变换的公式如下： 频率归一的DTFTn不必再关心信号的抽样间隔，而只需将得到的信号抽样值顺次保存起来，再作变换即可，从而大大方便了抽样信号在计算机等数字处理设备上的分析处理。因此，今后，在不致引起混淆的情况下，我们用x(n)来代表x(nT)。n为了与信号的实际物理频率区别开，我们称归一化处理后的“频率”为数字频率（归一化频率 ），单位为弧度/样本（对应数字角频率）或赫兹/样本（对应数字频率）。频率归一的DTFTn频率归一化的理解：（1） 对于序列而言，时间间隔Ts并非必须的

7、，将其视为1也就不会带来什么问题。（2） 对于序列对应的连续频谱，都是周期的，这个周期由信号的采样频率完全决定。而信号的采样频率是可以变化的，也就是可以按照实际需要给出。换言之，连续谱的周期并不是一个特别重要的限制条件。 （3） 对于周期谱，我们通常只需（也只能如此）关心和存储一个周期的内容，因此，周期的具体大小没什么影响。因此，我们把频谱的周期统一归整为是可行的。当然，在必要的时候，要恢复（求解）数字频率所对应的实际物理频率也是非常容易的。DTFT的基本性质 n(1) 周期性： 在数字频率意义下，奈奎斯特区间为 ，为研究方便，通常使用 作为奈奎斯特区间。n(2) 线性：n(3) 平移：n时移

8、特性：时移特性： n频移特性：频移特性： ，ak为常数为常数 DTFT的基本性质n(4) 反褶、共轭：n反褶：反褶： n共轭：共轭： n(5) 时域扩展 序列的时域扩展定义如下： 它的DTFT为n (6) 频域微分(时域线性加权) DTFT的基本性质n(7) 卷积定理 设设时域卷积：时域卷积： 频域卷积：频域卷积： n(8) 帕斯瓦尔定理 例题n例4.1 求单位冲激序列的DTFT( ( )( )1j nnDTFTnn en例4.2 求矩形脉冲序列的DTFT10/2/2/2/2/2/2(1)/21( )( )1()()sin(/2)sin(/2)jNNj nj nNNjnnjNjNjNjjjj

9、NeDTFT GnGn eeeeeeeeeNe)()(jjeeX 例题)(jeX24 N0)(2043 43n)()(4nRnx 0123451G例4.3 单边指数序列)()(nuanxn 1 a nnjjenxeX)()( 0nnjneajae 11 以上序列的以上序列的z变换为变换为111)( azzXaz RezImzj1a当当|a|1，单位圆被包含在收敛域中，所以，单位圆被包含在收敛域中，所以jezjaezXeXj 11)()(n)(nx0123450 an)(nx01 23450 ajDTFTnaenua 11)(即即例题例题n例4.4 求有限长序列x(n)=4,3,2,1,2,3,

10、4的DTFTn解：n那么 为多少？0()jX e例例4.5 已知已知X(ej)=DTFTx(n)，试求序列，试求序列x(n)。424231)( ) 1 (jjjjeeeeX) 1( 11)( )2(aaeeXjjccjeX001)( ) 3(解：解：由定义由定义nnjjenxeX)()(32)3()2() 1 ()0(jjjexexexx4)4(, 0)3(, 2)2(, 3) 1 (, 1)0(xxxxx)4(4)2(2) 1(3)()(nnnnnx例题 (2)见例见例4.3cc-21)(denxnjcc-21ndjejnnjccnjejn21)(21njnjcceejnnncsin1nnc

11、ccsinnncccsin)(nSacc)(jeXcc)(nxn0 123 4c DTFT 由定义由定义-)(21)(deeXnxnjj)(jeXcc加窗序列的DTFT n到目前为止，在数字信号处理中，我们所得到的 是X(f)的最好近似。然而，在工程上也仍是不可计算的，还需要无穷多的抽样点x(n)， 。n为此，必须对X(f)作进一步的近似，即用有限数目抽样样本的频谱来近似无穷多样本点序列的频谱！n这种近似过程，实际上是对抽样信号在时域加窗的操作。加窗序列的DTFTn加窗后可以认为信号在窗口外为零，在窗口内等于原信号的值，即宽为L的矩形窗可定义为： 则加窗后的信号可定义为： 加窗序列的DTFT这

12、样加窗前后信号的频谱为这样加窗前后信号的频谱为 加窗序列的DTFTn加窗对序列频谱的影响 设矩形窗设矩形窗W(n)的的DTFT频谱函数为频谱函数为 利用利用DTFT的卷积定理性质，序列加窗后的的卷积定理性质，序列加窗后的DTFT频谱密度函数为频谱密度函数为 因此，加窗序列的频谱将是原序列的频谱与窗序列频谱的卷积，因此，加窗序列的频谱将是原序列的频谱与窗序列频谱的卷积，下面我们来看看这种频谱卷积对于原频谱的影响。下面我们来看看这种频谱卷积对于原频谱的影响。根据矩形窗的定义，将根据矩形窗的定义，将w(n)=1代入，可得代入，可得 n加窗对序列频谱的影响 其幅度谱为其幅度谱为 频谱示意图如下：频谱示

13、意图如下： 加窗序列的DTFT定义主瓣的宽度为定义主瓣的宽度为 加窗序列的DTFTn加窗对序列频谱的影响 即主瓣宽度即主瓣宽度(频率分布范围频率分布范围) 由窗信号的持续时间由窗信号的持续时间(时间长度时间长度)唯一决定。唯一决定。若频谱分析所要求的频率分辨率为若频谱分析所要求的频率分辨率为 ，则所需信号样本的最小数目为：，则所需信号样本的最小数目为： 这也是窗函数序列的实际长度。这也是窗函数序列的实际长度。加窗序列的DTFTn一般来讲，加窗会对序列的频谱产生两种主要的影响：（1） 信号的频谱分辨率将降低。可分辨的最小频率间隔受限于数信号的频谱分辨率将降低。可分辨的最小频率间隔受限于数据记录的

14、长度（实际上是窗函数的时间长度据记录的长度（实际上是窗函数的时间长度 ）。）。（2） 将高频噪音引入了信号的频谱。这些高频分量是信号将高频噪音引入了信号的频谱。这些高频分量是信号x(n)在在矩形窗的左右两个边缘因被截断而发生突变造成的。矩形窗的左右两个边缘因被截断而发生突变造成的。总之，窗函数频谱的主瓣宽度决定了总之，窗函数频谱的主瓣宽度决定了DTFT总的能达到的频率分总的能达到的频率分辨率，而窗函数的旁瓣则决定了辨率，而窗函数的旁瓣则决定了DTFT总的频率泄漏。频率泄漏是加总的频率泄漏。频率泄漏是加窗操作引入的副作用，它可能与信号中那些较小的谐波分量处的主瓣窗操作引入的副作用，它可能与信号中

15、那些较小的谐波分量处的主瓣相混淆，因此应该尽可能的减少或减轻频率泄漏。相混淆，因此应该尽可能的减少或减轻频率泄漏。5.2 离散傅里叶变换离散傅里叶变换DFT连续时间傅里叶变换连续时间傅里叶变换CTFT不适宜于在数字不适宜于在数字计算机上进行计算。计算机上进行计算。其主要原因为：其主要原因为：信号覆盖了整个时间轴（时间受限信号除外）信号是时间连续的（定义域是连续的）信号的频谱覆盖了整个频谱轴（频带受限信号除外）信号的频谱是连续的时域要离散、有限！ 频谱要离散、有限！时域周期延拓时域截断时域抽样解决信号的离散化问题解决信号的离散化问题工程上无法处理时间无限信号工程上无法处理时间无限信号要使频率离散

16、，就要使时域变成周期信号要使频率离散，就要使时域变成周期信号时域乘以矩形脉冲信号，频域相当于和抽样函数卷积通过窗函数对信号进行逐段截取连续信号离散化使得信号的频谱被周期延拓周期延拓中的搬移通过与 的卷积来实现周期延拓后的周期函数具有离散谱)(snTt 通过与抽样信号相乘得到经过抽样、截断和延拓后，信号时域和频域都是离散、周期的。DFT的推导有 卷 积 波 纹NN原 函 数用 于 抽 样抽 样 后用 于 截 断截 断 后用 于 延 拓延 拓 后定 义 D FT叠 加 干 涉0 t0 t0 t0 t0 t0 t0 t0 t 或 nTs0 f 或 kf00 f0 f0 f0 f0 f0 f0 fDF

17、T的定义n设信号的数据长度为L，其N点DFT定义为信号的DTFT在奈奎斯特区间 上N个等间距的频率点处的频谱密度值，即信号的N点DFT结果是N个频谱密度值。在奈奎斯特区间上均匀分布的N个DFT频率为 根据根据DFT的定义，将这些频率值代入的定义，将这些频率值代入DTFT的频谱公式中，得的频谱公式中，得 DFT的定义nDFT是是DTFT的一种特殊均匀抽样方式：（的一种特殊均匀抽样方式：（为什么说它为什么说它特殊呢？特殊呢？）它的频段范围是整个奈奎斯特区间，因此，）它的频段范围是整个奈奎斯特区间，因此，要考察的频率点的位置仅与要考察的频率点的位置仅与DFT要求的点数要求的点数N有关有关（因为抽取范

18、围是固定的因为抽取范围是固定的）。对所有的）。对所有的N点点DFT来讲，来讲，它们所涉及的频率点位置都是一样的，即它们所涉及的频率点位置都是一样的，即 因此，通常我们可以将因此，通常我们可以将N点点DFT直接写作直接写作 DFT的定义若令若令 ，则上式可以简记为，则上式可以简记为 其中，其中， 与与DFT的点数的点数N有关，称为有关，称为DFT的旋转因子。的旋转因子。这可以看作是这可以看作是DFT的另一种更直接的定义式。的另一种更直接的定义式。DFT的定义 从数学上看，序列的N点DFT可以看作是一个线性矩阵变换，即将L维的时域向量变成N维的频域向量的一种线性变换。即： 其中，其中，L 是数据记

19、录中时域样本的数目，它可能是无限的；是数据记录中时域样本的数目，它可能是无限的；N 则是对则是对DTFT进行抽样的频率的数目。进行抽样的频率的数目。 通常在讨论通常在讨论DFT时，一般都假定时，一般都假定LN。 DFT的定义DFT的定义补零与回绕补零与回绕N点等间隔采样点等间隔采样补零与回绕n当然，如果取变换区间N32，即在有限长离散时间序列尾部补零更多位，则32点的DFT谱线更密。这是因为增长观察时间，可提高频率分辨率。但DFT频谱的包络，始终与非周期序列 的离散时间傅立叶变换DTFT的连续频谱曲线一致。这又表明DFT是DTFT连续频谱的离散化。n补零的结果是对已经截断得到的信号的频谱分辨率

20、的提高，而不是对原来未截断的信号的分辨率的提高。 补零与回绕n回绕n任意两个序列，只要它们的回绕序列是相等的，那么它们的DFT结果也就是相等的。因此，多个完全不同的序列，可以对应完全相同的DFT结果！换句话说，也就是一个DFT结果实际上对应着多个序列！ 补零与回绕n如果序列的长度L小于DFT点数N，可以通过补零使它们相等，并且这不会影响DFT结果；而当序列长度L大于DFT点数N时，单个DFT结果会对应多个时域信号。这就是说：序列短了（LN）会发生多个序列对应同一个DFT结果，运算就不是可逆的了。 离散傅里叶逆变换IDFT 或NjNeW/2变换核定义变换核定义IDFT的第二种实现方法n说明IDF

21、T可以与DFT共享同一个算法实现。 离散傅里叶逆变换IDFT“同一同一DFT结果对应着多个信号结果对应着多个信号”，这里所求出的只是原，这里所求出的只是原始信号的回绕信号。它们之间的关系如下图所示：始信号的回绕信号。它们之间的关系如下图所示： 只有在只有在 时，才不会有回绕发生时，才不会有回绕发生 DFT的频谱特点n通过DFT所得的频谱n（1）是离散的这是显然的，因为）是离散的这是显然的，因为DFT对对DTFT连续谱的抽样；连续谱的抽样；n（2）也是周期的（关于下标）也是周期的（关于下标k，周期是，周期是N）这）这是是DTFT频谱的周期性的体现（频谱的周期性的体现（DTFT是抽样信号的是抽样信

22、号的傅里叶变换，时域抽样所以频域周期）。傅里叶变换，时域抽样所以频域周期）。 DFT的频谱特点DFT的频谱特点DFT的频谱特点n周期性序列的序列的N点的点的DFT离散谱关于下标离散谱关于下标k是周期的，周期为是周期的，周期为N，即，即 n实序列频谱的共轭对称性若若 是实序列，其是实序列，其N点点DFT关于原点和关于原点和N/2都都具有共轭对称性，即具有共轭对称性，即 关于原点共轭对称：关于原点共轭对称： 或或 关于关于N/2点共轭对称点共轭对称(N为偶数为偶数)： 或或 推论：推论：实序列的实序列的DFT频谱关于原点和频谱关于原点和N/2点是幅度对称的。点是幅度对称的。DFT的性质n线性 n若

23、若 则则DFT的性质n时移特性（圆周移位）显然，上式中显然，上式中 ，因此序列的时移不会影响，因此序列的时移不会影响DFT频谱的幅度。频谱的幅度。 另外，还可以根据回绕序列的另外，还可以根据回绕序列的DFT与原序列的与原序列的DFT的关系，来的关系，来证明上面的特性。证明上面的特性。 最后，还可以通过引入圆周移位（也称循环移位）的概念，最后，还可以通过引入圆周移位（也称循环移位）的概念，对对DFT的时移特性作出解释。的时移特性作出解释。 即不是直接在直线上对序列进行普通的移位，而是将序列看成即不是直接在直线上对序列进行普通的移位，而是将序列看成是排列在一个是排列在一个N等分的圆周上，等分的圆周

24、上，N个样本点首尾相接，平移个样本点首尾相接，平移m个单位是在圆周上进行的，即让序列沿着圆周按一定的方向要个单位是在圆周上进行的，即让序列沿着圆周按一定的方向要求求“转动转动”m个单位！当然，序列沿圆周移位后，序列的起点个单位！当然，序列沿圆周移位后，序列的起点位置还是原先的位置，只不过不是对应原先的元素了。位置还是原先的位置，只不过不是对应原先的元素了。DFT的性质n时移特性（圆周移位） 将将 x(n) 周期延拓周期延拓( (周期周期 N ) )，得，得 x(n)N 将将 x(n)N 左移或右移左移或右移 m点点，得，得 x(nm)N 截取截取 x(nm)N 的主值序列即得。的主值序列即得。

25、( )()( )NNy nx nmRnDFT的性质n时移特性（圆周移位） 周期序列移位时，在周期序列移位时，在 0, N-1区间，从该区间一端移出的序区间，从该区间一端移出的序列值，与从另一端移入的序列列值，与从另一端移入的序列值相同，所以值相同，所以x(n)的圆周移位的圆周移位相当于其序列值在圆上的旋转。相当于其序列值在圆上的旋转。如：如：N=8x(6)x(4)x(0)x(1)x(2)x(3)x(5)x(N-1)0有限长序列的圆周移位有限长序列的圆周移位左移左移顺时针旋转顺时针旋转右移右移逆时针旋转逆时针旋转DFT的性质n时移特性（圆周移位）对于序列的反褶运算、奇偶对称性的判断等，也可以在圆

26、周上进行。对于序列的反褶运算、奇偶对称性的判断等，也可以在圆周上进行。 例：例：已知已知 5点有限长序列点有限长序列 x(n)=5,4,3,2,1155( )(2)( )2,1,5,4,3y nx nR n266( )(2)( )1,0,5,4,3,2ynx nR n355( )(2)( )3,2,1,5,4y nx nR n线性移位序列：线性移位序列：(2)x n(2)x n线性右移线性右移线性左移线性左移圆周移位序列：圆周移位序列： ( (N=5) )( (N=6) )圆周圆周右移右移( (N=5) )圆周左圆周左移移466( )(2)( )3,2,1,0,5,4ynx nR n( (N=

27、6) )0, 0 ,5, 4, 3, 2,15, 4, 3, 2,1DFT的性质DFT的性质n频移特性如果序列的如果序列的DFT频谱在频域发生平移，与结果将导致序列在时频谱在频域发生平移，与结果将导致序列在时域发生一定的改变。域发生一定的改变。 这个定理表明，如果序列在时域乘以指数项这个定理表明，如果序列在时域乘以指数项W-nl，则离散傅里叶，则离散傅里叶变换就向右圆移变换就向右圆移l单位。这可以看作是调制信号的频谱搬移，也称单位。这可以看作是调制信号的频谱搬移，也称调制定理。调制定理。 DFT的性质n对称性DFT的对称性与连续时间傅里叶变换的对称性非常类似的对称性与连续时间傅里叶变换的对称性

28、非常类似 即如果将某序列的即如果将某序列的DFT变换结果，当作一个新的时域序列进变换结果，当作一个新的时域序列进行行DFT，所得的频谱与原序列有如下的关系存在，所得的频谱与原序列有如下的关系存在 上面的公式表明，当对离散谱再次进行上面的公式表明，当对离散谱再次进行DFT运算时，得到的运算时，得到的结果是原时域序列反褶的结果是原时域序列反褶的N倍。显然，如果原序列具有偶对倍。显然，如果原序列具有偶对称性，则其称性，则其DFT结果就是原时域序列的结果就是原时域序列的N倍了。倍了。 DFT的性质n反褶与共轭特性序列反褶，对应频域也反褶：序列反褶，对应频域也反褶： 序列共轭，频域共轭加反褶：序列共轭，

29、频域共轭加反褶： 序列反褶加共轭，频域共轭：序列反褶加共轭，频域共轭： 时域时域频域频域反褶反褶反褶反褶共轭共轭共轭共轭反反褶褶共轭共轭反褶反褶共轭共轭DFT的性质n奇偶虚实特性（a）对奇对称和偶对称的序列）对奇对称和偶对称的序列 奇函数的奇函数的DFT是奇函数；是奇函数； 偶函数的偶函数的DFT是偶函数。是偶函数。（b）对实序列：）对实序列：实偶函数的实偶函数的DFT是实偶函数；实奇函数的是实偶函数；实奇函数的DFT是虚奇函数。是虚奇函数。实函数的实函数的DFT，其实部是偶函数，虚部是奇函数；其模是偶，其实部是偶函数，虚部是奇函数；其模是偶函数，而相位是奇函数。函数，而相位是奇函数。（c）对

30、虚序列：）对虚序列：虚偶函数的虚偶函数的DFT是虚偶函数；虚奇函数的是虚偶函数；虚奇函数的DFT是实奇函数。是实奇函数。虚函数的虚函数的DFT，其实部是奇函数，虚部是偶函数；其模是偶，其实部是奇函数，虚部是偶函数；其模是偶函数，而相位是奇函数。函数，而相位是奇函数。DFT的性质n奇偶虚实特性举例DFT的性质n奇偶虚实特性举例利用上面的式子可以计算出一个利用上面的式子可以计算出一个N点复序列的点复序列的DFT的同时，的同时，计算出两个计算出两个N点实序列的点实序列的DFT。DFT的性质n时域卷积定理 时域卷积是一个很常见的运算，这一方面是因为时域卷积是一个很常见的运算，这一方面是因为线性时线性时

31、不变的特性不变的特性 ，另一方面是因为对频谱进行滤波处理时，要在，另一方面是因为对频谱进行滤波处理时，要在频域进行乘法频域进行乘法，从而导致信号（序列）在时域发生卷积。，从而导致信号（序列）在时域发生卷积。 DFT的性质n时域卷积定理时域圆周卷积DFT中的卷积定理是另外一种解释中的卷积定理是另外一种解释 如果将本性质换一种形式表达，改写成逆变换的形式，则有如果将本性质换一种形式表达，改写成逆变换的形式，则有 即序列即序列DFT乘积对应的序列是原序列卷积的回绕。乘积对应的序列是原序列卷积的回绕。可证得可证得 DFT的性质n时域卷积定理时域圆周卷积记做记做这样，如果我们把传统卷积过程中所包含的这样

32、，如果我们把传统卷积过程中所包含的“平移平移”操作改为操作改为“圆圆移移”，即相当于同时完成，即相当于同时完成“平移平移”和和“回绕回绕”操作，则上面的这种对操作，则上面的这种对序列序列x(m)和和y(m)而言是特殊的而言是特殊的“卷积卷积”运算，仍旧与传统的卷积运运算，仍旧与传统的卷积运算一样，包含了算一样，包含了“反褶反褶”、“移位移位”、“乘积乘积”与与“求和求和”等步骤。等步骤。（只不过这时的（只不过这时的“移位移位”实际上是圆周上的移位）。实际上是圆周上的移位）。 DFT的性质既是为了突出这两种卷积之间的不同之处，也是为了突出它既是为了突出这两种卷积之间的不同之处，也是为了突出它们之

33、间的相同处，我们可以称过去定义的卷积为们之间的相同处，我们可以称过去定义的卷积为“线卷积线卷积”，而定义这里新引入的特殊形式的卷积为而定义这里新引入的特殊形式的卷积为“圆卷积圆卷积”，同时引，同时引入一个新的卷积符号来表示这种运算入一个新的卷积符号来表示这种运算 n时域卷积定理时域圆周卷积圆卷积编程实现容易圆卷积编程实现容易DFT的性质n帕斯瓦尔定理n频域卷积DFT的快速算法FFTn在数字信号处理（如滤波器设计）、信号的频谱分析（如在通信、图像传输、雷达、声纳等中的频谱分析）、系统的分析和设计实现等方面，都会大量用到DFT计算。 n直接按定义计算DFT的计算量太大 DFT的快速算法FFTnDF

34、T的算法复杂度n由由IDFT与与DFT定义可知二者的运算量完全相同的定义可知二者的运算量完全相同的n通常，通常，x(n)和和 都是复数，算得的都是复数，算得的X(k)也是复数，也是复数，因此每计算一个因此每计算一个X(k)值，都需要值，都需要N次复数乘法次复数乘法（x(n)与与 相乘）以及（相乘）以及（N-1）次复数加法。而）次复数加法。而序列序列X(k)一共有一共有N个点（个点（k从从0取到取到N-1），所以要），所以要完成整个完成整个DFT运算总共需要运算总共需要N2次复数乘法及次复数乘法及N(N-1)次复数加法。次复数加法。DFT的快速算法FFTnDFT直接计算的问题DFT的快速算法FF

35、Tn假设序列为假设序列为2，3，3，210233200000NNNNWWWWXjWWWWXNNNN12332 1 32100233226420NNNNWWWWXjWWWWXNNNN1233239630复数加法复数加法 N(N-1)复数乘法复数乘法 N 2DFT的快速算法FFTnDFT直接计算的问题DFT的快速算法FFTnDFT计算的改进思路基于W的两个性质n周期性周期性n对称性对称性DFT的快速算法FFTnDFT计算的改进思路将上面的性质应用到前面的矩阵中，可以简化为DFT的快速算法FFTDFT的快速算法FFTnFFT算法分类n按时间抽取（按时间抽取（DIT）的）的FFT算法算法n按频率抽取（

36、按频率抽取（DIF）的）的FFT算法算法n基基-2FFT算法：算法： N为为2的整数幂的的整数幂的FFT算法算法DFT的快速算法FFTnDIT-FFT12/.210) 12()()2()(21Nrrxrxrxrx，将序列将序列x(n)按按n的奇偶分成两组：的奇偶分成两组：10)()()(NnknNWnxnxDFTkXkrNnNrrkNnNrWrxWrx)12(12/0212/0) 12()2( 为奇为偶 )(12/02/2)(2/12/0121)()(kXNrrkNkNkXrkNNrWrxWWrx)()()(21kXWkXkXkN记：记： （1 1）rkNrkNWW2/2（这一步利用：（这一步

37、利用： ）,0,1,./2 1r kN将将N点点DFT定义式分解为两个长度为定义式分解为两个长度为N/2的的DFTDIT-FFTDITFFT再利用周期性求再利用周期性求X(k)的后半部分的后半部分/22NkNkkNNNNWWWW 又)(2)()()(222112/02/112/0)2/(2/11kXkNXkXWrxWrxkNXNrrkNNrkNrNrkNkNrNWW2/)2/(2/)2()2()2()2(12/,.2 , 1 , 0)()()(2)2/(121kNXWkNXkNXNkkXWkXkXkNNkN，12/,.2 , 1 , 0)()(21NkkXWkXkN，N=2xk=x0, x1 1 0002xWxX 1 0 1 12xWxX0 x 1 x0X-102W 1 X 1 002xWx基2时间抽取FFT的算法流程x0 x2x1x3X10X11X20X212点DFT2点DFT111104W14W02W02WX 0X 1X 2X 31 , 0,241mmXWmXmXm1 , 0,2241mmXWmXmXm4点基2时间抽取FFT算法流程4点基2时间抽取FFT算法流程4点DFT4点DFTx0 x2x4x6x1x3x5x7X10X11X12X13X20X21X22X23X 0X 1X 2X 3X 4X 5X 6X 7 111111108W