信息论与编码第四章

信息论与编码第四章*1第一页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码2第4章限失真信源编码4.1平均失真和信息率失真函数

失真函数

平均失真

信息率失真函数

信息率失真函数的性质4.2离散信源和连续信源的计算4.3限失真信源编码定理4.4常用信源编码方法简介

游程编码

算术编码

矢量量化

预测编码变换编码习题第二页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码3第4章限失真信源编码控制信息失真的原因?

在实际问题中，信号有一定的失真是可以容忍的。但是当失真大于某一限度后，信息质量将被严重损伤，甚至丧失其实用价值。要规定失真限度，必须先有一个定量的失真测度。

例如：语音、图像第三页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码44.1平均失真和信息率失真函数失真函数

失真函数定义:信源编码Xx1x2xnYy1y2ym第四页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码54.1平均失真和信息率失真函数失真函数失真矩阵第五页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码6失真函数

例设信源符号X∈｛0，1｝,编码器输出符号Y∈｛0,1,2｝,规定失真函数为d(0,0)＝d(1,1)＝0;d(0,1)＝d(1,0)=1;d(0,2)＝d(1,2)＝0.5，求失真矩阵。解:由式得失真矩阵第六页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码7失真函数(1)常用失真函数均方失真：绝对失真：相对失真：

误码失真：

说明:第七页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码8失真函数说明:

(2)最常用的失真函数及其适用性均方失真函数、绝对失真函数、相对失真函数适用于连续信源；误码失真适用于离散信源。

(3)失真函数困难性比较均方失真和绝对失真只与(xi-yj)有关，而不是分别与xi及yj有关，在数学处理上比较方便。第八页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码9失真函数

失真函数的定义的推广-序列编码如果假定离散信源输出符号序列X＝{x1x2…xi…xn}，其中L长符号序列X=X1X2…XL的取值设为

xi=[xi1xi2…xiL]，经信源编码后，接收端收到符号序列Y={y1y2…yj…ym}，其中L长符号序列yj=[yj1yj2…yjL]则失真函数定义为式中d(xik,yjk)是信源输出第i个L长符号xi中的第k个符号xik，接收端收到第j个L长符号yj中的第k个符号yjk的失真函数。第九页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码10平均失真失真矩阵信源编码Xx1x2xnYy1y2ym第十页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码11平均失真平均失真失真函数的数学期望称为平均失真。对于连续随机变量的平均失真连续随机变量的联合概率密度第十一页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码12信息率失真函数1.信息率失真函数R(D)问题产生?

对于信道容量为C的信道传输信息传输率为R的信源时，如果R＞C，就必须对信源压缩，使其压缩后信息传输率R’小于信道容量C，但同时要保证压缩所引入的失真不超过预先规定的限度D。信息压缩问题就是对于给定的信源，在满足平均失真

的前提下，使信息率尽可能小。

（举例语音）第十二页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码13信息率失真函数2D允许信道（D允许的试验信道）对于离散无记忆信道(假想信道，实际上是信源编码)3信息率失真函数R(D)对于离散无记忆信源第十三页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码14信息率失真函数例4-1-2已知,编码器输入的概率分布为:p(x)＝{0.5，0.5}，信道矩阵分别为:

求:互信息。

x1x2y1y20.60.40.20.8第十四页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码15信息率失真函数例4-1-2分析p(x)＝{0.5，0.5}

x1x2y1y20.60.40.20.8第十五页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码16信息率失真函数解(1)因p(xiyj)＝p(xi)p(yj/xi)；

p’(x1y1)=0.3，p’(x1y2)＝0.2，

p’(x2y1)=0.1，p’(x2y2)＝0.4

因为p(yi)=所以p’(y1)＝0.4，p’(y2)＝0.6x1x2y1y20.60.40.20.8第十六页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码17信息率失真函数又因为p(xi/yj)=p(xiyj)/p(yj)所以p’(x1/y1)=3/4,p’(x1/y2)=1/3,p’(x2/y1)=1/4,p’(x2/y2)=2/3

根据互信息公式代入可得

比特/符号

用p’ij代入进行同样的运算可得

I(X;Y)=0.397比特／符号

第十七页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码18信息率失真函数补充例已知,编码器输入的概率分布为:p(x)＝{0.5，0.5}，信道模型分别为:

求:互信息、平均失真。

