泊松求和公式.pptx

《泊松求和公式.pptx》由会员分享，可在线阅读，更多相关《泊松求和公式.pptx（71页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、离散付氏级数的数学解释泊松求和公式(The Poisson Sum Formula)设一周期函数 是以f(t)为主值函数，以T为周期进行周期延拓而得，如下图左图所示。在第二章中已经证明，若F()是f(t)的付氏变换，则：此系时域泊松求和公式，是将无穷积分变换成有限求和的基础。第1页/共71页离散付氏级数的数学解释下面将用线性系统理论证明泊松求和公式，以此来说明其系统意义。设某系统的传递函数为F()，对应的冲激响应为f(t)，如下图所示。f(t)F()第2页/共71页离散付氏级数的数学解释若输入为：则由线性系统理论知，其输出为：另一方面，由付氏级数输入信号可展开成：将上式右端通过系统，得到响应为

2、：第3页/共71页离散付氏级数的数学解释此即时域泊松求和公式。另外，在频域也有类似的公式成立：设 为以F()为主值函数，以 1为周期进行周期延拓而得的周期函数，见前图右图。f(t)是F()的付氏反变换，则有频域泊松求和公式：第4页/共71页离散付氏级数的数学解释f(t)与F()为付氏变换对，而 与 不是付氏变换关系。和 分别是f(t)和F()的周期延拓，其周期分别为T和 1。当f(t)为因果函数时，利用频域泊松求和公式(令=0)有：利用泊松公式可以推导出一些有用的恒等式。第5页/共71页离散付氏级数的数学解释例3-10：已知变换对：试求序列 的付氏展开式。解：由频域泊松公式有：第6页/共71页

3、离散付氏级数的数学解释令=0和T1=1，有：题给出的变换对和题给出的变换对和=0=0和和T T1 1=1=1，可得，可得第7页/共71页离散付氏级数的数学解释付氏变换与付氏级数(Fourier Transform and Fourier Series)由泊松公式可见，通过X()的样本X(n 0)可求得 的付氏级数系数(频谱)，即：频域取样（离散化）后，x(t)就周期化了，而且 0=2/T，当 0越小，则T越大；当T时，00；若x(t)已知，则可以精确地确定 ；对于信号g(t)的截短函数：x(t)=g(t)Pa/2(t)，由上式可求得g(t)的付氏变换G()的样本的近似值。第8页/共71页离散付

4、氏级数的数学解释X()为截短函数的付氏变换，一般情况下，它可近似G()。与时域取样类似，若x(t)严格限制在有限区间内，即x(t)满足：当|t|a/2时，x(t)=0；则有：若Ta，则 可由x(t)唯一地确定；若T10时，Cn=0，所以，由Cn与 关系式得：第12页/共71页离散付氏级数的数学解释一般而言，不能确定Cn，除非仅有N个不为0的 。例如三角多项式为：若N2M1，由Cn与 关系式知：Cn与 的图形如下图所示。这时，由 就能求出Cn。由于 由 唯一地确定，从而，可以推定类似三角多项式这样的函数的付氏级数系数Cn能由它的样本值 来确定。亦即可由y(t)的样本求出Y()的样本，从而近似求得

5、Y()。从数学上讲，这就是Y()的数值计算问题。第13页/共71页离散付氏级数的数学解释数值计算的基本定理(The Basal Theorem of Numerical Computation)对于x(t)的付氏变换：第14页/共71页离散付氏级数的数学解释的计算基于如下定理：若T是任意常数，N是任意整数，而且有：则对任何m有：式中：由信号理论易知其合理性：时域取样导致频域周期化；频域取样对应时域周期化。第15页/共71页离散付氏级数的数学解释因为有T=NT1，1=N 0，所以无论时域或频域在一个周期均为N个样值，因此，在一个周期内，一组由定理等式定义的N个方程确定了 与 之间的关系。可以由N

