数字信号处理课件1-4

第1章时域离散信号和时域离散系统,掌握常见时域离散信号的表示及运算。掌握时域离散系统的线性、时不变性、因果性及稳定性的含义及判别方法。掌握采样定理。,信号的定义：是信息的载体，是传输信息的函数，这种信息通常是一个物理系统的状态或特性。信号的分类：模拟信号离散信号数字信号,1.1引言,信号处理信号处理是研究系统对含有信息的信号进行处理（变换），以获得人们所希望的信号，从而达到提取信息、以便利用的一门学科。,1.1引言,系统分类：模拟系统数字系统,1.1引言,数字信号处理数字信号处理就是把用数字或符号，通过计算机或者通用（专用）的信号处理设备，用数字的数值计算的方法进行处理，以达到提取信息便于应用的目的。,1.1引言,数字信号处理的特点,灵活性高精度和高稳定性便于大规模集成可以实现模拟系统无法实现的诸多功能,1.1引言,1.2时域离散信号,离散时间信号（序列）只在离散时刻给出函数值，是时间上不连续的序列。实际中遇到的信号一般是模拟信号，对它进行等间隔采样便可以得到时域离散信号。假设模拟信号为xa(t)，以采样间隔T对它进行等间隔采样，得到：,注意：n为整数,思考：序列的表示方法有哪些？,离散时间信号及其时域表示,离散时间信号在物理上是指定义在离散时间上的信号样品的集合，在数学上可用时间序列x(n)来表示。,样品集合可以是本来就存在的，也可以是由模拟信号通过采样得来的或者是用计算机产生的,x(n)代表序列的第n个样点的数字，n代表时间的序号。,1.2时域离散信号,离散时间信号的时域表示,*离散信号还可用图形的方式表示,图中横坐标n表示离散的时间坐标，且仅在n为整数时才有意义；纵坐标代表信号样点的值。,许多时候为了方便，直接用x(n)来代表序列全体x(n)。本书中，离散时间信号与序列将不予区分。,一、典型序列,1单位采样序列(n),单位采样序列的作用：表示任意序列,例1.写出图示序列的表达式,2、单位阶跃序列u(n),3矩形序列RN(n),4实指数序列,5.复指数序列,式中0为数字频率,将复指数表示成实部与虚部,其示意图如下：,6.正弦序列,正弦与余弦序列示意图如下：,7周期序列定义：如果对所有n存在一个最小的正整数N，使下面等式成立：则称序列x(n)为周期性序列，周期为N。,例2、求下列周期,二、序列的运算,1加法和乘法序列之间的加法和乘法，是指同一时刻的序列值逐项对应相加和相乘。,2移位移位序列x(nn0)，当n00时,称为x(n)的延时序列；当n0反转-平移-相乘-求和（2）列表法（3）解析法,1.3时域离散系统,一、线性系统,系统的输入、输出之间满足线性叠加原理的系统称为线性系统。设x1(n)和x2(n)分别作为系统的输入序列，其输出分别用y1(n)和y2(n)表示，即,若统满足叠加原理,线性系统,那么该系统就是线性系统。,例7、判断y(n)=ax(n)+b(a和b是常数）所代表系统的线性性质。,二、时不变系统,如果系统对输入信号的运算关系T在整个运算过程中不随时间变化，或者说系统对于输入信号的响应与信号加于系统的时间无关，则这种系统称为时不变系统，用公式表示如下：,例8、判断y(n)=nx(n)代表的系统是否是时不变系统。,例9、判断y(n)=ax(n)+b(a和b是常数）所代表系统是否是时不变系统。,三、LTI系统输入与输出之间的关系,单位脉冲响应LTI系统的输出,解释：LTI系统,卷积和性质：代数运算性质（交换律、结合律、分配律）延迟性质典型信号的卷积,*交换律,*结合律,卷积的性质,若有两个级联系统h1(n)和h2(n)，如图所示，,则有,*分配律,若有两个并联系统h1(n)和h2(n)，如图所示，,则有,以上两图中的系统分别等效,四、系统的因果性和稳定性,因果性：当且仅当信号激励系统时，才产生响应的系统，也称为不超前响应系统。LTI系统具有因果性的充要条件：判断一个系统是否为因果，有两种方法。定义法和充要条件，后者只对LTI系统有效。,证明：充分性若nn0的x(m)无关。因此，该系统为因果性系统。,下面证明线性时不变因果系统的充要条件,必要性：采用反证法。假定系统为因果性系统，但在n0时h(n)0，按卷积公式，对于任何输入x(n)，n0时刻的其输出y(n0)为,这样，由于nn0的x(m)有关，与系统是因果性系统的假设矛盾。因此必须有n0时h(n)=0。证毕。,稳定性：有界输入（指幅度有界），有界输出LTI系统稳定的充分必要条件：系统的单位脉冲响应绝对可和，即,例9、设LTI系统的单位系统脉冲响应h(n)=anu(n)，式中a是实常数，试分析该系统的因果稳定性。,1.4时域离散系统的输入输出描述法线性常系数差分方程,N阶线性常系数差分方程表示：式中，x(n)和y(n)分别是系统的输入序列和输出序列，ai和bj均为常数.,线性常系数差分方程的求解,经典解法（实际中很少采用）递推解法（方法简单，但只能得到数值解，不易直接得到公式解）变换域法（Z域求解，方法简便有效）,递推解法,例10、设因果系统用差分方程y(n)=ay(n1)+x(n)描述，输入x(n)=(n)若初始条件y(-1)=0，求输出序列y(n)。,若初始条件改为y(-1)=1，求y(n),例11、设差分方程如下，求输出序列y(n)。,非因果系统,结论,差分方程本身不能确定该系统是因果系统还是非因果系统，还需要用初始条件进行限制。一个线性常系数差分方程描述的系统不一定是线性时不变系统，这和系统的初始状态有关。,课堂练习,1、以下序列是LTI系统的单位序列响应h(n)，判断系统的因果性和稳定性。,答案（1）非因果、稳定（2）非因果、不稳定。,课堂练习,课堂练习,3、判断题：一个系统是因果系统的充要条件是，单位序列响应h(n)是因果序列。答案：错,课堂练习,4、将序列x(n)用一组幅度加权和延迟的冲激序列的和来表示。,5、判断下面的序列是否是周期的;若是周期的，确定其周期。,解：（1）因为=,所以,这是有理数，因此是周期序列，周期T=14。（2）因为=,所以=16,这是无理数，因此是非周期序列。,课堂练习,6、设线性时不变系统的单位脉冲响应h(n)和输入x(n)分别有以下几种情况，分别求输出y(n)。（1）h(n)=R4(n),x(n)=R5(n)（2）h(n)=2R4(n),x(n)=(n)(n2)解：（1）1，2，3，4，4，3，2，1（2）2，2，0，0，-2，-2,课堂练习,频谱分析：把信号表示为不同频率正弦分量或复指数分量的加权和，简称信号的谱分析。傅立叶分析：用频谱分析的观点来分析系统，或称为系统的频域分析。,频域分析法在系统分析中极其重要，主要是因为：(1)频域分析法易推广到复频域分析法，同时可以将两者统一起来；(2)利用信号频谱的概念便于说明和分析信号失真、滤波、调制等许多实际问题，并可获得清晰的物理概念；(3)连续时间系统的频域分析为离散时间系统的频域分析奠定坚实基础。(4)简化了求解微分方程的过程,傅立叶分析,周期信号，周期为，角频率,该信号可以展开为下式复指数形式的傅立叶级数。,复指数形式的傅立叶级数,其中,(一)周期信号的傅立叶级数,式中称为傅立叶系数，是复数。,例：将图示周期矩形脉冲信号展成指数形式傅立叶级数,解：直接代入公式有,所以,(一)周期信号的傅立叶级数,1.周期信号的频谱为了能既方便又明白地表示一个信号中包含有哪些频率分量，各分量所占的比重怎样，就采用了称为频谱图的表示方法。,(二)周期信号的频谱,在傅立叶分析中，把各个分量的幅度随频率或角频率的变化称为信号的幅度谱。,而把各个分量的相位随频率或角频率的变化称为信号的相位谱。,幅度谱和相位谱通称为信号的频谱。,三角形式的傅立叶级数频率为非负的，对应的频谱一般称为单边谱，指数形式的傅立叶级数频率为整个实轴，所以称为双边谱。,频谱图：,若把相位为零的分量的幅度看作正值，把相位为的分量的幅度看作负值，那么幅度谱和相位谱可合二为一。,幅度谱,相位谱,(二)周期信号的频谱,周期矩形脉冲信号的傅立叶系数为,对周期信号，如果令T趋于无穷大，则周期信号将经过无穷大的间隔才重复出现，周期信号因此变为非周期信号.,从傅立叶级数到傅立叶变换,当T增加时，基波频率变小、离散谱线变密，频谱幅度变小，但频谱的形状保持不变。在极限情况下，周期T为无穷大，其谱线间隔与幅度将会趋于无穷小。这样，原来由许多谱线组成的周期信号的离散频谱就会联成一片，形成非周期信号的连续频谱。,上两式称为傅立叶变换对，采用下列记号：,傅立叶正变换,傅立叶反变换,(三)傅立叶变换,矩形脉冲信号,典型信号的傅立叶变换,时域卷积性质,若则,频域卷积性质,（四）傅里叶变换的性质,拉氏变换对,正变换,反变换,记作，称为原函数，称为象函数,采用系统，相应的单边拉氏变换为,考虑到实际信号都是有起因信号,拉普拉斯变换的定义,收敛域：使F(s)存在的s的区域称为收敛域。记为：ROC(regionofconvergence)实际上就是拉氏变换存在的条件；,拉普拉斯变换的定义,1.5模拟信号数字处理方法,采样定理；采样前的模拟信号和采样后得到的采样信号之间的频谱关系；如何由采样信号恢复成原来的模拟信号；实际中如何将时域离散信号恢复成模拟信号。,什么是信号抽样,为什么进行信号抽样,(1)信号稳定性好:数据用二进制表示，受外界影响小。,(4)系统精度高:可通过增加字长提高系统的精度。,(5)系统灵活性强:改变系统的系数使系统完成不同功能。,(2)信号可靠性高:存储无损耗，传输抗干扰。,离散信号与系统的主要优点：,(3)信号处理简便:信号压缩，信号编码，信号加密等,对模拟信号进行采样可以看做一个模拟信号通过一个电子开关S。,实际抽样,电子开关合上时间0，则形成理想采样,理想抽样,理想采样,理想采样,采样信号的频谱是原模拟信号频谱以s为周期，进行周期性延拓而成的，且频谱幅度为1/T。,信号时域的离散化导致其频域的周期化,采样信号频谱,频谱混叠,采样信号的恢复,采样信号的恢复,采样信号的恢复,低通滤波器G(j）的单位冲激响应g(t)为：,采样信号的恢复,采样信号的恢复,奈奎斯特采样定理,对连续信号进行等间隔采样形成采样信号，采样信号的频谱是原连续信号的频谱以采样频率s为周期进行周期性延拓形成的。设连续信号xa(t)属带限信号，最高截止频率为c，如果采样角频率s2c，那么让采样信号通过一个增益为T、截止频率为s/2的理想低通滤波器，可以唯一地恢复出原连续信号xa(t)。否则,s2c会造成采样信号的频谱混叠现象，不可能无失真地恢复原连续信号。,抽样定理的工程应用,许多实际工程信号不满足带限条件,抗混低通滤波器,混叠误差与截断误差比较,抽样定理的工程应用,重要公式,课堂练习,7、设LTI系统由下面差分方程描述：设系统是因果的，利用递推法求系统的单位脉冲响应。,解：令x(n)=(n),则,n=0时，,n=1时，,n=2时，,n=3时，,所以,8、数字信号是指_的信号。时间幅度都离散的,9、若用单位序列及其移位加权和表示x(n)=_。,10、序列是周期序列的条件是_。,11、序列2，3，2，1与序列2，3，5，2，1相加为_，相乘为_。4，6，7，3，14，9，10，2,12、判断正误数字信号处理的主要对象是数字信号，且是采用数值运算的方法达到处理目的的。()对,13、判断正误单位阶跃序列与矩形序列的关系是错,14、判断正误因果系统一定是稳定系统。()错,15、判断正误如果系统对输入信号的运算关系在整个运算过程中不随时间变化，则这种系统称为时不变系统。（）对,16、判断正误所谓稳定系统是指有界输入、有界输出的系统。（）对,17、判断正误差分方程本身能确定该系统的因果和稳定性。()错。差分方程本身不能确定该系统的因果和稳定性，还需要用初始条件进行限制。,18、判断正误若连续信号属带限信号，最高截止频率为c，如果采样角频率s2c，那么让采样信号通过一个增益为T、截止频率为s/2的理想低通滤波器，可以唯一地恢复出原连续信号。()错,引言,一、时域离散信号傅里叶变换的定义,正变换：序列x(n)的傅里叶变换（离散时间傅里叶变换DTFT）定义为：序列的傅里叶变换存在的充分条件是序列x(n)满足绝对可和的条件，即,一、时域离散信号傅里叶变换的定义,反变换X(ej)的傅里叶反变换为：性质：傅里叶变换的周期性、线性性质时移与频移性质、对称性时域卷积定理、频域卷积定理帕斯维尔定理,例1、设x(n)=RN(n)，求x(n)的傅里叶变换。,当N=4时，其幅度与相位随频率的变化曲线如图所示：,1、傅里叶变换的周期性,傅里叶分析规律：则离散非周期序列的傅里叶变换是：连续周期的。,1、傅里叶变换的周期性,傅里叶变换是频率的周期函数，周期是2。说明：由于傅里叶变换的周期是2，一般只分析或02的范围。,1、傅里叶变换的周期性,2、线性性质,3、时移与频移性质,时移性质：,频移性质：,4、傅里叶变换的对称性,（1）共轭对称的定义设序列xe(n)满足：则称xe(n)为共轭对称序列。,4、傅里叶变换的对称性,结论：共轭对称序列的实部是偶对称的，虚部是奇对称的。,4、傅里叶变换的对称性,（2）共轭反对称定义设序列xo(n)满足：则称xo(n)为共轭反对称序列。,4、傅里叶变换的对称性,结论：共轭反对称序列的实部是奇对称的，虚部是偶对称的。,（3）一般序列可用共轭对称与共轭反对称序列之和表示，即又则,4、傅里叶变换的对称性,同理,4、傅里叶变换的对称性,（4）傅里叶变换的对称性质将上式进行傅里叶变换，得到:,4、傅里叶变换的对称性,结论：序列分成实部与虚部两部分，实部对应的傅里叶变换具有共轭对称性；虚部和j一起对应的傅里叶变换具有共轭反对称性。,4、傅里叶变换的对称性,将序列分成共轭对称部分xe(n)和共轭反对称部分xo(n)，即x(n)=xe(n)+xo(n)则,4、傅里叶变换的对称性,结论：序列x(n)的共轭对称部分xe(n)对应着X(ej)的实部ReX(ej)；序列x(n)的共轭反对称部分xo(n)对应着X(ej)的虚部乘j，即jImX(ej)。,4、傅里叶变换的对称性,5、时域卷积定理,若y(n)=x(n)*h(n),则,6、频域卷积定理,若y(n)=x(n)h(n),则,7、帕斯维尔定理,定理表明：时域的总能量等于频域的总能量。,2.3周期序列的离散傅里叶级数及傅里叶变换表示式,掌握周期序列的离散傅里叶级数掌握周期序列的傅里叶变换,一、周期序列的离散傅里叶级数,例2、设x(n)=R4(n)，将x(n)以N=8为周期进行周期延拓，得到周期序列，周期为8，求DFS,一、周期序列的离散傅里叶级数,一、周期序列的离散傅里叶级数,幅度特性,一、周期序列的离散傅里叶级数,各种傅里叶变换的定义及特点,各种傅里叶变换的定义及特点,二、周期序列的傅里叶变换,因为周期序列不满足绝对可和的条件，因此它的FT并不存在，但由于是周期性的，可以展成离散傅里叶级数，引入奇异函数(W)，其FT可以用公式表示出来。（知识回顾）连续信号的傅里叶变换对离散信号中存在傅里叶变换对,周期序列的傅里叶变换,周期序列的傅里叶变换,二、周期序列的傅里叶变换,二、周期序列的傅里叶变换,二、周期序列的傅里叶变换,二、周期序列的傅里叶变换,例3、设x(n)=R4(n)，将x(n)以N=8为周期进行周期延拓，得到周期序列，周期为8，求FT,解：已知,得：,其幅度频谱为：对比例2,二、周期序列的傅里叶变换,二、周期序列的傅里叶变换,课堂练习,2、序列的傅里叶变换为_。,3设系统的单位脉冲响应h(n)=anu(n),00时，h(n)0C当n1,二、序列特性对收敛域的影响,1有限长序列其z变换为：有限长序列的收敛域一般是0|z|0时，ROC为：,0|z|,0|z|,0|z|,有限长序列,例6、求x(n)=RN(n)的Z变换及其收敛域。解：收敛域为：0a,求其逆Z变换x(n)。解n0时，F(z)在c内只有1个极点：z1=a；n0时，F(z)在c内有2个极点：z1=a,z2=0（高阶）；,1、留数法,则n0时，n0时，围线内有高阶极点，由于F(z)的分母阶次比分子阶次高二阶以上，因而求圆外极点留数。由于围线外无极点，故n|a1|，对应的x(n)是因果序列；（2）|z|a|，对应的x(n)是左序列；（3）|a|z|a1|:这种情况的原序列是因果序列，无须求n0时的x(n)。当n0时，F(z)在c内有两个极点：z=a和z=a1，因此,1、留数法,最后表示成：x(n)=(anan)u(n)。,1、留数法,（2）收敛域为|z|a|:原序列是左序列，无须计算n0情况。实际上，当n0时，围线积分c内没有极点，因此x(n)=0。n0时，c内只有一个极点z=0，且是n阶极点，改求c外极点留数之和。即,最后将x(n)表示成封闭式：x(n)=(anan)u(n1),1、留数法,（3）收敛域为|a|z|a1|:x(n)是双边序列。根据被积函数F(z)，按n0和n0两种情况分别求x(n)。n0时，c内只有1个极点：z=a,则x(n)=ResF(z),a=an,1、留数法,na,课堂练习,2、的Z变换为_，收敛域为_。,1/(1-az-1)，za,3、判断题序列z变换的收敛域内可以含有极点。()错,课堂练习,4、已知求z反变换。解:,所以当n0时，x(n)=0。只需考虑n0时的情况。,课堂练习,如图所示，取收敛域的一个围线c，可知当n0时,C内有两个一阶极点，所以,课堂练习,5、已知，求z反变换。,课堂练习,如图所示，取收敛域的一个围线c，分两种情况讨论：（1）n1时，,C内只有一个一阶极点,课堂练习,课堂练习,（2）当n0,1,即s平面的右半平面映射到z平面单位圆外；,r1,即s平面的左半平面映射到z平面单位圆内；,s平面和z平面之间的映射关系,（2）与的关系（=T）,s平面宽的水平条带对应整个z平面。,=0，=0，s平面的实轴对应z平面正实轴；,s平面和z平面之间的映射关系,s平面宽的水平条带，同样对应整个z平面。,s平面和z平面之间的映射关系,六、z变换与理想抽样信号傅立叶变换的关系,序列的z变换为：,傅立叶变换是拉普拉斯变换在虚轴的特例,理想抽样信号的拉普拉斯变换为：,z变换与傅立叶变换的关系,可得z变换与傅立叶变换之间的关系：,抽样序列在单位圆上的z变换,就等于理想抽样信号傅立叶变换。,单位圆上的z变换称为序列的傅里叶变换(频谱)，也称为离散时间傅里叶变换(DTFT)。,2.6利用Z变换分析信号和系统的频响特性,一、系统函数在线性时不变系统中，h(n)表示系统的单位冲激响应，它反映了系统的特性。H(z)称作线性时不变系统的系统函数。,系统函数,在单位圆上的系统函数就是系统的频率响应。,令，得h(n)的傅立叶变换（系统的频率响应）。,二、因果稳定系统（从z变换收敛域判断）,回顾因果稳定的线性时不变系统的充要条件是？因果：h(n)是因果序列。稳定：h(n)绝对可和。,故，线性时不变系统因果稳定的充要条件是：h(n)是因果序列且绝对可和，即：,h(n)序列绝对可和，即h(n)的傅里叶变换存在，则其z变换收敛域必须包括。,单位圆,因果稳定系统（从z变换收敛域判断）,所以：一个因果稳定系统的系统函数H(z)的收敛域必须在从单位圆到的整个z域内收敛。,或：系统函数的全部极点都必须在单位圆内。,思考：判断系统因果稳定的方法有几种？,解H(z)的极点为z=a,z=a1。（1）收敛域为a1|z|:对应的系统是因果系统，但由于收敛域不包含单位圆，因此是不稳定系统。（2）收敛域为0|z|a:对应的系统是非因果且不稳定系统。（3）收敛域为a|z|a1:对应一个非因果系统，但由于收敛域包含单位圆，因此是稳定系统。,例14、已知分析其因果性和稳定性。,因果稳定系统（从z变换收敛域判断）,三、系统函数和差分方程的关系,线性移不变系统常用差分方程表示：,取z变换得：,系统函数和差分方程的关系,分析：,在已知收敛域的条件下系统的特性由系数bm、ak决定。,在已知收敛域的条件下系统的特性由系数cm、dk决定。,注：仅有差分方程，不能唯一确定系统,四、系统的频率响应的意义,系统单位抽样响应h(n)的傅立叶变换称作系统频率响应。,对于线性时不变系统：,系统的频率响应的意义,若输入为正弦信号，输出也为正弦信号。,五、频率响应的几何确定,1、频率响应的零极点表达式,频率响应的几何确定,频率响应的几何确定,2、几点说明(1)单位圆附近的零点对幅度响应的谷点的位置与深度有明显影响，当零点位于单位圆上时，谷点为零。零点可在单位圆外。(2)单位圆附近的极点对幅度响应的峰点的位置和高度有明显影响，极点越接近单位圆，峰值就越尖锐。极点在单位圆上，系统不稳定。,频率响应的几何确定,零点在单位圆上0和pi处；极点在处。,频率响应的几何确定,解：系统的传输函数为：,解：,极点为z=b，零点为z=0,例16、已知H(z)=1zN，试定性画出系统的幅频特性。解极点：H(z)的极点为z=0，这是一个N阶极点，它不影响系统的幅频响应。零点：零点有N个，由分子多项式的根决定。,即,频率响应的几何确定,N个零点等间隔分布在单位圆上，设N=8，极零点分布如图所示：,频率响应的几何确定,重要公式,傅里叶变换的正变换傅里叶变换的逆变换注意正变换存在的条件是：序列服从绝对可和的条件。,离散傅里叶级数变换对可用于表现周期序列的频谱特性。,周期序列的傅里叶变换如果周期序列的周期是N，则其频谱由N条谱线组成，注意画图时要用带箭头的线段表示。,Z变换的正变换双边Z变换注意收敛域,课堂练习,1、若H（Z）的收敛域包括点，则h（n）一定是_序列。因果,2、线性时不变系统h(n)是因果系统的充要条件是_。h(n)=0,n0或收敛域在某圆的外面,3、线性时不变系统h(n)是稳定系统的充要条件是_。h(n)绝对可和或收敛域包括单位圆,4、时域离散线性时不变系统的系统函数为若要求系统稳定，则a的取值域为_和b的取值域为_。|a|1,|b|1,5、时域离散线性时不变系统的系统函数为若要求系统因果稳定，则a的取值域为_和b的取值域为_。0|a|N）用w(n)表示，w(n)=y(n)的条件是_。LM+N-1,2、对6点有限长序列5，1，3，0，5，2进行向左2点圆周移位后得到序列_。3，0，5，2，5，1,课堂练习,3、离散傅里叶变换中，有限长序列都是作为周期序列的一个周期来表示的，都隐含有周期性的意思。(),对,4、已知长度为N=10的两个有限长序列：,课堂练习,5、假设线性时不变系统的单位脉冲响应h(n)和输入信号x(n)分别用下式表示（1）计算该系统的输出信号y(n)（2）如果对x(n)和h(n)分别进行12点DFT，得到X(k)和H(k),令求y1(n)解：（1）y(n)=1,2,3,4,4,4,4,4,3,2,1（2）y1(n)=1,2,3,4,4,4,4,4,3,2,1,0,4.2基2FFT算法,一、DFT的计算工作量以正变换为例：,计算所有的X(k)就要N2次复数乘法运算,N(N-1)N2次复数加法运算。当N很大时,运算量将是惊人的,如N=1024,则要完成1048576次(一百多万次)运算。这样,难以做到实时处理。,通常x(n)和都是复数,所以计算一个X(k)的值需要N次复数乘法运算,和N-1次复数加法运算。,算法基本思想：,FFT算法就是不断地把长序列的DFT分解成几个短序列的DFT，并利用的周期性和对称性来减少DFT的运算次数。,回顾：的性质,有关系数关系：,利用这些性质可大大减少DFT的计算量，用这种方法计算DFT称为快速傅里叶变换（FFT)。,FFT分按时间抽取(DIT)和按频率抽取(DIF)两大类。,二、按时间抽取法基2FFT算法原理,(一)N/2点DFT1、先将x(n)按n的奇偶分为两组作DFT，设N=2L,不足时可补零。这样有:n为偶数时:n为奇数时:,下面用x1(r)和x2(r)来求x(n)的DFT。,(一)N/2点DFT,(一)N/2点DFT,(一)N/2点DFT,3、X(k)的后一半的确定由于（周期性）,所以:,(一)N/2点DFT,可见,X(k)的后一半，也完全由X1(k),X2(k)确定。,N点的DFT可由两个N/2点的DFT来计算.,(一)N/2点DFT,4、蝶形运算,蝶形运算，运算结构如下：,(一)N/2点DFT,例如N=8时的DFT,可以分解为两个N/2=4点的DFT。具体方法如下:(1)n为偶数时,即分别记作:,(一)N/2点DFT,(2)n为奇数时,分别记作:,(一)N/2点DFT,整个过程如下图所示:,(1)N/2点的DFT运算量:复乘次数:复加次数:(2)两个N/2点的DFT运算量:上述次数的2倍；(3)N/2个蝶形运算的运算量:复乘次数:复加次数:,(一)N/2点DFT,5、运算量分析按奇、偶分组后的计算量：,(一)N/2点DFT,总共运算量:,复乘:,复加:,比较N点DFT的运算量，N点DFT的复乘为N2;复加N(N-1);与分解后相比可知,计算工作量差不多减少一半。,(二)N/4点DFT,由于N=2L,所以N/2仍为偶数,可以进一步把每个N/2点的序列再按其奇偶部分分解为两个N/4的子序列。例如，n为偶数时的N/2点分解为:,分解后的每个序列进行N/4点的DFT,得到,(二)N/4点DFT,从而有：,(二)N/4点DFT,同样对n为奇数时，N/2点分为两个N/4点的序列:,分解后的每个序列进行N/4点的DFT,得到,(二)N/4点DFT,从而有：,(二)N/4点DFT,利用可约性：可将系数化为统一的点数。如下所示：,(二)N/4点DFT,例如，N=8时的DFT可分解为四个N/4的DFT，具体步骤如下:（1）序列分解,(二)N/4点DFT,同样：,分别构成4个N/4点DFT，从而得到X3(0)、X3(1)、X4(0)、X4(1)、X5(0)、X5(1)、X6(0)、X6(1)。,(二)N/4点DFT,（2）蝶形运算由X3(0),X3(1),X4(0),X4(1)进行碟形运算,得到X1(0),X1(1),X1(2),X1(3)。由X5(0),X5(1),X6(0),X6(1)进行碟形运算,得到X2(0),X2(1),X2(2),X2(3)。由X1(0),X1(1),X1(2),X1(3)，X2(0),X2(1),X2(2),X2(3)再进行碟形运算,得到,X(0),X(1),X(2),X(3)X(4),X(5),X(6),X(7),(二)N/4点DFT,(二)N/4点DFT,这样,又一次分解,得到四个N/4点DFT,两级蝶形运算,其运算量又大约减少一半。对于N=8时DFT,N/4点即为两点DFT,也可以用蝶形运算实现，如下所示：,(二)N/4点DFT,也即：,8点DIT-FFT运算流图,这种FFT算法,是在时间上对输入序列次序的奇偶性进行分解的，所以称作按时间抽取的算法（DIT）,三、DIT-FFT与DFT运算量的比较,N=8需三级蝶形运算N=23=8，由此可知，N=2M共需M级蝶形运算,而且每级都由N/2个蝶形运算组成，每个蝶形运算有一次复乘，两次复加。,N点的FFT的运算量为：复乘次数：(N/2)*M=(N/2)log2N复加次数：N*M=Nlog2NN点的DFT直接计算的运算量为：复乘次数：N*N复加次数：N*（N-1）,三、DIT-FFT与DFT运算量的比较,四、DIT-FFT的运算规律及编程思想,1、原位运算,输入数据、中间运算结果和最后输出均用同一存储器,由运算流图可知，基2FFT算法一共有log2N=M级蝶形运算，每一级共N/2个蝶形运算，而且每个蝶形仅与蝶形的2个输入有关，也仅有2个输出值，这4个值均与其它蝶形运算无关，而且2个输入值在计算完输出值后没有其它用途。因此，可用2个输入单元保存2个输出值。即实现所谓原位运算。,四、DIT-FFT的运算规律及编程思想,2、旋转因子的变化规律,N点DIT-FFT运算流图中，每级都有N/2个蝶形。每个蝶形都要乘以旋转因子，p为旋转因子的指数。但各级的旋转因子和循环方式都有所不同。为了编写计算程序，应先找出旋转因子与运算级数的关系。用L表示从左到右的运算级数(L=1，2，M)。第L级共有2L1个不同的旋转因子。N=23=8时的各级旋转因子表示如下：,四、DIT-FFT的运算规律及编程思想,对N=2M的一般情况，第L级的旋转因子为,四、DIT-FFT的运算规律及编程思想,因为所以按上两式确定第L级运算的旋转因子(实际编程序时，L为最外层循环变量)。,四、DIT-FFT的运算规律及编程思想,3蝶形运算规律设序列x(n)经倒序后，存入数组A中。如果蝶形运算的两个输入数据相距B个点，应用原位计算，则蝶形运算可表示成如下形式：式中下标L表示第L级运算，AL(J)则表示第L级运算后的数组元素A(J)的值（即第L级蝶形的输出数据）。而AL1(J)表示第L级运算前A(J)的值（即第L级蝶形的输入数据）。,四、DIT-FFT的运算规律及编程思想,4、编程思想运算规律：第L级中，每个蝶形的两个输入数据相距B=2L1个点；每级有B个不同的旋转因子；同一旋转因子对应着间隔为2L点的2ML个蝶形。,四、DIT-FFT的运算规律及编程思想,5、序列的倒序由图可知，输出X(k)按正常顺序排列在存储单元，而输入是按顺序:这种顺序称作倒序。造成这种排列的原因是序列按下标是否奇偶数抽取而引起的。,四、DIT-FFT的运算规律及编程思想,形成倒序的树状图,四、DIT-FFT的运算规律及编程思想,四、DIT-FFT的运算规律及编程思想,一、算法原理1.N点DFT的另一种表达形式,五、频域抽取法FFT(DIF-FFT),由于故因此X(k)可表为,五、频域抽取法FFT(DIF-FFT),2.N点DFT按k的奇偶分组可分为两个N/2点DFT当k为偶数,即k=2m时,(-1)k=1当k为奇数,即k=2m+1时(-1)k=-1这时X(k)可分为两部分：,k为偶数时：,五、频域抽取法FFT(DIF-FFT),k为奇数时：令,五、频域抽取法FFT(DIF-FFT),3.蝶形运算,X(k)按奇偶k值分为两组，其偶数组是x1(n)的N/2点DFT，奇数组则是x2(n)的N