x1x2y1y20.990.010.010.09x1x2y1y211x1x2y1y20.90.10.10.9x1x2y1y20.60.40.40.6x1x2y1y20.50.50.50.5第十八页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码19信息率失真函数补充例编码器输入的概率分布为:p(x)＝{0.5，0.5}

x1x2y1y211第十九页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码20信息率失真函数补充例编码器输入的概率分布为:p(x)＝{0.5，0.5}，

x1x2y1y20.990.010.010.99第二十页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码21信息率失真函数补充例编码器输入的概率分布为:p(x)＝{0.5，0.5}，

x1x2y1y20.90.10.10.9第二十一页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码22信息率失真函数补充例编码器输入的概率分布为:p(x)＝{0.5，0.5}，

x1x2y1y20.60.40.40.6第二十二页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码23信息率失真函数补充例编码器输入的概率分布为:p(x)＝{0.5，0.5}，

x1x2y1y20.50.50.50.5第二十三页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码24信息率失真函数补充例总结

x1x2y1y20.50.50.50.5当信源固定，变动信道，这里指信源编码的一种方式，信道转移概率可变。第二十四页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码25信息率失真函数补充例总结

x1x2y1y20.990.010.010.09x1x2y1y211x1x2y1y20.90.10.10.9x1x2y1y20.60.40.40.6x1x2y1y20.50.50.50.51-pppI(X;Y)DR(D)第二十五页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码26信息率失真函数例设信源的符号表为A=｛a1,a2,…,a2n｝,概率分布为p(ai)＝1/2n，i＝1,2,…,2n，失真函数规定为由信源概率分布可求出信源熵为设想采用下面的编码方案：等效试验信道第二十六页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码27信息率失真函数例设信源的符号表为A=｛a1,a2,…,a2n｝,概率分布为p(ai)＝1/2n，i＝1,2,…,2n，失真函数规定为平均失真D为等效试验信道第二十七页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码28信息率失真函数由该信道模型知，它是一个确定信道由互信息公式可得

I(X;Y)=H(Y)-H(Y/X)=H(Y)信道输出概率分布为所以概率分布为则输出熵H(Y)为第二十八页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码29信息率失真函数信息率失真函数的意义：

在一定允许失真度D的条件下，用尽可能少的码符号来传送信源消息，以提高通信系统的可靠性。作业：4-1本次课小结：

1失真函数

2平均失真度

3信息率失真函数第二十九页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码30信息率失真函数的性质1.R(D)函数的定义域

R(D)的定义域为D∈［0，Dmax］2.R(D)函数的下凸性和连续性3.R(D)函数的单调递减性例:R(D)在定义域内是下凸的,连续的。R(D)的单调递减性可以作如下理解：容许的失真度越大，所要求的信息率越小。第三十页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码31信息率失真函数的性质得出如下结论：R(D)是非负的实数，即R(D)≥0。其定义域为0～Dmax，其值为0～H(X)。当D＞Dmax时,R(D)≡0。R(D)是关于D的下凸函数，因而也是关于D的连续函数。R(D)是关于D的严格递减函数。第三十一页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码324.2离散信源和连续信源的计算某些特殊情况下R(D)的表示式为：率失真函数第三十二页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码334.2离散信源和连续信源的计算例设输入输出符号表为X=Y=｛0，1｝，输入概率分布p(x)=｛p，1-p｝，0＜p≤1/2，失真矩阵为

求信息率失真函数R(D).

解:简记

(1)按下式解方程

解得第三十三页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码344.2离散信源和连续信源的计算(2)按下式解方程解得(3)得转移概率分布第三十四页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码354.2离散信源和连续信源的计算(4)求s(s=logα)第三十五页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码364.2离散信源和连续信源的计算(5)计算R(D)，将上面各式代入，则有(D)=H(p)-H(D)，p为参数第三十六页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码374.3限失真信源编码定理限失真信源编码定理：设离散无记忆信源X的信息率失真函数R(D)，则当信息率R＞R(D)，只要信源序列长度L足够长，一定存在一种编码方法，其译码失真小于或等于D+ε，ε为任意小的正数；反之，若R＜R(D)，则无论采用什么样的编码方法，其译码失真必大于D。如果是二元信源，对于任意小的ε＞0，每一个信源符号的平均码长满足如下公式在失真限度内使信息率任意接近R(D)的编码方法存在。第三十七页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码384.4常用信源编码方法简介游程编码游程长度在二元序列中，只有两种符号，即“0”和“1”，这些符号可连续出现，连“0”这一段称为“0”游程，连“1”这一段称为“1”游程。它们的长度分别称为游程长度L(0)和L(1).