6、个 样本值通过求解方程组，求出 的样本值。一般而言，不能唯一确定X(n 0)，但若X()满足：X()=0，当|和 12，=/T；则有下式成立：上条件说明x(t)是带限信号，而且满足取样定理。第16页/共71页第三章 付里叶分析若x(t)不是带限的，但只要 1足够大，使得当|1/2时的X()可以忽略不计，则当n0，左移；m0，右移。循环移位概念也可用圆移位解释，所以有时又称为“圆位移”。下面（如图）用一个N=8，左移3位的圆位移的几何过程进一步说明循环移位。时域循环移位定理时域循环移位定理(Time-Domain Circular Shift Theorem)设x(n)是长为N的有限长序列，y(

7、n)为循环位移m位后的序列，其DFT为：第27页/共71页循环移位几何意义示意图第28页/共71页用圆位移形象说明循环位移第29页/共71页离散付氏变换频域循环移位定理(Frequency-Domain Circular Shift Theorem)若 则循环卷积定理循环卷积定理(Circular Convolution Theorem)循环卷积(Circular Convolution)设有两有限长序列x1(n)和x2(n)，长度分别为N1和N2，取N=maxN1，N2（较短的一个通过补零，达到N长），则两者的循环卷积定义为：第30页/共71页离散付氏变换或者：记作：循环卷积中x(n)、x1

8、(n)、x2(n)均等长，为N点。从时域直接计算两序列的循环卷积通常有三种方法：利用公式直接计算；同心圆法；波形作图法。同心圆法和波形作图法计算示意见下图。第31页/共71页循环卷积计算图示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)第32页/共71页离散付氏变换时域卷积定理(Time-Domain Circular Convolution Theorem)设x1(n)和x2(n)的N点DFT分别为：若 则有：利用卷积定理可将循环卷积变换到频域利用乘法运算实现，通过DFT的快

9、速计算方法可以大大降低运算量。第33页/共71页离散付氏变换频域卷积定理(Frequency-Domain Circular Convolution Theorem)与时域对称，也存在频域卷积定理：若则：第34页/共71页离散付氏变换复共轭序列的DFT(DFT of a Complex Conjugation Sequence)设 为x(n)的复共轭序列，而且有：则:，0kN-1 且 X(N)=X(0)共轭对称性(Conjugation Symmetry)关于圆对称：关于圆周的中轴线对称。写成表达式如下：设xep(n)为有限长共轭对称序列，xop(n)为有限长共轭反对称序列；有：第35页/共7

10、1页共轭对称示意71263516523404N=80N=7对称轴第36页/共71页离散付氏变换对N为偶数，将上式中n换成N/2n，有：下图给出了一个N=8的序列对称示意。序列的共轭对称性(Conjugation Symmetry of Sequences)任意序列都可写成其共轭对称分量与共轭反对称分量之和；利用序列与复共轭序列DFT间的关系，可导出序列DFT的对称特性。第37页/共71页复序列共轭对称示意图第38页/共71页离散付氏变换如果序列x(n)的DFT为X(k)，则x(n)的实部和纯虚部的DFT分别为X(k)的共轭对称分量和共轭反对称分量。即，如果：x(n)=xr(n)+jxi(n)；

11、X(k)DFTx(n)Xep(k)Xop(k)，则：DFTxr(n)=Xep(k)；DFTjxi(n)=Xop(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的对称关系，它们可总结如下表所示。第39页/共71页序列共轭对称性总结及示例第40页/共71页离散付氏变换1、若x(n)为实函数，则X

12、(k)是共轭偶对称的；x(n)为共轭偶对称的，则X(k)是实函数，从而有：实、偶实、偶2、若x(n)为共轭奇对称的，则X(k)是虚函数；x(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)为实奇函数，从而有：虚、奇实、奇第41页/共71页第三章 付里叶分析利用序列DFT的对称关系可以减少DFT的运算量，一般

13、而言，只需计算大约一半点数的DFT，另一半可由对称性求得。序列对称性是DFT和DFS快速算法（FFT)的重要基础。频率域采样(Frequency Sampling)由时域采样定理知：在时域只要满足采样定理（即时域采样点足够多）即可用采样序列无失真地恢复原始信号（用采样序列代表原始连续信号）。由时频域的对称性原理推断，在频域也应存在类似的采样定理。即满足何种条件可以对频域连续函数采样，使得采样序列可以无失真地恢复原始频域函数。第42页/共71页频率域采样频域采样定理(Frequency Sampling Theorem)：对M点有限长序列x(n)，若X(k)为x(n)频域函数的采样序列，只有当采

