第二章 无失真信源编码

第二章无失真信源编码信息量、熵和互信息信源编码定理霍夫曼码及其他编码方法算术编码游程编码改进的霍夫曼码通用编码第二章无失真信源编码无失真编码：保证信源产生的全部信息无失真地传递给信宿。（只有对离散信源可以实现无失真信源编码。）实质上是一种概率匹配编码。限失真信源编码：在确定标准和准则的条件下，信源所必须传递的最小信息量。也称信息率失真函数（限定波形失真——波形编码，限定特性参量失真——参量编码）。第二章无失真信源编码信源中的统计多余度主要取决于以下两个主要因素：一是消息概率分布的非均匀性，另一个是消息间的相关性。对无记忆信源主要取决于概率分布的非均匀性，但是，对于有记忆信源，两者都起作用，且相关性更加重要。第二章无失真信源编码统计匹配编码：是根据信源的不同概率分布而选用与之相匹配的编码，以达到的系统同中传信速率最小，且满足在信宿复制时无失真或低于某一允许的失真限度值。2．1信息量、熵和互信息量时间发生的概率越小，不确定性就越大，给人的信息量就越小；发生的概率越大，不确定性就越小，给人的信息量就越大。

条件概率联合概率必须掌握的概率论知识必须掌握的概率论知识全概率：设B1

,B2

,…是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（样本空间）；p（Bi）＞0，i=1，2，…，则对任一事件A，有：必须掌握的概率论知识4)Bayes公式:

设B1

,B2

,…是一列互不相容的事件(Bi

Bj=0），且有B1

∪B2

∪…=Ω（样本空间）；

p（Bi）＞0，i=1，2，…，则对任一事件A，有：一个离散无记忆信源是由n个符号消息组成的集合:X={x1，x2

·

··xn

}，这n个符号消息的概率分布为了：称为符号xi

的先验概率,散信源数学模型表示为：

称为概率空间,其中从概率的角度看，可以将符号消息xi看一个随机事件。因此xi具有不确定性。

2．1信息量、熵和互信息量信息量定义：2．1信息量、熵和互信息量信息量定义：美国科学家L.V.R.Hartley

于1928年给出了信息的度量方法。定义若信源发出一符号xi，由于信道存在干扰，收到的不是xi而是yi，从yi中获取有关xi的信息量用I(xi；yi)表示，称为互信息量。

定义上述情况，若信道无干扰，收到的就是xi本身，这样I(xi；yi)就可以用I(xi；xi)表示，或简单记作I(xi)，并称为自信息量。一、自信息量1)函数I(xi)的属性

1º若有两个事件xi

，xj

，其先验概率为p(xi)＜p(xj)，则事件xi比事件xj有更大的不确定性，同时会带来更多的信息量；I(xi

)>I(xj

)2º事件xi先验概率p(xi)=1（确定事件）,则不存在不确定性，同时不会带来信息量；I(xi)=0.3º事件xi先验概率p(xi)=0（不可能事件）,则存在不确定性应为无穷大，同时会带来无穷的信息量；I(xi)→∞.4º两个统计独立事件的联合自信息量应等于它们各自信息量之和;则I(xy)=

I(x)＋I(y)2)

定义一个符号消息xi的自信息量为其发生概率的对数的负数，并记为I(xi)：

I(xi)=－logp(xi)

当p(xi)=0，则I(xi)→∞；当p(xi)=1，则I(xi)=0.3)自信息量的单位自信息量的单位与所用对数的底有关：

1º对数的底是2时，单位为比特—bit(binaryunit)2º对数的底是e(自然对数)时，单位为奈特

—nat(natureunit)3º对数的底是10(常用对数)时，单位为笛特或哈特

—det(decimalunit)orHart(Hartley)三种信息量单位之间的换算：

1det=log210≈3.322bit1bit=ln2≈0.6931nat

1bit=lg

2≈0.3010det1nat=log2e≈1.4427bit

在信息论中常用以2为底的对数，为了书写方便，以后将log2书写为log，因其单位为比特bit，不会产生混淆；注意有些文献将log2书写为lb4)自信息量的含义是随机量、根据单个符号消息的先验概率确定其信息量和不确定度。二、离散信源熵信源X发出某一个符号提供的信息量不适合描述信源X发出一个符号提供的信息量。定义信息源的平均不确定度为信源中各个符号不确定度的数学期望，记作H(X)

其中

H(X)又称为信源X的信源熵。

2)H(X)

的含义

1º表示的是信源的平均不确定度。

2º表示信源X发出一个符号提供的平均信息量。

3º是统计量、数学期望（统计平均）、各个符号平均不确定度和平均信息量。

3)

信源熵单位：二进制:bit/信源符号，或bit/信源序列十进制:det/信源符号，或det/信源序列

e进制:nat/信源符号，或nat/信源序列

4)信源熵的三种特殊情况1º当

p(xi)=0时（p(xi)→0），则p(xi)logp(xi)=02º信源X={x1，x2

·

··xn

}

，若其中xi

的概率p(xi)=1

则其余xj

的p(xj)=0，因为则H(X)=0bit/信源符号3º当信源中X所有n个符号均有相同的概率p(xi)=1/n，

则H(X)=-(1/n)log(1/n)=lognbit/信源符号2º联合熵（共熵）

联合熵是联合符号集合XY上的每个元素对xi

,

yj的自信息量的概率加权的统计平均值。3º条件熵与联合熵的关系

I(xi

|yj)=－logp(xi

|

yj)

，I(xi

yj)=－logp(xi

yj)

因

全概率公式5)条件熵与联合熵