对于多元序列也存在相应的游程序列。例如m元序列中，可有m种游程。连着出现符号ar的游程，其长度L(r)就是“r”游程长度。设有多元信源序列(x1，x2，…，xm1，y，y，…，y，xm1+1，xm1+2，…xm2，y，y，…其中x是含有信息的代码，取值于m元符号集A，可称为信息位；y是冗余位，它们可为全零，即使未曾传送在收端也能恢复。这样的序列可用下列两个序列来代替：

111，…，100，…，000111，…，111000和

x1，x2，…，xm1，xm1+1，xm1+2，…xm2，…

前一个序列中，用“1”表示信息位，用“0”表示冗余位；后一个序列是取消冗余位后留下的所有信息位。第三十八页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码39算术编码算术编码的基本思路从全序列出发，将各信源序列的概率映射到［0，1］区间上，使每个序列对应这区间内的一点，也就是一个二进制的小数。积累概率则例如有一序列S=011，这种三个二元符号的序列可按自然二进数排列，000，001，010，……，则S的积累概率为

P(S)=p(000)+p(001)+p(010)如果S后面接一个“0”，积累概率就成为

P(S0)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)=p(000)+p(001)+p(010)=P(S)

信源的符号概率和积累概率第三十九页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码40算术编码如果S后面接一个“1”，则其积累概率是

P(S1)=p(0000)+p(0001)+p(0010)+p(0011)+p(0100)+p(0101)+p(0110)=P(S)+p(0110)=P(S)+p(S)p0上面两式可统一写作一般的递推公式序列的概率的公式

第四十页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码41算术编码实用中，采用积累概率P(S)表示码字C(S)，符号概率p(S)表示状态区间A(S)，则有实际编码过程:

先置两个存储器C和A，起始时可令其中代表空集。每输入一个信源符号，存储器C和A就按照上式更新一次，直至程序结束，就可将存储器C的内容作为码字输出。第四十一页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码42算术编码例有简单的四个符号a，b，c，d构成序列S=abda，各符号及其对应概率如表算术编解码过程如下:设起始状态为空序列φ，则A(φ)=1，C(φ)=0。表4-4-1各符号及其对元概率符号符号符号概率pi符号概率pi符号累积概率Pj符号累积概率Pjabcd0.100(1/2)0.010(1/4)0.001(1/8)0.001(1/8)0.0000.1000.1100.111第四十二页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码43算术编码算术码编码过程第四十三页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码44算术编码据递推公式的相反过程译出符号。具体译码顺序是后编的先译，故称为LIFO算术码，步骤如下：C(abda)=0.010111＜01∈［0,0.1)第一个符号为a；放大至［0,1):C(abda)×2＝0.10111∈［0.1,0.110)第二个符号为b；去掉累积概率Pb:0.10111-0.1=0.00111放大至［0,1):0.00111×=0.111∈［0.111,1)第三个符号为d去掉累积概率Pd：0.111-0.111=0放大至［0,1)：0×=0∈［0,0.1)第四个符号为a。第四十四页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码45矢量量化标量量化

连续信源进行编码的主要方法是量化，即将连续的样值x离散化成为yi，i=1,2,3,…,n。设信源符号的取值区间为(a0，an)，即a0＜x＜an，a0可为负无限，an可为正无限，所以上述假设不失一般性。量化就是将上面的区间分成n个小区间，每个区间内定一个量化值yi，若各区间端点为ai-1和ai，必有

a0≤y1≤a1≤y2≤…≤an-1≤yn≤an最佳标量量化就是在一定的n值时，选择各ai和yi以使失真最小。此时的信息率为R=logn第四十五页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码46矢量量化量化噪声

当一个样值x经量化后所产生的误差为也就是在信号值x上叠加了一个样值为的噪声信号。以语音信号量化常用的脉码调制(PCM)为例。设语音信号的准峰值为L，由于语音信号是双向性的，则其取值范围为［-L,L］。量化级数为n，量化级差为2L/n，用中心值作为量化值yi。语音信号样值x的概率密度是负指数分布经推导计算(见参考文献2)可得信号功率与噪声功率之比即信噪比为第四十六页，共五十一页，2022年，8月28日*北京工商大学信息工程学院信息论与编码47矢量量化压扩技术

综