14、样点数NM时，才有：即可由频域采样序列X(k)恢复原始频域连续函数，进而可恢复原始时域序列x(n)。若采样点数NM，时域将发生混叠现象（失真），不能无失真地恢复原始信号；有限长序列DFT是建立在频域采样定理基础上的，由此可以解释为何DFT用N点对频谱等间隔采样；由频域采样定理可以推断无限长序列的DFT不存在（无意义），因为此时无论频域采样点数选取多大，时域都将发生混叠。第43页/共71页频率域采样X(z)的内插公式及内插函数(Interpolation Function and Interpolation Formula of X(z)满足频域采样定理后，x(n)的DFT（X(k)）可以无失真

15、地恢复（表示）x(n)，所以它也应能表示它的Z变换X(z)。用X(k)表示X(z)的表达形式称为X(z)的内插公式；在内插公式中描述采样点间轨迹关系的函数称为内插函数。利用IDFT表达式和有限项级数求和公式容易推导得到X(z)的内插公式为：式中：为内插函数。第44页/共71页频率域采样利用序列z变换与付氏变换的关系，由X(z)的内插公式容易求得 的内插公式和内插函数为：利用尤拉公式和 ，对内插函数进行恒等变换：第45页/共71页频率域采样所以，的内插公式和内插函数又可写作：第46页/共71页第三章 付里叶分析此表达方式将在数字信号处理介绍的频率采样FIR滤波器设计中得到应用。快速付氏变换(Fa

16、st Fourier Transform)引言(Introduction)DFT是数字（离散）信号中的一种重要变换，但从DFT定义可以容易得到直接计算一个N点的DFT需要：N2次复数乘法；N(N-1)次复数加法。即其运算量随着N按平方增加，当N较大时，其计算量非常大，直接用DFT进行实时计算或谱分析是不切实际的。第47页/共71页快速付氏变换1965年库利和图基发现DFT的快速算法后，DFT才得到实际的应用。自1965年后，DFT的快速计算算法的研究得到空前的发展，除了Cooley-Tukey算法；Sande-Tukey算法外，还有许多其它算法，如：Winograd算法；余弦变换快速算法；Wa

17、lsh变换；数论变换等。基2FFT算法(The Algorithm of Base 2 FFT)FFT的基本思想(The Basal Thought of FFT)长为N的序列x(n)的DFT定义：第48页/共71页快速付氏变换式中，为旋转因子，具有如下特性：周期性：对称性：FFT的基本思想(The Basal Thought of FFT)：1)利用 的周期性和对称性，可使DFT运算中的某些项合并；2)因为DFT的运算量与N2成正比，若将DFT运算尽可能地分解成小N点的DFT的组合，这样可以降低运算量。第49页/共71页快速付氏变换基2时域抽取FFT(Cooley-Tukey算法，DIT-F

18、FT)基2FFT：通过补零使N满足：N=2M，M为自然数;时域抽取原理(Time-Domain Decimation Theory)按n的奇偶将x(n)分解为两个N/2点的子序列：则x(n)的DFT可写作：第50页/共71页快速付氏变换再由 的周期性和对称性可求的DFT的后一半：由周期性：得：第51页/共71页快速付氏变换和再由对称性：从而有：这样，一个N点的DFT被分解成了两个N/2点的DFT线性组合：将DFT分解M次，最后为2点DFT，完成FFT分解。第52页/共71页快速付氏变换蝶形运算表示(The Denotation of Butterfly Computation)上式定义的运算称

19、为蝶形运算(Butterfly Computation)，它可由下图形象表示，利用蝶形运算符号可将FFT运算用流图描述。一个蝶形运算一个蝶形运算由一次复乘法；由一次复乘法；两次复加法实两次复加法实现。向上加；现。向上加；向下减。向下减。第53页/共71页快速付氏变换N=8的的Cooley-Tukey法示例法示例一个一个N点基点基2FFT算法可以通过分解算法可以通过分解M次，每次用次，每次用N/2个蝶形运算表示。个蝶形运算表示。例例3-13：N=8的时域抽取的时域抽取FFT通过通过3次抽取实现。次抽取实现。后面三个后面三个图分别给出了图分别给出了8点时域抽取点时域抽取FFT的一、二、的一、二、三