1º条件熵在给定yj条件下，xi的条件自信息量为：

I(xi

|yj)=－logp(xi

|

yj)

集合X的条件熵为：

在给定Y（即各个yj）条件下，集合X的条件熵定义为：三、互信息（一）简单的通信模型

若信源发出符号xi，由于信道存在干扰，收到的不是xi而是yi，从yi中获取有关xi的信息量称为互信息量，用I(xi;yi)表示。信源X有干扰离散信道信宿Y干扰源所以H(XY)=H(X

)＋H(Y|X)同理H(XY)=H(Y)＋H(X|Y)含义：平均从Y获得的关于X的信息量。 （又称信道 的信息传输率R）（二）平均互信息※I(X;Y)与熵：※I(X;Y)与I(x;y)：

I(x;y)表示由随机事件y中获得的关于事件x的信息。互信息:关系：I(X;Y)＝EXY[I(x;y)]注意：（二）平均互信息

※比较：I(x;y)可正可负，1．非负性I(X;Y)≥0（三）平均互信息的性质

※

当I(X;Y)=0全损信道：H(X)=H(X|Y)，说明：

通信的意义——通过消息的传递可获得信息信源加密密钥源信道解密信宿保密通信系统框图XY’Y非法用户全损信道（三）平均互信息的性质

※信息处理的一般规律：通过传输获得的信息量不大于提供的信息量。

※

I(X;Y)=H(X)无损信道：H(X|Y)=02．

极值性，P(x|y)=0or1（三）平均互信息的性质

I(X;Y)=I(Y;X)３．交互性（对称性)（三）平均互信息的性质I(X;Y)=H(X)－H(X|Y)=H(Y)－H(Y|X)

4.

I(X;Y)与各类熵的关系

文氏图H(X∣Y)H(Y∣X)信源熵信道疑义度噪声熵（散布度）I(X;Y)

=H(X)+H(Y)－H(XY)信宿熵H(XY)（三）平均互信息的性质特殊信道特殊信道总结

信道名称信道特征信息传输情况全损信道P(xy)=P(x)P(y)H(X︱Y)=H(X)I(X；Y)=0无噪信道

P(y︱x)=0or1H(Y︱X)=0I(X；Y)=H(Y)无损信道

P(x︱y)=0or1H(X︱Y)=0I(X；Y)=H(X)（三）平均互信息的性质

5．

凸状性I(X;Y)=f[P(x)，P(y|x)]（三）平均互信息的性质Th3.2：对于固定信源分布，平均互信息I(X;Y)是信道传递概率p(y|x)的∪型凸函数。※不同信源通过不同信道传输得到的平均互信息不同；

5．

凸状性Th3.1：对于固定信道，平均互信息I(X;Y)是信源概率分布p(x)的∩型凸函数。平均互信息是信源符号概率分布的上凸函数平均互信息是信道转移概率的下凹函数（三）平均互信息的性质

例1．

分析二元信源通过BSC信道的I(X;Y)特性信源：，信道：1－p1－ppp0011则（三）平均互信息的性质其中，

（三）平均互信息的性质，得：（三）平均互信息的性质

I.

固定信道（p一定），∴H(p)一定I(X;Y)∝H(ω+p－2ωp)由熵上凸性的该I(X;Y)为ω的上凸函数I(X;Y)1－H(p)01/21ωω＝1/2时，I(X;Y)极大I(X;Y)＝H(1/2)－H(p)=1－H(p)

（三）平均互信息的性质Ⅱ.

固定信源（ω一定）则I(X;Y)～p，∴I(X;Y)=I(p)∴I(p)为下凹函数可求：p=1/2,I(X;Y)=0,极小p=0,I(X;Y)=H(ω)p=1,I(X;Y)=H(ω)I(X;Y)01/21p（三）平均互信息的性质2．2信源编码定理信源编码的无失真编码：接收端信宿要求无失真精确的复制信源输出的消息。只有对离散信源才可以实现无失真编码。实质上是一种统计匹配编码——根据信源的不同概率分布而选用与之相匹配的编码，以达到在系统中传送速率最小，且满足在信宿复制时无失真或低于某一允许的失真限度值。2．2．1信源编码的基本概念信源编码：将信源输出符号，经信源编码器变换成另外的压缩符号，然后将压缩有信息经信道传送到信宿。只考虑信源和信宿两个因素。通信系统模型简化为P15图2-1编码A器输入为：编码器输出的码字为：符号码1码2码3码4等长码变长码u100001u201101101u3100000001u311011100012．2．1信源编码的基本概念树图（码树）法：树根=码字的起点树的度=码元数分支结点=码的符号的一部分终端结点=待编码符号满树=等长码：树中各结点有相同树枝数，且每层结点树达到最大值。非满树=变长码2．2．1信源编码的基本概念编码方法：1）将待编码的字符作为终端结点，构造码树；2）按一定规则给每个树枝分配一个标记；3）将从根到终端结点的路径上的编号依次相连，作为该终端结点所表示的字符的编码。2．2．1信源编码的基本概念译码方法：1）从树根出发，根据接收到的第一个码字符号来选择应走的第一条路径。2）沿所选路径走到分支结点，在根据收到的第而个码字选择应走的第二条路径。直至走到终端结点为止。3）根据所走路径，可立即判断出接收到的码符号。4）重新返回到树根，再作下一个接收码符号的判断。2．2．1信源编码的基本概念

分组码（块码）分类

1°按码字的码长分类定长码：码集中所有码字的码长相等。变长码：码集中所有码字的码长不全相等。

2°按信源符号与码字对应关系分类非奇异码：信源符号与码字是一一对应的。奇异码：信