测试信号处理技术第四章.ppt

《测试信号处理技术第四章.ppt》由会员分享，可在线阅读，更多相关《测试信号处理技术第四章.ppt（89页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、离散时间信号分析离散时间信号分析内容提要内容提要 序列的傅里叶变换（序列的傅里叶变换（DTFT）拉氏变换、傅氏变换与拉氏变换、傅氏变换与z变换之间的关系变换之间的关系 离散傅里叶级数（离散傅里叶级数（DFS）离散傅里叶变换（离散傅里叶变换（DFT）快速傅里叶变换（快速傅里叶变换（FFT）快速傅里叶变换的应用快速傅里叶变换的应用离散离散时间时间傅里叶傅里叶变换变换DTFT与与连续时间连续时间傅里叶傅里叶变换变换的关系的关系性性质质离散傅里叶离散傅里叶变换变换DFT定定义义性性质质离散傅里叶离散傅里叶变换变换的快速算法的快速算法FFT原理原理流程流程应应用用实际信号的特点：信号的特点：时域：域：连

2、续时间信号信号;持持续时间较长频域：域：频谱是是连续的的数字数字处理理设备（计算机）的特点：算机）的特点：存存储空空间有限有限-只能存只能存储有限多的数据有限多的数据离散的离散的时间点点有限有限长的的时间范范围表示空表示空间有限有限-只能表示有限多的数只能表示有限多的数值取取值在一定精度内在一定精度内取取值在一定范在一定范围内内在在时域如何域如何对信号信号进行离散化？行离散化？要求保要求保证信号的信号的信息不受信息不受损！信息不受信息不受损=可以恢复原信号可以恢复原信号理理论问题已在第二章解决已在第二章解决乘以冲激串信号，乘以冲激串信号，进行行时域抽域抽样要求抽要求抽样过程程满足抽足抽样定理定

3、理信号信号频带有限，抽有限，抽样频率是信号最高率是信号最高频率率的两倍的两倍矛盾1已基本解决如何用抽如何用抽样信号的信号的频谱来来恢复恢复原信号的原信号的频谱？抽抽样信号信号频谱与原信号与原信号频谱是什么关系？是什么关系？理理论上如何恢复？上如何恢复？工程工程实践上如何践上如何实现？抽抽样信号的信号的频谱如何如何计算算？得到抽得到抽样信号后，如何信号后，如何计算其算其频谱？输入：抽入：抽样信号（序列）信号（序列）输出：抽出：抽样信号的信号的频谱在工程上，在工程上，计算机接受的算机接受的输入是一系列数入是一系列数值信号被截短信号被截短时，频谱发生什么生什么变化化？有有时信号持信号持续时间超出超出

4、处理能力理能力时域信号需要被截断域信号需要被截断截断会不会影响截断会不会影响对信号的分析？信号的分析？截断截断对信号的信号的频谱有何影响？有何影响？有限有限长离散信号离散信号频谱的的存存储与与计算算频谱是是连续周期的周期的1.1.只能存只能存储有限有限长的的频谱一个周期即可一个周期即可2.2.只能存只能存储有限多的有限多的频谱离散离散频率点率点处的的频谱值离散离散频率点率点谱值的的计算算法一：先有法一：先有连续谱，后有离散，后有离散谱值（频域采域采样）法二：直接用法二：直接用时间抽抽样值计算离散算离散谱值（公式）？（公式）？如何由如何由频谱恢复抽恢复抽样信号？信号？离散离散频谱值是有限的是有限

5、的恢复抽恢复抽样信号的信号的计算公式算公式如何如何编程程实现（如何（如何进行快速行快速计算）？算）？按定按定义实现-计算量太大算量太大由离散信号由离散信号计算离散算离散频谱由离散由离散频谱恢复离散信号恢复离散信号从工程需要出从工程需要出发，理解信号，理解信号频谱分析的分析的实际问题。即即在在实践中践中领悟悟处理原理的意理原理的意义从解决从解决问题出出发，理解各种信号，理解各种信号处理方法的目的。理方法的目的。即即在矛盾中思考工程在矛盾中思考工程实现的背景的背景在解决的问题过程中感受知识的力量、体会学习的快乐在解决的问题过程中感受知识的力量、体会学习的快乐1.定义x(n)x(n)的的z z变换为

