《现代通信理论》课件第2章.ppt

1、第章信源编码理论 第第2 2章信源编码理论章信源编码理论2.1波形编码理论波形编码理论2.2时域波形编码时域波形编码2.3频域波形编码频域波形编码2.4参数编码参数编码2.5图像压缩编图像压缩编2.6数据通信和数据加密编码数据通信和数据加密编码习题习题第章信源编码理论 2.1波形编码理论波形编码理论2.1.1信源的数学模型信源的数学模型任何信源的输出都是随机的,也就是说,信源输出是用统计方法来定性的;否则,如果信源输出已确知,就没有必要传输了。本节将分别以离散和模拟信源的数学模型为前提讨论这两种信源。第章信源编码理论 最简单的离散信源是由有限字符集的字符组成的序列。例如,一个二进制信源发出10

2、0101110形式的二进制字符串,它的字符集仅包含两个字符0,1。更一般地讲,若字符集含有L个可能的字符,如x1,x2,xL,则信源发出的是该字符集里的字符串。为了构造离散信源的数学模型,假定字符集x1,x2,xL的每个字符都有给定的发生概率Pk,即第章信源编码理论 Pk=P(X=xk)1kL这里 11LkkP下面讨论离散信源的两种数学模型。(1)离散无记忆信源(DMS)。假设信源的输出序列是统计独立的,即当前的输出字符与所有过去和将来的输出字符统计无关。凡信源输出序列各字符间满足统计独立条件,则称其为无记忆的,这样的信源称为离散无记忆信源(DMS)。第章信源编码理论(2)平稳离散信源。假如离

3、散信源的输出是统计相关的,可基于统计上的平稳来构造数学模型。根据平稳的定义,如果长度为n的两个序列a1,a2,an和a1+m,a2+m,an+m的联合概率在所有n1和所有移序m的情况下均相等,那么该离散信源是平稳的。换言之,信源输出的任何两个随意长度的序列的联合概率不随时间起点位置的移动而变化。第章信源编码理论 模拟信源具有输出波形x(t),它是随机过程X(t)的一个样本函数。假设X(t)是一个平稳随机过程,其自相关函数为Rxx(),功率谱密度是Pxx(f)。当X(t)是带限的随机过程,即|f|fm时满足条件Pxx(f)=0,可以用抽样定理来表示X(t):)2fnt(2)2(2sin)2()(

4、mmmmmffntffnXtX(2.1)第章信源编码理论 这里,X(n/2fm)表示以每秒fs=2fm个样值的奈奎斯特速率对过程X(t)抽样。这样,利用抽样定理可把模拟信源的输出转换成等效的离散时间信源。于是对于所有m1,都可用联合概率密度函数p(x1,x2,xm)从统计角度描述信源输出的特性,此处Xn=X(n/2fm),1nm,Xn是与X(t)抽样对应的随机变量。我们注意到,由平稳信源得到的每个输出抽样X(n/2fm)通常是模拟量,可以把各个采样值量化成一组离散的幅度,而这种量化处理必然导致精度损失。第章信源编码理论 2.1.2离散信源编码离散信源编码前面我们介绍了离散随机变量X所含信息量的

5、度量方法。当X是一个离散信源的输出时,信源熵H(X)代表信源发出的平均信息量。本节将讨论信源输出的编码方法,即用二进制数字序列来表示信源输出的方法。有一种衡量信源编码效率的办法是把表示信源每一个输出字符所用的平均二进制数字的个数与信源熵H(X)比较。第章信源编码理论 初看起来,有限字符集离散信源的编码相对来说是一个简单问题,然而,只有当信源无记忆时才是这样,即由信源发出的前后符号间统计独立,每个符号可以单独编码。这种离散无记忆信源(DMS)是能够想到的最简单的物理信源模型,但极少有实际信源是与此理想数学模型相符的。第章信源编码理论 例如,从一台打印英语课文的机器里发出的前后字符被认为是统计相关

6、的;另一方面,如果从机器里送出的是用Fortran语言编写的程序,那么输出符号序列之间的相关性要小得多。但不管是什么情况,都可以证明:对字符组编码总是比对单个字符编码效率高。如果使字符组足够长,则信源中的每个输出字符所用的二进制数字的平均个数可无限地趋近于信源熵。第章信源编码理论 1.离散无记忆信源的编码离散无记忆信源的编码假设有一个DMS,每s秒产生一个字符或符号,每个符号选自有限字符集xi(i=1,2,L),各符号发生的概率分别是P(xi)(i=1,2,L)。以“bit/信源符号”为单位,该DMS的熵是1()()lb()lbLiiiH XP xP xL(2.2)第章信源编码理论 当各符号等

7、概时,上式的等号成立。每信源符号的平均比特数是H(X),以b/s为单位计算的信源速率是H(X)/s。1)固定长度码字首先讨论一个分组编码的方案,为每个符号制定惟一的R位二进制数字串与之对应。因为每个符号有L个可能的取值,当L是2的幂次时,每个符号为了能惟一编码所需要的二进制位数应是R=lbL(2.3)第章信源编码理论 当L不是2的幂次时,应有R=lbL+1(2.4)式中,x表示小于x的最大整数(取整)。在上述情况下,每个符号的码率为R(以比特为单位),并且由于H(X)lbL,可知RH(X)。第章信源编码理论 DMS的编码效率定义为H(X)/R之比。我们看到,当L是2的幂次且信源符号等概时,R=