20、次分解过程。由分解完成的三次分解过程。由分解完成的8点时域点时域FFT流图可流图可以看出流图由以看出流图由M=3级构成，每一级由级构成，每一级由N/2个蝶形组个蝶形组成，每级蝶形的旋转因子均有其规律。成，每级蝶形的旋转因子均有其规律。第54页/共71页8 点DFT的第一次时域抽取分解图第55页/共71页8 点DFT的第二次时域抽取分解图第56页/共71页N点DIT-FFT运算流图（N=8）第57页/共71页快速付氏变换Cooley-Tukey算法的规律及特点(Rules and Properties of Cooley-Tukey Algorithm)规律：流图结构(The Structure

21、 of Flow-Graph)N=2M点基2FFT算法流图结构共有M级，每级有N/2个蝶形；输入序列的倒序(The Reverse order of Input Sequence)按M位二进制“码位倒置”规律扰乱输入序列的角标顺序。例3-14：设N=8，M=3，有：第58页/共71页快速付氏变换蝶距(The Space of Butterfly Input)定义：蝶形输入两信号点间的节点数称为蝶距。式中：N为点数；M为级数；l为级号。旋转因子各级蝶形有 组 ；每组有 个 ，而且组中 的幂m按差 由0递增。由这些规律可以很容易地画出N=2M点的基2FFT运算流图，从而用软件编程或硬件系统实现信号

22、的DFT运算。第59页/共71页快速付氏变换特点：运算次数(Number of Computation)每个蝶形最多需要一次复乘法、二次复加法。这样一个N点基2FFT的运算量最多为：复乘法：复加法：与直接运算比较：复乘法：第60页/共71页快速付氏变换复加法：例如，N=1024210，M=10，有：N越大，FFT效率越高。原位运算(Original Computation)在运算中无需中间寄存器。仅需（N+N/2）个存储单元。第61页/共71页快速付氏变换IDFT的运算(Computation of IDFT)1)将运算中的旋转因子 改为 ，计算完后再乘1/N。此法需要修改FFT子程序；2)由

23、IDFT表达式有：由上式可以看出，若先将X(k)取共轭，然后直接调用FFT子程序（或用与正变换相同的专用硬件），再将结果取共轭并乘以1/N，即可求出X(k)的IDFT。此法的特点是无需对软件或硬件做修改，可共用。第62页/共71页快速付氏变换基基2频域抽取频域抽取FFT(Sande-Tukey算法算法，DIF-FFT)抽取原理(Decimation Theory)将x(n)分成前N/2和后N/2两半，即：这样，DFT可写作：第63页/共71页快速付氏变换将k分成偶和奇数，即将X(k)分解成奇偶两组，在偶数组中k=2r,则 ；在奇数组中k=2r+1,则 ；有：第64页/共71页快速付氏变换至此，

24、X(k)已被分解成了两个N/2点的DFT，当然，在计算N/2点DFT之前还需计算如下蝶形运算：第65页/共71页快速付氏变换与时域抽取类似，继续分解M次，直到2点DFT。频域抽取的蝶形运算(Butterfly Computation in Frequency-Domain)与时域抽取类似，上式蝶形运算也可用一种蝶形描述，如下图所示，其运算次数与时域蝶形相同，区别在于旋转因子相乘的位置不同。第66页/共71页快速付氏变换N=8的频域抽取法示例的频域抽取法示例 例例3-15：以下二图说明了：以下二图说明了8点频域抽取点频域抽取FFT第一次第一次抽取和第二次抽取的过程，再后一图为抽取和第二次抽取的过程，再后一图为8点频域抽点频域抽取取FFT的完整信号流图。的完整信号流图。第67页/共71页DIF-FFT一次分解运算流图（N=8）第68页/共71页DIF-FFT二次分解运算流图（N=8）第69页/共71页DIF-FFT运算流图（N=8）第70页/共71页感谢您的观看。第71页/共71页