6、如果X(z)X(z)在在单位位圆上是收上是收敛的，的，则把在把在单位位圆上上的的z z变换定义为序列的傅里叶变换，表示为(4.1)相对应序列的傅里叶反变换，由z z反反变换的的围线积分公式若把积分围线C C取在取在单位位圆上，上，则有有（4.2）2 2物理意物理意义把序列的傅里叶把序列的傅里叶变换称作非周期序列的称作非周期序列的频谱，为什什么把序列的傅里叶么把序列的傅里叶变换和序列的和序列的频谱联系在一起系在一起?可以与可以与连续信号的傅里叶信号的傅里叶变换进行行对比比进行分析行分析.已知已知连续信号的傅里叶信号的傅里叶变换为F()有频谱密度的意义，是频谱的概念，有频谱密度的意义，是频谱的概念

7、，在式（在式（4.1）中，）中，X(ej)是序列的傅里叶变换，是序列的傅里叶变换，与与F()在连续信号傅里叶变换的表达式中一在连续信号傅里叶变换的表达式中一样起着相同的作用，所以看作是样起着相同的作用，所以看作是序列的频谱序列的频谱。f(t)和和x(n)的两个表达式都具有叠加重构（综的两个表达式都具有叠加重构（综合）时域信号即傅里叶反变换的作用，合）时域信号即傅里叶反变换的作用，因此把式（因此把式（4.2）称为序列的傅里叶反变换。）称为序列的傅里叶反变换。将式（4.1）和（4.2）重写并表示为(4.3)(4.4)3特点特点由式由式(4.3)知，序列知，序列频谱频谱X(ej)是是ejn的函数，的

8、函数，而而ejn 是是以以2为为周期的函数，并且由于序列周期的函数，并且由于序列在在时时域上是非周期的，因而，序列的域上是非周期的，因而，序列的频谱频谱是周是周期的期的连续频谱连续频谱。同同时时X(ej)是是 的复函数，可的复函数，可进进一步表示一步表示为为(4.5)(4.5)()()()()()wwwjwwjjjjjeXjeXeeXeXImRe+=其幅度谱如图4.1所示图4.1 4.1 序列及其幅谱图序列及其幅谱图序列傅立叶序列傅立叶变换存在的条件存在的条件由于序列的傅里叶由于序列的傅里叶变换是是单位位圆上的上的z z变换，序列的序列的z z变换在在单位位圆上必上必须收收敛是序列傅里是序列傅

9、里叶叶变换存在的条件，即存在的条件，即上式表明，序列傅里叶上式表明，序列傅里叶变换存在的条件是：序存在的条件是：序列必列必须绝对可和。可和。(充分条件充分条件)例4.1 求出下列序列的傅里叶求出下列序列的傅里叶变换变换。x2(n)=(n+3)-(n-4)解:目的目的:找出找出连续信号与离散信号各种信号与离散信号各种变换的关系的关系变换关系的关系的纽带:冲激抽冲激抽样信号信号 沟通沟通连续和离散信号的和离散信号的桥梁梁1.冲激抽冲激抽样样信号的拉氏信号的拉氏变换变换Xs(s)与与连续连续信号的拉信号的拉氏氏变换变换Xa(s)之之间间关系：关系：拉氏拉氏变换变换的指数形式的指数形式为为周期周期为T

10、 T的周期冲激信号傅氏的周期冲激信号傅氏级数的表达式数的表达式(周周期延拓期延拓)为见例见例2.122.12的证明的证明 为采采样角角频率，率，则冲激抽冲激抽样信号可表示信号可表示为可可导出冲激抽出冲激抽样信号拉氏信号拉氏变换的另一种形式的另一种形式由此，可得到冲激抽由此，可得到冲激抽样信号的拉氏信号的拉氏变换有有指数指数级数数与与周期延拓周期延拓表示的两种等价表达式。表示的两种等价表达式。即即()()()-=-=-W-=msansnTasjmsXTenTxsX1(4.14)(4.14)2 2冲激抽冲激抽样信号的拉氏信号的拉氏变换X Xs s(s)(s)与抽与抽样序列的序列的z z变换X(z)

