限失真信源编码讲义（精品）.ppt

第5章　限失真信源编码;第一节　信息率失真函数（71页） ;5.1 平均失真和信息率失真函数;5.1.1 失真函数;失真矩阵;例5-1-1 ;均方失真：? ;例：设有对称信源（r=s） 信源符号集X={x1,x2,……,xr} 接收符号集Y={y1,y2,……,ys} 其失真度定义为：d(xi,yj)=(yj-xi)2 求失真矩阵[d]（以r=s=3为例） 。; 失真函数的定义可以推广到序列编码情况，如果假定离散信源输出符号序列X=(X1X2…Xl…XL)，其中L长符号序列样值xi＝(xi1xi2…xil…xiL)，经信源编码后，输出符号序列Y=(Y 1Y 2…Y l…Y L)，其中L长符号序列样值yj＝(yj1yj2…yjl…yjL)，则失真函数定义为： ? ;5.1.2 平均失真 ;;对于连续随机变量同样可以定义平均失真 ;5.1.3 信息率失真函数R(D);5.1.3 信息率失真函数R(D);1、D允许试验信道 ;2、信息率失真函数R(D) ;对于离散无记忆信源，R(D)函数可写成; 例 设信源的符号表为A＝{a1，a2，…，a2n}，概率分布为p(ai)＝1/2n，i＝1，2，…，2n，失真函数规定为 即符号不发生差错时失真为0，一旦出错，失真为1，试研究在一定编码条件下信息压缩的程度。;（1）R(D)是非负实数，定义域为0～Dmax，值域为0～H(X)。 当D Dmax，R(D)=0。 ;讨论;本节小结;限失真信源编码定理： 设离散无记忆信源X的信息率失真函数为R（D），则当信息率R＞R（D），只要信源序列长度 L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ ， 为任意小的正数；反之，若R＜R（D），则无论采用什么样的编码方法,其译码失真必大于D。 ;无失真与限失真编码定理比较;变长编码定理： 若一离散无记忆信源的符号熵为H（X），每个信源符号用m进制码元进行变长编码，一定存在一种无失真编码方法，其码字平均长度满足下列不等式 ;限失真信源编码定理： 设离散无记忆信源X的信息率失真函数为R（D），则当信息率R＞R（D），只要信源序列长度 L足够长，一定存在一种编码方法，其译码失真小于或等于D＋ ， 为任意小的正数；反之，若R＜R（D），则无论采用什么样的编码方法,其译码失真必大于D。 ;变长编码的优缺点: 优点：无损编码，相对于定长编码有较高的编码效率 缺点：具有分组码所具有的缺点 1）概率空间细微改变均会导致码表改变 2）对于二元信源需要多个符号合起来编码 3）当合并的符号数不大时，编码效果不佳 4）当合并的符号数增加时，码表中码字呈指数增加，设备要求更复杂 非分组码的必要性;5.3.1 游程编码 游程编码基本思想: 将任何(二元)序列变换成一一对应的游程长度序列，按哈夫曼编码或其他方法处理以达到压缩码率的目的 . ;什么叫二元序列游程和游程长度? 在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L（0）和L（l）。 “0”游程和“l”游程总是交替出现的。如果规定二元序列是以“0”开始，第一个游程是“0”游程，第二个必为“1”游程，第三个又是“0”游程等等。对于随机的二元序列，各游程长度将是随机变量，其取值可为1，2，3，…，直到无限。 ;说明: (1) 例 如有一个二元序列：00101110010001… 可变换成游程长度序列：2113213… (2)二元序列与游程序列一一对应，可逆。 (3) 对二元序列进行哈夫曼编码时，应先测定“0”游程长度和“l”游程长度的概率分布，或由二元序列的概率特性去计算各种游程长度的概率。 ;什么叫多元序列游程和游程长度? 对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号ar的游程，其长度L（r）就是“r”游程长度。这也是一个随机变量。 说明： （1）用L（r）也可构成游程序列。但是多元符号的游程序列必须加入一些标志符号，才能成为一一对应或可逆的。 （2）多元序列的游程序列中标志符号占用较大信息率，使得编码效果变差。 （3）游程编码只适用于二元序列，对于多元信源，一般不能直接利用游程编码。;在许多信源序列中，常有不少符号不携带信息，除了它的数目或所占时长外，完