8、H(X)成立,这时每个符号R比特的固定长度码达到了100%的效率。但当L不是2的幂次而信源符号依然等概时,R与H(X)的差别至多是每符号1比特。当lbL1时,这种编码方式的效率仍然较高。另一方面,当L很小时,可以一次对J个符号的序列编码,这样的固定长度码能提高效率。为了实现要求的编码,需要LJ个不同的码字。若采用二进制数字序列,N长的序列可表示2N个可能的码字,所以N的选择必须满足条件第章信源编码理论 NJ lbL因此,满足要求的N的最小整数值是N=J lbL+1 (2.5)于是,每信源符号的平均比特数是N/J=R,与上述逐符号编码相比,(由取整造成的)效率降低约可减小一个因子1/J。如果以J

9、H(X)/N的比值来度量编码效率,那么当J足够大时,编码效率可任意地趋近于1。第章信源编码理论 下面,我们试图降低码率R,在编码过程中放宽“惟一性”这个条件,例如假设在LJ种符号取值中只有一部分是一一对应编码的。说得更具体些,选择2N1种最有可能的J符号组,让它们一一对应编码,而剩余的LJ(2N1)种J符号组统统编成余下的码字。采用这种处理方式后,每当遇到低概率符号组编成那个码字时,就会导致译码失败或译码差错概率(失真),可以用Pe代表这个差错概率。对于这种分组的编码方法,香农于1948年提出了以下信源编码定理。第章信源编码理论 2)信源编码定理若X是有限熵离散无记忆信源的字符集,由信源发出的

10、J个字符组成的分组编成长度为N的二进制码字。对于任何0,都可使分组译码的差错概率Pe任意小,只要()NRH XJ(2.6)第章信源编码理论 以及J足够大。反之,如果RH(X)(2.7)那么当J足够大时,Pe可以任意地趋近于1。从上述结论可看到,想要以任意小的译码差错概率对DMS信源的输出编码,每个符号的平均比特数是以信源熵为下边界的。另一方面,如果RL),可把一种称为K均值算法(这里K=L)的迭代簇聚算法运用于这组训练矢量。这种算法依靠迭代把M个训练矢量分割成L簇,使最优化的两个必要条件都能满足。第章信源编码理论 K均值算法描述如下:步骤1初始化,设置迭代次数i=0。选择一组输出矢量 k,1k