11、X(z)之之间关系关系z z与与s s变量之量之间的映射关系的映射关系z=ez=esTsT，若离散，若离散时间信号信号为抽抽样序列，即序列，即x(nT)=x(n)x(nT)=x(n)，并引入，并引入z=ez=esTsT时，得到，得到序列序列z z变换为上式表示，上式表示，z z变换可以看成沖激抽样信号的拉变换可以看成沖激抽样信号的拉氏变换由氏变换由s s平面映射到平面映射到z z平面的变换。平面的变换。3冲激抽冲激抽样样信号的拉氏信号的拉氏变换变换Xs(s)与其傅氏与其傅氏变换变换Xs(j)之之间间的关系的关系为为由由s=+j，若，若=0，而且拉氏，而且拉氏变换变换收收敛敛域包含虚域包含虚轴时

12、轴时，则则虚虚轴轴上的拉氏上的拉氏变换变换即即为为其傅氏其傅氏变换变换，或，或者者说说，冲激抽冲激抽样样信号的傅里叶信号的傅里叶变换变换是其在虚是其在虚轴轴上上的拉氏的拉氏变换变换。4冲激抽冲激抽样样信号的傅氏信号的傅氏变换变换Xs(j)与与连续时间连续时间信号的傅氏信号的傅氏变换变换Xa(j)之之间间：冲激抽冲激抽样样信号傅氏信号傅氏变换变换的指数的指数级级数的形式，以及数的形式，以及连续时间连续时间信号的傅里叶信号的傅里叶变换变换Xa(j)的周期延拓形的周期延拓形式，式，对对沖激抽沖激抽样样信号而言是等价的，表示信号而言是等价的，表示为为5激抽激抽样样信号傅氏信号傅氏变换变换的指数形式与序

13、列的的指数形式与序列的傅里叶傅里叶变换变换表达式：两相比表达式：两相比较较，若序列，若序列为为抽抽样样序序列，有：列，有：x(n)=xa(nT)，而且数字角，而且数字角频频率与模率与模拟拟角角频频率率，满满足足=T，则则相相应频应频率点上的率点上的频谱值频谱值相等。相等。6序列序列z变换变换X(z)与序列傅里叶与序列傅里叶变换变换X(ej)之之间间：序列的傅里叶序列的傅里叶变换变换X(ej)为为X(z)在在单单位位圆圆上的特例。上的特例。把上述分析的把上述分析的结论，用，用图来形象地描来形象地描绘如下：如下：()()()()()()()()()()()()-=-W=-=W-=W=-=-=-=-

14、=W=W-W=W-njnjTnTnjasmsaezjsnneznTxnxnsTnasmsaenxeXenTxjXjmjXTznxzXenTxsXjmsXTjsTawwww11此图非常清晰地表明了：此图非常清晰地表明了：冲激抽样信号是沟冲激抽样信号是沟通离散信号与连续信号各种变换的桥梁。通离散信号与连续信号各种变换的桥梁。4.3.1 傅里叶傅里叶变换变换在在时时域和域和频频域中的域中的对对称称规规律律一一连续连续非周期信号，由前述，其傅里叶非周期信号，由前述，其傅里叶变换变换（频频谱谱）Xa()是非周期的是非周期的连续谱连续谱，时时域上的非周期域上的非周期对对应频应频域上的域上的连续连续，或，或

15、频频域上的域上的连续对应时连续对应时域上的域上的非周期，由此可以得到非周期，由此可以得到时时、频频域的第一个域的第一个对对称称规规律：律：时时域上的非周期将域上的非周期将产产生生频谱频谱的的连续连续，或者或者说说，频频域的域的连续导连续导致致时时域的非周期域的非周期总总之一个域中函数的之一个域中函数的连续对应连续对应另一个域的非周期。另一个域的非周期。如下如下图图4.4（a）所示）所示图图4.4 4.4 信号在时、频域中的对称规律信号在时、频域中的对称规律如如图图4.4（b），一周期信号），一周期信号xp(t)，其，其频谱频谱是离散是离散谱谱Xpk1)。可以从另一个角度来理解：。可以从另一个角

16、度来理解：Xp(k)正是正是对图对图4.4（a）中的）中的频谱频谱Xa()以采以采样频样频率率1进进行抽行抽样样，即，即频频域被离散化，域被离散化，则则在在时时域上域上产产生生单单周期信周期信号号xa(t)的周期延拓，延拓周期的周期延拓，延拓周期为为T1=21，形成周形成周期延拓波形期延拓波形xp(t).时时、频频域的第二个域的第二个对对称称规规律：律：时时域上的周期化将域上的周期化将产产生生频谱频谱的离散化，或的离散化，或者者说说，频频域的离散化域的离散化导导致致时时域的周期化，域的周期化，总总之，一个域的离散化之，一个域的离散化对应对应另一个域的周期化。另一个域的周期化。各种信号傅里叶各种

