《泊松求和公式.ppt》由会员分享，可在线阅读，更多相关《泊松求和公式.ppt（71页珍藏版）》请在三一办公上搜索。
1、第三章 付里叶分析,离散付氏级数的数学解释(The Mathematical Explanation of DFS)如前所述，连续信号x(t)或离散信号x(nT1)的频谱：都是连续谱，无法用计算机直接处理。要用计算机研究处理（数字信号处理）必须将：无穷积分(求和)近似为有限积分(求和)；频率离散化。本节主要讨论如何进行近似计算，和实施这些数学计算所需的一些必要的数学基础。,离散付氏级数的数学解释,泊松求和公式(The Poisson Sum Formula)设一周期函数 是以f(t)为主值函数，以T为周期进行周期延拓而得，如下图左图所示。在第二章中已经证明，若F()是f(t)的付氏变换，则：此
2、系时域泊松求和公式，是将无穷积分变换成有限求和的基础。,离散付氏级数的数学解释,下面将用线性系统理论证明泊松求和公式，以此来说明其系统意义。设某系统的传递函数为F()，对应的冲激响应为f(t)，如下图所示。,离散付氏级数的数学解释,若输入为：则由线性系统理论知，其输出为：另一方面，由付氏级数输入信号可展开成：将上式右端通过系统，得到响应为：,离散付氏级数的数学解释,此即时域泊松求和公式。另外，在频域也有类似的公式成立：设 为以F()为主值函数，以1为周期进行周期延拓而得的周期函数，见前图右图。f(t)是F()的付氏反变换，则有频域泊松求和公式：,离散付氏级数的数学解释,f(t)与F()为付氏变
3、换对，而 与 不是付氏变换关系。和 分别是f(t)和F()的周期延拓，其周期分别为T和1。当f(t)为因果函数时，利用频域泊松求和公式(令=0)有：利用泊松公式可以推导出一些有用的恒等式。,离散付氏级数的数学解释,例3-10：已知变换对：试求序列 的付氏展开式。解：由频域泊松公式有：,离散付氏级数的数学解释,令=0和T1=1，有：题给出的变换对和=0和T1=1，可得,离散付氏级数的数学解释,付氏变换与付氏级数(Fourier Transform and Fourier Series)由泊松公式可见，通过X()的样本X(n0)可求得 的付氏级数系数(频谱)，即：频域取样（离散化）后，x(t)就周
4、期化了，而且0=2/T，当0越小，则T越大；当T时，00；若x(t)已知，则可以精确地确定；对于信号g(t)的截短函数：x(t)=g(t)Pa/2(t)，由上式可求得g(t)的付氏变换G()的样本的近似值。,离散付氏级数的数学解释,X()为截短函数的付氏变换，一般情况下，它可近似G()。与时域取样类似，若x(t)严格限制在有限区间内，即x(t)满足：当|t|a/2时，x(t)=0；则有：若Ta，则 可由x(t)唯一地确定；若Ta，将产生混叠。用窗函数w(t)代替Pa/2(t)（矩形窗），通过选择适当的w(t)，可使误差G(n0)-X(n0)减小。这类截短问题在数字信号处理中有许多应用，如数字滤
5、波器设计和频谱分析等。,离散付氏级数的数学解释,付氏级数与离散付氏级数(Fourier Series and DFS)通过对付氏级数与离散付氏级数关系的讨论，将可用一个有限和式来近似计算付氏级数系数。设一个周期函数：若对 进行取样，取N为一任意整数，而且有T=NT1，即在一个周期内取N点，则 的样值 由下式确定：,离散付氏级数的数学解释,式中，WN是1的N元根，称作旋转因子。我们知道，在一个域内取样离散化，则在另一个域内周期化，而k又可写作：K=n+rN，n=0,1,N-1；r=,-1,0,1,并且，旋转因子具有周期性：和，所以上式又可写作：令：，显然 序列是周期的，即：所以有：,离散付氏级数
6、的数学解释,上式说明，周期函数 的样本值 由一组（一个周期）来确定；而且，也由一个周期内的样本值 来确定。的付氏级数系数Cn与 由 来联系。例3-11：设，N9；试求解：因为|n|10时，Cn=0，所以，由Cn与 关系式得：,离散付氏级数的数学解释,一般而言，不能确定Cn，除非仅有N个不为0的。例如三角多项式为：若N2M1，由Cn与 关系式知：Cn与 的图形如下图所示。这时，由 就能求出Cn。由于 由 唯一地确定，从而，可以推定类似三角多项式这样的函数的付氏级数系数Cn能由它的样本值 来确定。亦即可由y(t)的样本求出Y()的样本，从而近似求得Y()。从数学上讲，这就是Y()的数值计算问题。,
7、离散付氏级数的数学解释,数值计算的基本定理(The Basal Theorem of Numerical Computation)对于x(t)的付氏变换：,离散付氏级数的数学解释,的计算基于如下定理：若T是任意常数，N是任意整数，而且有：则对任何m有：式中：由信号理论易知其合理性：时域取样导致频域周期化；频域取样对应时域周期化。,离散付氏级数的数学解释,因为有T=NT1，1=N0，所以无论时域或频域在一个周期均为N个样值，因此，在一个周期内，一组由定理等式定义的N个方程确定了 与 之间的关系。可以由N个 样本值通过求解方程组，求出 的样本值。一般而言，不能唯一确定X(n0)，但若X()满足：X
8、()=0，当|和12，=/T；则有下式成立：上条件说明x(t)是带限信号，而且满足取样定理。,第三章 付里叶分析,若x(t)不是带限的，但只要1足够大，使得当|1/2时的X()可以忽略不计，则当n1/20=N/2时，近似等于X(n0)。但存在一定的混叠误差：X(n0)-。离散付氏变换(Discrete Fourier Transform)DFT引入背景(The Inductive Background of DFT)再次研讨信号时频域关系（见下图）可以发现在四种信号时频关系中，只有第四类信号时频域均是离散的，能进行计算机（数字）处理。第二类信号时域是离散的，但其频域却是连续的，不能直接应用数字
9、信号处理技术，为了能,信号时频关系示意图,离散付氏变换,够处理这类信号，故人为引入离散付立叶变换。分析离散非周期序列（有限长序列）频谱可知：其频谱是周期的，只需研究一个周期；频谱是连续的，需要对其进行离散化，应用频域采样定理可以在不丢失信息的条件下，将其离散化。进行上述处理后即可得到有限长序列的DFT，如上图所示。离散付氏变换定义(Definition of DFT)对一个N点的有限长序列x(n)，由序列的付氏变换定义，有：,离散付氏变换,对正变换，取频谱的一个周期（设取主值周期），按频域采样定理，在一个周期内取N点离散化，令 有：对反变换，因为，故有：,离散付氏变换,DFT定义(Defini
10、tion of DFT)：一N点的有限长序列x(n)，对它的频谱在一个周期内进行N点等间隔取样，则得其的频域序列，两者的关系称为离散付氏变换(Discrete Fourier Transform,DFT)，即：式中，称为旋转因子。,离散付氏变换,DFT的物理意义(The Physical Meaning of DFT)DFT与Z变换的关系：容易证明，有限长序列x(n)的DFT是其在单位圆上Z变换（序列的付氏变换）的N点等间隔采样。由序列的付氏变换的物理意义容易推得DFT的物理意义：N点有限长序列x(n)的(频域序列)DFTX(k)为x(n)的频谱在一个周期里的N点等间隔取样。只要取样满足一定的
11、规律（频域取样定理），即可无失真地反映X(ej)，进而可恢复信号x(n)。,离散付氏变换,DFT的隐含周期性(The Connotative Periodicity of DFT)由信号时频关系的内在本质联系知，对DFT来说，时、频域均是离散的，故其时、频域均是周期序列，即时域对应的是由主值序列x(n)以N为周期进行周期性延拓后得到的周期序列；频域对应的是由主值序列X(k)以N为周期进行周期性延拓后得到的周期序列。由于在处理时仅需主值序列（或者说一个周期的序列），所以在DFT定义中，时频域均限制在主值序列范围内，即：0nN-1；0kN-1。,离散付氏变换,例3-12：考察一个离散系统：离散付氏
12、变换分析器，其差分方程为y(n)-y(n-1)=x(n)。解：易得系统的系统函数为：所以其单位脉冲响应为：若输入为0nN-1的N点有限长序列x(n)，由于x(n)和h(n)均为因果序列，由卷积公式易得：,离散付氏变换,当n=N时，因为有x(N)0，所以有：即当系统输入x(n)时，N时刻系统的输出等于其对应的DFT变换X(k)值，改变系统常数；即可求得对应的DFT：。DFT的基本性质(The Basal Properties of DFT)线性性(Linearity)满足齐次性和叠加原理。设x1(n)和x2(n)是长度分别为N1和N2的有限长序列，若a、b为任意常数，且：,离散付氏变换,取N=m
13、axN1，N2，设X1(k)和X2(k)分别为x1(n)和x2(n)的N点DFT，则N点序列y(n)的DFT为：循环移位性质(The Property of Circular Shift)序列的循环移位(Circular Shift of Sequence)N点有限长序列x(n)的循环移位定义为：式中：x()N表示对x()中序号进行模N取余运算。为0N-1的窗口序列。,离散付氏变换,循环移位的几何意义和过程可如下图所示。m0，左移；m0，右移。循环移位概念也可用圆移位解释，所以有时又称为“圆位移”。下面（如图）用一个N=8，左移3位的圆位移的几何过程进一步说明循环移位。时域循环移位定理(Tim
14、e-Domain Circular Shift Theorem)设x(n)是长为N的有限长序列，y(n)为循环位移m位后的序列，其DFT为：,循环移位几何意义示意图,用圆位移形象说明循环位移,离散付氏变换,频域循环移位定理(Frequency-Domain Circular Shift Theorem)若 则循环卷积定理(Circular Convolution Theorem)循环卷积(Circular Convolution)设有两有限长序列x1(n)和x2(n)，长度分别为N1和N2，取N=maxN1，N2（较短的一个通过补零，达到N长），则两者的循环卷积定义为：,离散付氏变换,或者：记
15、作：循环卷积中x(n)、x1(n)、x2(n)均等长，为N点。从时域直接计算两序列的循环卷积通常有三种方法：利用公式直接计算；同心圆法；波形作图法。同心圆法和波形作图法计算示意见下图。,循环卷积计算图示,x2(1),x2(0),x2(N-1),x1(N-1),x1(0),x1(1),x2(0),x2(1),x2(N-1),x1(N-1),x1(0),x1(1),x1(n),x2(n),x(n),离散付氏变换,时域卷积定理(Time-Domain Circular Convolution Theorem)设x1(n)和x2(n)的N点DFT分别为：若 则有：利用卷积定理可将循环卷积变换到频域利用
16、乘法运算实现，通过DFT的快速计算方法可以大大降低运算量。,离散付氏变换,频域卷积定理(Frequency-Domain Circular Convolution Theorem)与时域对称，也存在频域卷积定理：若则：,离散付氏变换,复共轭序列的DFT(DFT of a Complex Conjugation Sequence)设 为x(n)的复共轭序列，而且有：则:，0kN-1 且 X(N)=X(0)共轭对称性(Conjugation Symmetry)关于圆对称：关于圆周的中轴线对称。写成表达式如下：设xep(n)为有限长共轭对称序列，xop(n)为有限长共轭反对称序列；有：,共轭对称示意
17、,离散付氏变换,对N为偶数，将上式中n换成N/2n，有：下图给出了一个N=8的序列对称示意。序列的共轭对称性(Conjugation Symmetry of Sequences)任意序列都可写成其共轭对称分量与共轭反对称分量之和；利用序列与复共轭序列DFT间的关系，可导出序列DFT的对称特性。,复序列共轭对称示意图,离散付氏变换,如果序列x(n)的DFT为X(k)，则x(n)的实部和纯虚部的DFT分别为X(k)的共轭对称分量和共轭反对称分量。即，如果：x(n)=xr(n)+jxi(n)；X(k)DFTx(n)Xep(k)Xop(k)，则：DFTxr(n)=Xep(k)；DFTjxi(n)=Xo
18、p(k)如果序列x(n)的DFT为X(k)，则x(n)的共轭对称分量和共轭反对称分量的DFT分别为X(k)的实部和纯虚部。即，如果：x(n)=xep(n)+xop(n)；X(k)DFTx(n)XR(k)jXI(k)，则：DFTxep(n)=ReX(k)=XR(k)DFTxop(n)=jImX(k)=jXI(k)由序列DFT的共轭关系，可以推出各类序列DFT的对称关系，它们可总结如下表所示。,序列共轭对称性总结及示例,离散付氏变换,1、若x(n)为实函数，则X(k)是共轭偶对称的；x(n)为共轭偶对称的，则X(k)是实函数，从而有：实、偶实、偶2、若x(n)为共轭奇对称的，则X(k)是虚函数；x
19、(n)为实函数，则X(k)是共轭偶对称的，即其虚部为奇函数；从而有：实、奇虚、奇3、因为X(k)=DFTjxiep(n)jDFTxiep(n)，由“1”得DFTxiep(n)是实偶函数，即X(k)为虚偶函数，从而有：虚、偶虚、偶4、因为X(k)DFTjxiop(n)jDFTxiop(n)，由“2”得DFTxiop(n)是虚奇函数，即X(k)为实奇函数，从而有：虚、奇实、奇,第三章 付里叶分析,利用序列DFT的对称关系可以减少DFT的运算量，一般而言，只需计算大约一半点数的DFT，另一半可由对称性求得。序列对称性是DFT和DFS快速算法（FFT)的重要基础。频率域采样(Frequency Sam
20、pling)由时域采样定理知：在时域只要满足采样定理（即时域采样点足够多）即可用采样序列无失真地恢复原始信号（用采样序列代表原始连续信号）。由时频域的对称性原理推断，在频域也应存在类似的采样定理。即满足何种条件可以对频域连续函数采样，使得采样序列可以无失真地恢复原始频域函数。,频率域采样,频域采样定理(Frequency Sampling Theorem)：对M点有限长序列x(n)，若X(k)为x(n)频域函数的采样序列，只有当采样点数NM时，才有：即可由频域采样序列X(k)恢复原始频域连续函数，进而可恢复原始时域序列x(n)。若采样点数NM，时域将发生混叠现象（失真），不能无失真地恢复原始信
21、号；有限长序列DFT是建立在频域采样定理基础上的，由此可以解释为何DFT用N点对频谱等间隔采样；由频域采样定理可以推断无限长序列的DFT不存在（无意义），因为此时无论频域采样点数选取多大，时域都将发生混叠。,频率域采样,X(z)的内插公式及内插函数(Interpolation Function and Interpolation Formula of X(z)满足频域采样定理后，x(n)的DFT（X(k)）可以无失真地恢复（表示）x(n)，所以它也应能表示它的Z变换X(z)。用X(k)表示X(z)的表达形式称为X(z)的内插公式；在内插公式中描述采样点间轨迹关系的函数称为内插函数。利用IDFT
22、表达式和有限项级数求和公式容易推导得到X(z)的内插公式为：式中：为内插函数。,频率域采样,利用序列z变换与付氏变换的关系，由X(z)的内插公式容易求得 的内插公式和内插函数为：利用尤拉公式和，对内插函数进行恒等变换：,频率域采样,所以，的内插公式和内插函数又可写作：,第三章 付里叶分析,此表达方式将在数字信号处理介绍的频率采样FIR滤波器设计中得到应用。快速付氏变换(Fast Fourier Transform)引言(Introduction)DFT是数字（离散）信号中的一种重要变换，但从DFT定义可以容易得到直接计算一个N点的DFT需要：N2次复数乘法；N(N-1)次复数加法。即其运算量随
23、着N按平方增加，当N较大时，其计算量非常大，直接用DFT进行实时计算或谱分析是不切实际的。,快速付氏变换,1965年库利(J.W.Cooley)和图基()发现DFT的快速算法后，DFT才得到实际的应用。自1965年后，DFT的快速计算算法的研究得到空前的发展，除了Cooley-Tukey算法；Sande-Tukey算法外，还有许多其它算法，如：Winograd算法；余弦变换快速算法；Walsh变换；数论变换等。基2FFT算法(The Algorithm of Base 2 FFT)FFT的基本思想(The Basal Thought of FFT)长为N的序列x(n)的DFT定义：,快速付氏变
24、换,式中，为旋转因子，具有如下特性：周期性：对称性：FFT的基本思想(The Basal Thought of FFT)：利用 的周期性和对称性，可使DFT运算中的某些项合并；因为DFT的运算量与N2成正比，若将DFT运算尽可能地分解成小N点的DFT的组合，这样可以降低运算量。,快速付氏变换,基2时域抽取FFT(Cooley-Tukey算法，DIT-FFT)基2FFT：通过补零使N满足：N=2M，M为自然数;时域抽取原理(Time-Domain Decimation Theory)按n的奇偶将x(n)分解为两个N/2点的子序列：则x(n)的DFT可写作：,快速付氏变换,再由 的周期性和对称性可
25、求的DFT的后一半：由周期性：得：,快速付氏变换,和再由对称性：从而有：这样，一个N点的DFT被分解成了两个N/2点的DFT线性组合：将DFT分解M次，最后为2点DFT，完成FFT分解。,快速付氏变换,蝶形运算表示(The Denotation of Butterfly Computation)上式定义的运算称为蝶形运算(Butterfly Computation)，它可由下图形象表示，利用蝶形运算符号可将FFT运算用流图描述。,一个蝶形运算由一次复乘法；两次复加法实现。向上加；向下减。,快速付氏变换,N=8的Cooley-Tukey法示例一个N点基2FFT算法可以通过分解M次，每次用N/2个
26、蝶形运算表示。例3-13：N=8的时域抽取FFT通过3次抽取实现。后面三个图分别给出了8点时域抽取FFT的一、二、三次分解过程。由分解完成的8点时域FFT流图可以看出流图由M=3级构成，每一级由N/2个蝶形组成，每级蝶形的旋转因子均有其规律。,8 点DFT的第一次时域抽取分解图,8 点DFT的第二次时域抽取分解图,N点DIT-FFT运算流图（N=8）,快速付氏变换,Cooley-Tukey算法的规律及特点(Rules and Properties of Cooley-Tukey Algorithm)规律：流图结构(The Structure of Flow-Graph)N=2M点基2FFT算法
27、流图结构共有M级，每级有N/2个蝶形；输入序列的倒序(The Reverse order of Input Sequence)按M位二进制“码位倒置”规律扰乱输入序列的角标顺序。例3-14：设N=8，M=3，有：,快速付氏变换,蝶距(The Space of Butterfly Input)定义：蝶形输入两信号点间的节点数称为蝶距。式中：N为点数；M为级数；l为级号。旋转因子各级蝶形有 组；每组有 个，而且组中 的幂m按差 由0递增。由这些规律可以很容易地画出N=2M点的基2FFT运算流图，从而用软件编程或硬件系统实现信号的DFT运算。,快速付氏变换,特点：运算次数(Number of Com
28、putation)每个蝶形最多需要一次复乘法、二次复加法。这样一个N点基2FFT的运算量最多为：复乘法：复加法：与直接运算比较：复乘法：,快速付氏变换,复加法：例如，N=1024210，M=10，有：N越大，FFT效率越高。原位运算(Original Computation)在运算中无需中间寄存器。仅需（N+N/2）个存储单元。,快速付氏变换,IDFT的运算(Computation of IDFT)将运算中的旋转因子 改为，计算完后再乘1/N。此法需要修改FFT子程序；由IDFT表达式有：由上式可以看出，若先将X(k)取共轭，然后直接调用FFT子程序（或用与正变换相同的专用硬件），再将结果取共
29、轭并乘以1/N，即可求出X(k)的IDFT。此法的特点是无需对软件或硬件做修改，可共用。,快速付氏变换,基2频域抽取FFT(Sande-Tukey算法，DIF-FFT)抽取原理(Decimation Theory)将x(n)分成前N/2和后N/2两半，即：这样，DFT可写作：,快速付氏变换,将k分成偶和奇数，即将X(k)分解成奇偶两组，在偶数组中k=2r,则；在奇数组中k=2r+1,则；有：,快速付氏变换,至此，X(k)已被分解成了两个N/2点的DFT，当然，在计算N/2点DFT之前还需计算如下蝶形运算：,快速付氏变换,与时域抽取类似，继续分解M次，直到2点DFT。频域抽取的蝶形运算(Butterfly Computation in Frequency-Domain)与时域抽取类似，上式蝶形运算也可用一种蝶形描述，如下图所示，其运算次数与时域蝶形相同，区别在于旋转因子相乘的位置不同。,快速付氏变换,N=8的频域抽取法示例 例3-15：以下二图说明了8点频域抽取FFT第一次抽取和第二次抽取的过程，再后一图为8点频域抽取FFT的完整信号流图。,DIF-FFT一次分解运算流图（N=8）,DIF-FFT二次分解运算流图（N=8）,DIF-FFT运算流图（N=8）,