11、L。步骤2根据下列准则,将训练矢量X(m),1mM归类合并成簇Ck。最邻近点准则:若对于任何kj,均有d(X,k(i)d(X,j(i),则XCk(i)。XXX第章信源编码理论 步骤3令i=i+1,按下式重新计算落在每一簇的训练矢量的质心k(i):X1()()(1)kkCkimkLMXXX重新计算输出矢量,并计算本次(第i次)迭代所得结果的失真D(i)。步骤4如果两次迭代所得平均失真之差D(i1)D(i)相对而言足够小,迭代停止;否则,转到步骤2。第章信源编码理论 一旦选定了称为码本的输出矢量组k,1kL,每一个信号矢量X(m)就都量化成其中之一,使得以所用的失真量度衡量时,信号矢量与该点最近。

12、如果一一计算X(m)到L个可能的输出矢量k的距离,这个过程就是所谓的全搜索。设计算每一个距离需n次乘、加运算,则每一个输入矢量全搜索所需的乘加运算量为XX第章信源编码理论 C=nL(2.74)如果把L选成是2的幂次,lbL就是每一个矢量所需的比特数。如果用R表示每抽样(X(m)每分量或每维)的比特率,有nR=lbL,因此计算量是C=n2nR(2.75)注意,运算量随维数和每维的比特数R上升。第章信源编码理论 采用次优的算法可降低与全搜索相关的计算量。一个特别简单的办法是根据二进树搜索构造一个码本。二进树搜索用分级簇聚的方法分割n维空间,使搜索的运算量降低到正比于lbL。这种方法先用K均值(K=

13、2)算法将n维试验矢量分成两个区域,这样我们就得到了两个区域以及它们的重心,比如1和2。XX第章信源编码理论 下一步,采用K=2的K均值算法将落入第一个区域的点再分成两个区域,我们又得到两个重心,比如11和12。在第二个区域也这样做,得到另两个重心21和22。于是一个n维区域被分成了4个区域,每个区域都有相应的重心。重复这样的过程,直到将n维空间划分成L=2nR个区域,此处R是每码矢的比特数。对应的码矢可以被看成是二进树的终节点,如图2.10所示。XXXX第章信源编码理论 图 2.10用于二进搜索矢量量化的均匀树第章信源编码理论 二进树搜索的计算量是C=2n lbL=2n2R与全搜索中运算量成

14、指数关系上升相比,这种方法的运算量与R(每维的比特率)成线性关系。虽然运算量大大减少,然而存储(重心)矢量所需要的内存需从nL增加到2nL,因为我们现在除存储终节点矢量外,还必须存储中间节点矢量。第章信源编码理论 二进树搜索算法产生的是一棵“均匀树”。一般而言,这种方法所得码字与用全搜索方法所得码字相比具有较大的误差,从这个意义上说,这种方法产生的码本是次优的。如果能打破均匀树的限制,就有可能提高性能。特别地，如果能在过程的每一步把具有最大总误差的试验矢量簇划分开来,就能获得误差较小的码本。这样,我们第一步先把n维空间分成两个区域；第二步,选出具有较大误差的矢量簇(区域)并把它分割开,于是有了

15、3个矢量；第三步,从中再挑出最大误差的簇将它分开,于是成了4个簇;如此重复进行,最终的结果是获得了一棵非均匀码树,如图2.11所示。图中取L=7。注意,这里L可以不是2的幂次。第章信源编码理论 图 2.11用于二进搜索矢量量化的非均匀树第章信源编码理论【例例 2.4】令x1和x2是两个随机变量,具有均匀的联合概率密度函数:121(,)()0Cp x xPabXX其他(2.76)式中C是一个矩形区域,如图2.12所示。注意,该矩形相对于水平轴旋转了45。另外,边缘密度p(x1)和p(x2)示于图2.12。第章信源编码理论 图 2.12均匀联合概率密度函数第章信源编码理论 如果采用均匀的间隔长度分

16、别量化x1和x2,需要的电平数是122abLL(2-77)因此,对矢量X=x1 x2编码所需的比特数是 Rx=R1+R2=lbL1+lbL2=lb222)(ba(2-78)第章信源编码理论 这样,每个分量的标量量化相当于采用全部电平数的矢量量化:Lx=L1L2=(2.79)由此看到,这种途径相当于用许多正方形胞元顶盖一个能包围矩形区域的大正方形,这里的每个胞元代表Lx个量化区域之一。由于除XC外P(X)=0,所以这种编码很浪费,导致比特率增加。222)(ba 第章信源编码理论 如果用面积为2的小正方形仅仅覆盖P(X)0的区域,所需要的总电平数应是矩形面积除以2,即2xabL(2.80)因此,标量量化和矢量量化比特率之差是22()lb2xxabRRab(2.81)第章信源编码理论 若a=4b,比特率之差是RxR x=1.64 bit/矢量这样,在失真相同的情况下,矢量量化比标量量化好0.82 bit/抽样。旋转45进行一次线性变换可以去除x1和x2的相关性,使这两个随机变量统计独立。这样一来,标量量化和矢量量化可取得同等的效率。虽然线性变换能够去除构成矢量的各随机变量之间的相关性,但它不