17、信号傅里叶变换变换在在时时域、域、频频域上域上对对称性的称性的一一规规律可概括律可概括归纳为归纳为：1 在某一个域（在某一个域（时时域或域或频频域）中是域）中是连续连续的，相的，相应应地在另一个域（地在另一个域（频频域或域或时时域）中肯定是非周期性域）中肯定是非周期性的。的。2 在某一个域（在某一个域（时时域或域或频频域）中是离散的，相域）中是离散的，相应应地在另一个域（地在另一个域（频频域或域或时时域）中肯定是周期性的。域）中肯定是周期性的。上述上述规规律是由傅里叶律是由傅里叶变换变换的的对对称性（称性（对对偶性）偶性）所决定的。所决定的。4.3.2 离散傅里叶级数DFS对于连续周期函数x

18、p(t)，有对x p(t)进进行抽行抽样样，变变成了离散成了离散时间时间周期信号周期信号x ps(nT)或或x p(n)（以抽样序列x p(n)为为例），周期序列在例），周期序列在时时域可用复指数序列域可用复指数序列形式的傅里叶级数来表示，将t=nT、代入上式中，得从而有记作由于复指数序列的周期性，显然有 由上述分析可知：周期离散信号在时、频域上均为周期序列，根据周期信号的特点，当k变化一个N的整数倍时，得到的是完全一样的序列，所以，一个周期序列可以表示成一个有限项（N项）指数序列分量的叠加（即用任一个周期的序列情况，可以描述、代表所有其他周期序列的情况），则习惯上表示为上式就是离散傅里叶级数

19、（DFS）的定义式，是反变换的概念。根据反变换的表达式来导出正变换Xp(k)的解析表达式()()-=1021NkknNjppekXNnxp傅里叶傅里叶级数的正数的正变换以符号以符号DFSDFS表示，表示，离散傅里叶离散傅里叶级数的反数的反变换，符号，符号IDFSIDFS表示，表示，写成写成为表达简洁,引入符号DFTDFT要解决两个要解决两个问题：一是一是离散离散与与量化量化，二是二是快速运算快速运算。一一.DFT.DFT是重要的是重要的变换1.1.分析分析有限有限长序列序列的有用工具。的有用工具。2.2.在信号在信号处理的理的理理论上有重要意上有重要意义。3.3.在在运算方法上运算方法上起核心

20、作用，起核心作用，谱分分析、卷析、卷积、相关都可以通、相关都可以通DFTDFT在在计算机上算机上实现。4.4.1 离散傅里叶变换DFT定义式 对于一个周期为N的周期序列x xp p(n)(n)，把它的第，把它的第一一个周期的有限长序列定义为这一周期序列的主值序列，用x(n)x(n)表示表示周期序列周期序列X p(k)X p(k)、x p(n)x p(n)换成主成主值序列序列X(k)X(k)、x(n)x(n)，这样就得到了两个有限就得到了两个有限长序列的序列的变换对，并，并表示表示为式（式（4.354.35）称）称为离散傅里叶正离散傅里叶正变换，以符号，以符号DFTDFT表示，式（表示，式（4.

21、364.36）是离散傅里叶反）是离散傅里叶反变换，以符号以符号IDFTIDFT表示表示()()()()()()36.4(10,1)35.4(10,1010-=-=-=-=NnWkXNkXIDFTnxNkWnxnxDFTkXNkknNNnknNDFT DFT，IDFTIDFT可可简写写为:式中，式中，X(k)X(k)与与x(n)x(n)分分别为N N 行的列矩行的列矩阵，而，而WWnknk 与与WW-nk-nk分分别为N N N N 的的对称方称方阵。例例4.2 4.2 用矩用矩阵形式求矩形序列形式求矩形序列x(n)=Rx(n)=R4 4(n)(n)的的DFTDFT，再由所得再由所得X(k)X(

22、k)经IDFTIDFT求求x(n)x(n)，验证所求所求结果的正果的正确性。确性。4.4.2 4.4.2 离散傅里叶离散傅里叶变换DFTDFT与序列傅里叶与序列傅里叶变换的关系的关系设一有限长序列x(n)长度为N点，其z变换为因序列为有限长，满足绝对可和的条件，其z变换的收敛域为整个z平面，必定包含单位圆，则序列的傅里叶变换为现以 为间隔，把单位圆（表示为ej）均匀等分为N个点，则在第k个等分点由上式可以得出：有限长序列的DFT就是序列在单位圆上的z变换（即序列傅里叶变换）在单位圆上以为间隔 的抽样值，参见下图。DFT与序列傅里叶变换对比1 1线性特性性特性若若:X(k)=DFTx(n),Y(

23、k)=DFTy(n)X(k)=DFTx(n),Y(k)=DFTy(n)则DFTax(n)+by(n)=aX(k)+bY(k)DFTax(n)+by(n)=aX(k)+bY(k)式中，式中，a a、b b为任意常数。如果两个序列的任意常数。如果两个序列的长度度不相等，以最不相等，以最长的序列的序列为基准，基准，对短序列要短序列要补零，使序列零，使序列长度相等，才能度相等，才能进行行线性相加，性相加，经过补零的序列零的序列频谱会会变密，但不影响密，但不影响问题的性的性质。2.时移特性（1）圆周移位圆周移位也叫循环移位，简称圆移位。它是序列的这样一种移位：将一有限长序列x(n)，进行周期延拓，周期为

24、N，构成周期序列x p(n)，然后对周期序列x p(n)作m位移位处理得移位序列x p(n-m)，再取其主值序列（x p(n-m)与一矩形序列RN(n)相乘），得x p(n-m)R N(n)，就是所谓的圆周移位序列。2.2.圆周位移的含周位移的含义由于我由于我们取主取主值序列，即只序列，即只观察察n=0n=0到到N-1N-1这一主一主值区区间，当某一抽，当某一抽样从此区从此区间一端移出一端移出时，与它相同与它相同值的抽的抽样又从此区又从此区间的另一端的另一端进来。来。如果把如果把x(n)x(n)排列一个排列一个N N等分的等分的圆周上周上，序列的，序列的移位就相当于移位就相当于x(n)x(n)

25、在在圆上旋上旋转，故称作，故称作圆周移周移位。当位。当围着着圆周周观察几圈察几圈时，看到就是周期序，看到就是周期序列列:x(n)x(n)。（2）时移定理所谓时移定理是指：若DFT x(n)=X(k)则DFT xp(n-m)RN(n)=时移定理表明：序列在时域上圆周移位，频域上将产生附加相移。3 频移特性频移特性若若DFT x(n)=X(k)则则并并上述特性表明：若序列在时域上乘以复指数上述特性表明：若序列在时域上乘以复指数序列序列 ，则在频域上，则在频域上，X(k)将圆将圆周移位周移位l 位，这可以看作调制信号的频谱搬移，位，这可以看作调制信号的频谱搬移，因而又称因而又称“调制定理调制定理”。

26、4.5 离散傅里叶变换的性质4圆周卷积特性圆周卷积特性（1）时域圆周卷积）时域圆周卷积若对若对N点的序列有点的序列有X(k)DFT x(n),H(k)DFT h(n),Y(k)DFT y(n)，Y(k)=X(k)H(k)则则 若若x(m)保持不移位，则保持不移位，则 正是圆周正是圆周 移位，故称移位，故称 为圆周卷积。为圆周卷积。即即（2）频域圆卷积）频域圆卷积若：若：y(n)=x(n)h(n)则：则：DFT变换的性质()()()()()()()-=-=-=-=1111NmNmmnymxmnymxkYkXIDFT反褶反褶循环循环移位移位相乘相乘相加相加也是一种卷积也是一种卷积!为了突出新为了突

27、出新“卷积卷积”与与“旧旧”卷积的不同卷积的不同,同同时也为了突出它们之间的相同时也为了突出它们之间的相同,称过去传统的卷积为称过去传统的卷积为线卷积线卷积,而而称此称此“新卷积新卷积”为序列的圆周卷积，简称为序列的圆周卷积，简称圆卷积圆卷积。()()()()-=-=10Nmmnymxnynx频域卷积频域卷积()()()()kYkXNnynxDFT=1编程实现容易编程实现容易4.5 离散傅里叶变换的性质5 5奇偶性奇偶性（1 1）实数序列）实数序列设设x(n)x(n)为实序列，为实序列，X(k)X(k)DFT x(n)DFT x(n)，则，则可知：可知：X(k)X(k)的实部为的实部为k k的

28、偶函数，的偶函数，X(k)X(k)的虚部是的虚部是k k的奇的奇函数。函数。4.5 离散傅里叶变换的性质X(k)的幅度和相位分别为的幅度和相位分别为设设x(n)是实序列，其是实序列，其DFT可写成可写成4.5 离散傅里叶变换的性质从而有从而有 由上述式子表明：由上述式子表明：实数序列实数序列x(n)的离散傅里叶变换的离散傅里叶变换X(k)，在，在0至至N的范围的范围内，内，对于对于N/2点点，|X(k)|呈半周期呈半周期偶偶对称分布对称分布，arg X(k)呈半周期呈半周期奇奇对称分布对称分布。但由于长度为。但由于长度为N的的X(k)有值有值区间是区间是0（N-1），），而在式（而在式（4.5

29、3）中）中增加了第增加了第N点点的的数值，因此所谓的对称性并不是很严格。数值，因此所谓的对称性并不是很严格。4.5 离散傅里叶变换的性质（2 2）复数序列）复数序列对于共轭复数序列。若有限长序列对于共轭复数序列。若有限长序列x*(n)x*(n)是是x(n)x(n)的的共轭复数序列，并设共轭复数序列，并设4.5 离散傅里叶变换的性质则则 利用式（利用式（4.57）、（）、（4.58）可以计算出）可以计算出一个一个N点复序列点复序列DFT的同时，计算出的同时，计算出两个两个N点实序列的点实序列的DFT。4.5 离散傅里叶离散傅里叶变换的性的性质6 帕斯瓦尔定理帕斯瓦尔定理若若X(k)DFT x(n

30、)则则 上式左端代表离散信号在时域中的能量，右端是代表在上式左端代表离散信号在时域中的能量，右端是代表在频域中的能量，表明变换过程中能量是守恒的。频域中的能量，表明变换过程中能量是守恒的。计算DFT的快速算法-FFT()()()1,1,0,10-=-=NkWnxnxDFTNnnkNL计算计算DFT的计算量：的计算量：每算一个每算一个X(k)，需要，需要N次复数乘法，次复数乘法，N-1次次加法。因此，加法。因此，N点点DFT需要需要N*N次复数乘次复数乘法，法，N(N-1)次复数加法。次复数加法。直接计算直接计算DFT的复杂度为的复杂度为O(N2)尽管预先算好并保存旋转因子尽管预先算好并保存旋转

31、因子 WNk 可以节省部可以节省部分运算，但按定义求分运算，但按定义求DFT的运算量仍然很大。的运算量仍然很大。4.6 快速傅里叶变换（FFT）4.6.1 DFT4.6.1 DFT直接运算的问题和改进思路直接运算的问题和改进思路1 1DFTDFT直接运算的工作量直接运算的工作量直接对直接对DFTDFT进行计算的基本问题是运算量大，很难进行计算的基本问题是运算量大，很难实现信号的实时处理，如某序列实现信号的实时处理，如某序列x(n)x(n)，N N 4 4，则序列，则序列x(n)x(n)的的DFTDFT为为4.6 快速傅里叶变换（FFT）若要求若要求X(k)的的N=4个个值，复数乘的次数：复数乘

32、的次数：N2=42=16，复数加的次数：复数加的次数：N(N-1)12，这样简单的的DFT计算，其算，其计算量已算量已经不小。不小。如果如果N=210=1024，则复数乘的次数：复数乘的次数：N2=1,048,576，复数加次数：复数加次数：N2=1,048,576，难以以实现信号的信号的实时处理，若理，若N大大增加，运大大增加，运算量也会随之大大增加，算量也会随之大大增加，实时处理几乎就理几乎就变得得不可能了，因此必不可能了，因此必须改改进DFT的算法。的算法。4.6 快速傅里叶变换（FFT）2 2改改进思路思路DFTDFT的定的定义式式为（1 1）的的周期性周期性（2 2）的的对称性称性将

33、上述（1）、（2）中的结果，代入矩阵W，可以简化为（）矩阵W中，许多元素是相等的，可明显减少计算量。（）由于运算量正比于N2，因此可以把大点数（大N）DFT的计算化为小点数（如N/2），又可进一步地把DFT计算量大幅度减下来。综合应用上述的改进思路，实现傅里叶变换的快速计算的算法，就是快速快速傅里叶傅里叶变换，FFTFFT（Fast Fourier TransformFast Fourier Transform）。）。特特别说明：明：FFTFFT是是DFTDFT的快速算法，不是新的的快速算法，不是新的变换方法。其算法基方法。其算法基础是：是：WW的两个性的两个性质。1.W具有周期性2.W具有对

34、称性经过周期性与对称性简化之后经过周期性与对称性简化之后,容容易发现易发现DFT运算中存在着不必要运算中存在着不必要的重复计算的重复计算,避免这种重复避免这种重复,是简是简化运算的关键化运算的关键.N点点DFT运算可以分解为两组运算可以分解为两组N/2点点DFT运算，然后再取和。运算，然后再取和。DFTDFT的复杂度与点数的复杂度与点数N N有关！有关！4.6.2 基基2按按时间时间抽取的抽取的FFT算法（算法（时时析型）析型）1算法原理算法原理“基基2”序列序列x(n)，设设：N=2 M（M为为整整数），如果数），如果N不是不是2的的幂幂次，次，应应在序列后面在序列后面补补零到零到2 M，这

35、这是是“基基2”的意思。的意思。随后按照随后按照n的奇偶性的奇偶性以及以及时间时间的先后的先后抽取序列抽取序列值值，把序列分成奇数序号与偶数序号两，把序列分成奇数序号与偶数序号两组组序列序列之和（大点数化之和（大点数化为为小点数），小点数），这这也就是所也就是所谓谓的的“按按时间时间抽取抽取”的基本含意。的基本含意。()()()()()()()()()()()()()12,2,1,01221221221202120212021202nn-=+=+=+=+=-=-=-=-=NrrxrzrxryWrxWWrxWrxWWrxWnxWnxkXNrrkNkNNrrkNNrrkNkNNrrkNnkNnkN

36、L奇数偶数注意Y(k)与与Z(k)的周期是的周期是N/2!于是，于是，N点点X(k)可用可用N/2点的点的Y(k)和和Z(k)来来计计算：算：8点点DFT 4点点DFT（先按奇偶序分（先按奇偶序分组组，再求，再求4点点DFT）就地置换无需缓存就地置换无需缓存一个蝶形单元只需一个蝶形单元只需一一次复数次复数乘法和乘法和两两次复数加法次复数加法 全部计算分解为全部计算分解为M级，或称为级，或称为M次迭代。次迭代。输入序列输入序列x(n)按码位倒读顺序排列，输出序列按码位倒读顺序排列，输出序列X(k)按自然顺序排列。按自然顺序排列。每级都包含每级都包含N/2个蝶形单元。个蝶形单元。每每级级的若干蝶形

37、的若干蝶形单单元元组组成成“群群”。第。第1级级群数群数为为N/2，第，第2级级群数群数为为N/4，第第i级级群数群数为为N/2i，最后一最后一级级的群数的群数为为1。每个蝶形每个蝶形单单元都包含乘元都包含乘Wnk与与-Wnk的运的运算（可算（可简简化化为为乘乘Wnk与加、减法各一次）。与加、减法各一次）。同一同一级级中，各个群的中，各个群的W分布分布规规律律完全相同完全相同码位倒读码位倒读输输入序列入序列x(n)的排列次序不符合自然的排列次序不符合自然顺顺序。此序。此现现象是由于按象是由于按n的奇偶分的奇偶分组进组进行行DFT运算而造成的，运算而造成的，这这种排列方式称种排列方式称为为“码码位倒位倒读读”的的顺顺序。序。所谓所谓“倒读倒读”，是指按二进制表示的数，是指按二进制表示的数字首尾位置颠倒，重新按十进制读数。字首尾位置颠倒，重新按十进制读数。自然顺序自然顺序二进制顺序码二进制顺序码位倒置码位倒置码位倒读顺序位倒读顺序0 00000000000000 01 10010011001004 42 20100100100102 23 30110111101106 64 41001000010011 15 51011011011015 56 61101100110113 37 71111111111117 7码位倒读示例（码位倒读示例（N=8）