第二章 无失真信源编码
? 信息量、熵和互信息
? 信源编码定理
? 霍夫曼码及其他编码方法
? 算术编码
? 游程编码
? 改进的霍夫曼码
? 通用编码
第二章 无失真信源编码
? 无失真编码：保证信源产生的全部信息无失真地
传递给信宿。（只有对离散信源可以实现无失真
信源编码。）实质上是一种概率匹配编码。
? 限失真信源编码：在确定标准和准则的条件下，
信源所必须传递的最小信息量。也称信息率失真
函数（限定波形失真 —— 波形编码，限定特性参
量失真 —— 参量编码）。
第二章 无失真信源编码
? 信源中的统计多余度主要取决于以下两个
主要因素：
一是消息概率分布的非均匀性，
另一个是消息间的相关性。
对无记忆信源主要取决于概率分布的非均
匀性，但是，对于有记忆信源，两者都起
作用，且相关性更加重要。
第二章 无失真信源编码
? 统计匹配编码：是根据信源的不同概率分
布而选用与之相匹配的编码，以达到的系
统同中传信速率最小，且满足在信宿复制
时无失真或低于某一允许的失真限度值。
2,1 信息量、熵和互信息量
? 时间发生的概率越小，不确定性就越大，
给人的信息量就越小；发生的概率越大，
不确定性就越小，给人的信息量就越大。
? 条件概率
? 联合概率
必须掌握的概率论知识
)(
)(|
BP
ABPBAp ?）（
)(
)(|
AP
ABPABp ?）（
)|()( BApBPABp ?）（
)|()( ABpAPABp ?）（
必须掌握的概率论知识
全概率：
设 B 1,B 2,… 是一列互不相容的事件 (B i B j = 0）,
且有 B 1 ∪ B 2 ∪ … =Ω （ 样本空间 ） ；
p（ Bi） ＞ 0, i=1,2,…, 则对任一事件 A,有：
?? ??
i
i
i
ii ABpBApBpAp )()|()()(
必须掌握的概率论知识
4)Bayes公式,
设 B 1,B 2,… 是一列互不相容的事件 (B i B j=
0）,
且有 B 1 ∪ B 2∪ … =Ω （ 样本空间 ） ；
p（ Bi） ＞ 0, i=1,2,…, 则对任一事件 A,有：
)(
)|()(
)|()(
)|()()|(
1
AP
BAPBp
BApBp
BAPBpABp ii
i
ii
ii
i ?? ?
?
一个离散 无记忆信源是由 n个符号消息组成的集合,X={ x1，
x2 ···xn },这 n个符号消息的概率分布为了：
称为符号 xi 的 先验概率,散 信源数学模型表示为：
称为 概率空间,其中
从概率的角度看, 可以将符号消息 xi 看一个 随机事
件 。 因此 xi 具有 不确定性 。
2,1 信息量、熵和互信息量
? 信息量定义：
)}(),(),({ 21 nxpxpxpp ??
??
?
??
??
??
?
??
?
)()()()( 321
321
n
n
xpxpxpxp
xxxx
P
X
?
?
?
?
??
n
i
ii xpxp
1
1)(,0)(
2,1 信息量、熵和互信息量
? 信息量定义：
美国科学家 L.V.R.Hartley 于 1928年给出了信息的度量方法。
定义 若信源发出一符号 xi,由于信道存在干扰，收到
的不是 x i 而是 y i,从 y i中获取有关 x i的信息量用 I
( x i ； y i) 表示，称为互信息量。
定义 上述情况，若信道无干扰，收到的就是 x i 本身，
这样 I (x i ； y i) 就可以用 I (x i ； x i) 表示，或简单记
作 I( x i)，并称为自信息量。
一、自信息量
1) 函数 I(x i) 的属性
1o若有两个事件 x i, x j,其先验概率为 p(x i)
＜ p(x j)，则事件 x i 比事件 x j 有更大的不确定性，同时
会带来更多的信息量； I(xi ) > I(xj )
2o 事件 x i 先验概率 p(xi) = 1 （确定事件）,则不
存在不确定性，同时不会带来信息量； I( xi ) = 0.
3o 事件 x i 先验概率 p(xi) = 0（不可能事件）,则存
在不确定性应为无穷大，同时会带来无穷的信息量； I(xi)
→ ∞.
4o 两个统计独立事件的联合自信息量应等于它们各
自信息量之和 ; 则 I( x y ) = I( x )＋ I( y )
2) 定义 一个符号消息 xi的 自信息量 为其发生概率的对数
的负数, 并记为 I(xi)：
I (xi) = － log p(xi)
当 p(xi)=0,则 I(xi)→∞ ；当 p(xi)=1,则 I(xi)=0.
3) 自信息量的单位
自信息量的单位与所用对数的底有关：
1o对数的底是 2 时, 单位为比特 — bit(binary unit)
2o对数的底是 e (自然对数 )时, 单位为奈特
— nat(nature unit)
3o对数的底是 10(常用对数 ) 时, 单位为笛特或哈特
— det (decimal unit) or Hart (Hartley)
三种信息量单位之间的换算：
1 det = log2 10 ≈3.322 bit
1 bit = ln 2 ≈ 0.6931 nat
1 bit = lg2 ≈0.3010 det
1 nat = log2e ≈1.4427 bit
在信息论中常用以 2为底的对数, 为了书写方便, 以
后将 log2书写为 log,因其单位为比特 bit,不会产生混淆；
注意 有些文献将 log2书写为 lb
4) 自信息量的含义
是随机量, 根据 单个符号消息 的先验概率确定其信息
量和不确定度 。
二、离散信源熵
信源 X 发出某一个符号提供的信息量不适合描述信源
X发出一个符号提供的信息量。
定义 信息源的 平均不确定度 为信源中各个符号不确定 度
的数学期望，记作 H (X)
其中
H(X) 又称为信源 X的信源熵。
?
?
?? n
i
ii xpxp
1
1)(,0)(
??
??
???
n
i
ii
n
i
ii xxpxIxpXH
11
)l o g ()()()()(
2) H(X) 的含义
1o表示的是信源的平均不确定度 。
2o表示信源 X 发出一个符号提供的平均信息量 。
3o是统计量, 数学期望 （ 统计平均 ）, 各个符号平均不
确定度和平均信息量 。
3) 信源熵单位：
二进制, bit/信源符号, 或 bit/信源序列
十进制, det/信源符号, 或 det/信源序列
e进制, nat/信源符号, 或 nat/信源序列
4) 信源熵的三种特殊情况
1o当 p(xi)=0 时 （ p(xi)→ 0）, 则 p(xi) log p(xi)=0
2o信源 X = { x1,x2 ···xn }, 若其中 xi 的概率 p(xi)=1
则其余 xj 的 p(xj) =0,因为
则 H(X)=0 bit / 信源符号
3o当信源中 X所有 n个符号均有相同的概率 p(xi)=1/n，
则 H(X)= -(1/n)log(1/n) = log n bit / 信源符号
0)(l i m
1
1
l i m
1
l o g
l i ml o gl i m
0
2
000
???
?
??
????
?
?
?
?
?
??
????
2o联合熵 （ 共熵 ）
联合熵 是联合符号集合 XY上的每个元素对 xi,yj的自信息
量的概率加权的统计平均值 。
3o条件熵与联合熵的关系
I( x i | y j )=－ log p( x i |y j ), I(x i y j )= － log p( x i y j )
因
全概率公式
? ?? i j jiji yxIyxpXYH )()()(
??
?
??
1
)|()()()(
j
jij
j
jii yxpypyxpxp
? ? ??
? ?
???
??
i i j
ijjii
j
ji
i j
ijiji
yxpyxpxpyxp
yxpxpyxpXYH
)|(l o g)()(l o g)(
)]|()(l o g)[()(
5)条件熵与联合熵
1o条件熵
在给定 y j 条件下, x i 的条件自信息量为：
I(x i | yj)=－ log p(xi | yj)
集合 X的条件熵为：
在给定 Y（ 即各个 yj） 条件下, 集合 X的条件熵定义为：
)|()|()|( jiji
ij
yxIyxpyXH ??
? ? ??
???
??
??
j i j
jiji
i
jijij
i
jiji
j
jj
j
j
yxIyxpyxIyxpyp
yxIyxpypyXHypYXH
)|()()|()|()(
)|()|()()|()()|(
])()|()([ ?? ?
i ii ii
ABpBApBp?
三、互信息
（一）简单的通信模型
若信源发出符号 xi,由于信道存在干扰，收到的不
是 xi 而是 y i,从 y i中获取有关 xi 的信息量称为 互
信息量,用 I (x i ; y i) 表示。
信源 X 有干扰离散信道 信宿 Y
干扰源
所以 H( X Y ) = H(X )＋ H(Y | X )
同理 H( X Y ) = H(Y )＋ H( X | Y )
含义：平均从 Y获得 的关于 X的信息量 。
（ 又称信道 的 信息传输率 R）
? ??
X Y
s i gbitxP yxPxyP /)( )|(l o g)(
（二）平均互信息
)()();( YXHXHYXI ??
? ??
X Y
s i gb i tyPxP xyPxyP /)()( )(l o g)(
? ??
X Y
s i gbityP xyPxyP /)( )|(l o g)(
※ I(X;Y)与熵：
?
?
?
不同点：提供与获得
共同点：统计平均
※ I(X;Y)与 I(x;y)：
I(x;y)表示由随机事件 y中 获得 的关于事件 x的信息。
互信息,
)(
)(log);(
yp
yxpyxI ?
关系,I(X;Y)＝ EXY[I(x;y)]
? ??
X Y xP
yxPxyPYXI
)(
)|(l o g)();(
（二）平均互信息
※ 比较,I(x;y)可正可负,
1,非负性
I(X;Y)≥0
)(
)|(l o g);(
xp
yxpyxI ?
，通信受干扰
，通信中断＝＝
，正常通信当
0);(),()|(
0);(),()|(
0);(),()|(
??
??
yxIxpyxp
yxIxpyxp
yxIxpyxp
（三）平均互信息的性质
※ 当 I(X;Y)=0
全损信道,H(X)=H(X|Y)，
??
?
?
?
?
?
)|()(
)()()(
ijj
jiji
abpbp
bpapbap
说明：
通信的意义 —— 通过消息的传递可获得信息信源 加密
密钥源
信道 解密 信宿
保密通信系统框图
X
Y’
Y
非法用户
全损信道
（三）平均互信息的性质
※ 信息处理的一般规律：通过传输获得的信息量不
大于提供的信息量 。
)();(0 XHYXI ??
※ I(X;Y)=H(X)
无损信道,H(X|Y)=0
2,极值性
,P(x|y)=0 or 1
（三）平均互信息的性质
I(X;Y)=I(Y;X)
? ??
X Y xp
yxpxypYXI
)(
)|(l o g)();(
? ?? ? ??
X YX Y yp
xypxyp
ypxp
xypxyp
)(
)|(l o g)(
)()(
)(l o g)(
);()|()( XYIXYHYH ???
３,交互性（对称性 )
（三）平均互信息的性质
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)=0 or 1 H(Y︱ X)=0I(X； Y)=H(Y)
无损信道 P(x︱ y)=0 or 1 H(X︱ Y)= 0I(X； Y)=H(X)
（三）平均互信息的性质
5,凸状性
I(X;Y)=f [P(x),P(y|x)]
?
?
?
?
?
?
?
?
?
?
??
?
??
? ?
)()|()(
)()|()()(
)(
)|(
l o g)();(
xPxyPxyP
xPxyPxyPyP
xP
yxP
xyPYXI
XX
X Y
（三）平均互信息的性质
Th3.2,对于固定信源分布, 平均互信息 I(X;Y)是信道
传递概率 p(y|x)的 ∪ 型凸函数 。
※ 不同信源通过不同信道传输得到的平均互信息不同；
5,凸状性
Th3.1,对于固定信道, 平均互信息 I(X;Y)是信源概率
分布 p(x)的 ∩ 型凸函数 。
?平均互信息是信源符号概率分布的上凸函数
?平均互信息是信道转移概率的下凹函数
（三）平均互信息的性质
例 1,分析二元信源通过 BSC信道的 I(X;Y)特性
?
?
?
?
?
?
?
??
?
?
?
?
?
?? 1
10
)( xP
X
信源：,信道：
1－ p
1－ p
p
p
0 0
1 1
则
? ??
X Y xP
yxPxyPYXI
)(
)|(l o g)();(
)|()( XYHYH ??
（三）平均互信息的性质
其中,
? ?? ? ??
X YX Y xyP
xyPxPxyPxyPXYH )|( 1l o g)|()()|( 1l o g)()|(
??
?
??
? ???
??
?
??
? ??
pppppppp
1l og1l og)1(1l og1l og ??
pppp
1lo g1lo g ?? )( pH?
（三）平均互信息的性质
，得：
?
?
?
????????
???????
)2(1)1()1(
2)1()0(
ppppyP
ppppyP
????
????
)2()( ppHYH ?? ????
)()2();( pHppHYXI ???? ??
?? ??
XX
xPxyPxyPyP )()|()()(
（三）平均互信息的性质
I,固定信道 （ p一定 ）, ∴ H(p)一定
I(X;Y)∝ H(ω+p－ 2ωp)
由熵上凸性的该 I(X;Y)为 ω的上凸函数
I(X;Y)
1－ H(p)
0 1/2 1 ω
ω＝ 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)
? ?? ? 0)21(1)21()1(
)1()(" ?
??????
??
pppppI ????
??
∴ I(p)为下凹函数
可求,p=1/2,I(X;Y)=0,极小
p=0,I(X;Y)=H(ω)
p=1,I(X;Y)=H(ω)
I(X;Y)
0 1/2 1 p
（三）平均互信息的性质
2,2 信源编码定理
信源编码的无失真编码：接收端信宿要求无
失真精确的复制信源输出的消息。只有对
离散信源才可以实现无失真编码。
实质上是一种统计匹配编码 —— 根据信源的
不同概率分布而选用与之相匹配的编码，
以达到在系统中传送速率最小，且满足在
信宿复制时无失真或低于某一允许的失真
限度值。
2,2,1 信源编码的基本概念
? 信源编码：将信源输出符号，经信源编码器
变换成另外的压缩符号，然后将压缩有信息
经信道传送到信宿。只考虑信源和信宿两个
因素。通信系统模型简化为 P15图 2-1
编码 A器输入为,},,,{),,,,,( 211 nlLl uuussssS ??? ??
编码器输出的码字为,},,,{),,,,,(
211 mkKk bbbssxxX ??? ??
符号 码 1 码 2 码 3 码 4
等长码 变长码
u1 00 0 0 1
u2 01 10 11 01
u3 10 00 00 001
u3 11 01 11 0001
2,2,1 信源编码的基本概念
树图（码树）法：
树根 =码字的起点
树的度 =码元数
分支结点 =码的符号的一部分
终端结点 =待编码符号
满树 =等长码：
树中各结点有相同树枝数，且每层结点树达到最大值。
非满树 =变长码
2,2,1 信源编码的基本概念
? 编码方法：
1）将待编码的字符作为终端结点，构造码树；
2）按一定规则给每个树枝分配一个标记；
3）将从根到终端结点的路径上的编号依次相连，
作为该终端结点所表示的字符的编码。
2,2,1 信源编码的基本概念
? 译码方法：
1）从树根出发，根据接收到的第一个码字符号来选
择应走的第一条路径。
2）沿所选路径走到分支结点，在根据收到的第而个
码字选择应走的第二条路径。直至走到终端结点
为止。
3）根据所走路径，可立即判断出接收到的码符号。
4）重新返回到树根，再作下一个接收码符号的判断。
2,2,1 信源编码的基本概念
分组码 （ 块码 ） 分类
1° 按码字的码长分类
定长码,码集中所有码字的码长相等 。
变长码,码集中所有码字的码长不全相等 。
2° 按信源符号与码字对应关系分类
非奇异码,信源符号与码字是一一对应的 。
奇异码,信源符号与码字不是一一对应的 。
3° 按译码唯一性分类
唯一可译码,对于多个码字组成的有限长码流, 只
能唯一地分割一个个的码字 。 唯一可译码 又称为 单义
码,例 码流 100111000…
码 1 x1→ 0 x2→ 10 x3→ 11 可 分割 10,0,11,10,0,0
码 2 x1→ 1 x2→ 10 x3→ 11 则无法 唯一分割
唯一可译码在传输过程中不需要同步码 。
非 唯一可译码,对有限长码流, 不能唯一地分割
一个个的码字 。
4° 按译码的 即时 性分类
非即时码,接收端收到一个完整的码字后, 不能
立即译码；还需要等到下一个码字开始接收后才
能判断是否可以译码 。
即时码,接收端收到一个完整的码字后, 就能立
即译码；即时码又称为 非延长码 或 异前缀码 。
例 非即时码 码流 01001100…
x1→ 0 x2→ 01 x3→ 11 译码为 x2,x1,x1,x3,x1,?
即时码 码流 01001100…
x1→ 0 x2→ 10 x3→ 11 译码为 x1,x2,x1,x3,x1,x1
异前缀码 (即时码 )指的是码集任何一个码不能是
其他码的前缀,
即时码必定是 唯一可译码,唯一可译码不一定 是
即时码,
5° 有实用价值的分组码
分组码是 非奇异码, 唯一可译码, 即时码
? 信息量、熵和互信息
? 信源编码定理
? 霍夫曼码及其他编码方法
? 算术编码
? 游程编码
? 改进的霍夫曼码
? 通用编码
第二章 无失真信源编码
? 无失真编码：保证信源产生的全部信息无失真地
传递给信宿。（只有对离散信源可以实现无失真
信源编码。）实质上是一种概率匹配编码。
? 限失真信源编码：在确定标准和准则的条件下，
信源所必须传递的最小信息量。也称信息率失真
函数（限定波形失真 —— 波形编码，限定特性参
量失真 —— 参量编码）。
第二章 无失真信源编码
? 信源中的统计多余度主要取决于以下两个
主要因素：
一是消息概率分布的非均匀性，
另一个是消息间的相关性。
对无记忆信源主要取决于概率分布的非均
匀性，但是，对于有记忆信源，两者都起
作用，且相关性更加重要。
第二章 无失真信源编码
? 统计匹配编码：是根据信源的不同概率分
布而选用与之相匹配的编码，以达到的系
统同中传信速率最小，且满足在信宿复制
时无失真或低于某一允许的失真限度值。
2,1 信息量、熵和互信息量
? 时间发生的概率越小，不确定性就越大，
给人的信息量就越小；发生的概率越大，
不确定性就越小，给人的信息量就越大。
? 条件概率
? 联合概率
必须掌握的概率论知识
)(
)(|
BP
ABPBAp ?）（
)(
)(|
AP
ABPABp ?）（
)|()( BApBPABp ?）（
)|()( ABpAPABp ?）（
必须掌握的概率论知识
全概率：
设 B 1,B 2,… 是一列互不相容的事件 (B i B j = 0）,
且有 B 1 ∪ B 2 ∪ … =Ω （ 样本空间 ） ；
p（ Bi） ＞ 0, i=1,2,…, 则对任一事件 A,有：
?? ??
i
i
i
ii ABpBApBpAp )()|()()(
必须掌握的概率论知识
4)Bayes公式,
设 B 1,B 2,… 是一列互不相容的事件 (B i B j=
0）,
且有 B 1 ∪ B 2∪ … =Ω （ 样本空间 ） ；
p（ Bi） ＞ 0, i=1,2,…, 则对任一事件 A,有：
)(
)|()(
)|()(
)|()()|(
1
AP
BAPBp
BApBp
BAPBpABp ii
i
ii
ii
i ?? ?
?
一个离散 无记忆信源是由 n个符号消息组成的集合,X={ x1，
x2 ···xn },这 n个符号消息的概率分布为了：
称为符号 xi 的 先验概率,散 信源数学模型表示为：
称为 概率空间,其中
从概率的角度看, 可以将符号消息 xi 看一个 随机事
件 。 因此 xi 具有 不确定性 。
2,1 信息量、熵和互信息量
? 信息量定义：
)}(),(),({ 21 nxpxpxpp ??
??
?
??
??
??
?
??
?
)()()()( 321
321
n
n
xpxpxpxp
xxxx
P
X
?
?
?
?
??
n
i
ii xpxp
1
1)(,0)(
2,1 信息量、熵和互信息量
? 信息量定义：
美国科学家 L.V.R.Hartley 于 1928年给出了信息的度量方法。
定义 若信源发出一符号 xi,由于信道存在干扰，收到
的不是 x i 而是 y i,从 y i中获取有关 x i的信息量用 I
( x i ； y i) 表示，称为互信息量。
定义 上述情况，若信道无干扰，收到的就是 x i 本身，
这样 I (x i ； y i) 就可以用 I (x i ； x i) 表示，或简单记
作 I( x i)，并称为自信息量。
一、自信息量
1) 函数 I(x i) 的属性
1o若有两个事件 x i, x j,其先验概率为 p(x i)
＜ p(x j)，则事件 x i 比事件 x j 有更大的不确定性，同时
会带来更多的信息量； I(xi ) > I(xj )
2o 事件 x i 先验概率 p(xi) = 1 （确定事件）,则不
存在不确定性，同时不会带来信息量； I( xi ) = 0.
3o 事件 x i 先验概率 p(xi) = 0（不可能事件）,则存
在不确定性应为无穷大，同时会带来无穷的信息量； I(xi)
→ ∞.
4o 两个统计独立事件的联合自信息量应等于它们各
自信息量之和 ; 则 I( x y ) = I( x )＋ I( y )
2) 定义 一个符号消息 xi的 自信息量 为其发生概率的对数
的负数, 并记为 I(xi)：
I (xi) = － log p(xi)
当 p(xi)=0,则 I(xi)→∞ ；当 p(xi)=1,则 I(xi)=0.
3) 自信息量的单位
自信息量的单位与所用对数的底有关：
1o对数的底是 2 时, 单位为比特 — bit(binary unit)
2o对数的底是 e (自然对数 )时, 单位为奈特
— nat(nature unit)
3o对数的底是 10(常用对数 ) 时, 单位为笛特或哈特
— det (decimal unit) or Hart (Hartley)
三种信息量单位之间的换算：
1 det = log2 10 ≈3.322 bit
1 bit = ln 2 ≈ 0.6931 nat
1 bit = lg2 ≈0.3010 det
1 nat = log2e ≈1.4427 bit
在信息论中常用以 2为底的对数, 为了书写方便, 以
后将 log2书写为 log,因其单位为比特 bit,不会产生混淆；
注意 有些文献将 log2书写为 lb
4) 自信息量的含义
是随机量, 根据 单个符号消息 的先验概率确定其信息
量和不确定度 。
二、离散信源熵
信源 X 发出某一个符号提供的信息量不适合描述信源
X发出一个符号提供的信息量。
定义 信息源的 平均不确定度 为信源中各个符号不确定 度
的数学期望，记作 H (X)
其中
H(X) 又称为信源 X的信源熵。
?
?
?? n
i
ii xpxp
1
1)(,0)(
??
??
???
n
i
ii
n
i
ii xxpxIxpXH
11
)l o g ()()()()(
2) H(X) 的含义
1o表示的是信源的平均不确定度 。
2o表示信源 X 发出一个符号提供的平均信息量 。
3o是统计量, 数学期望 （ 统计平均 ）, 各个符号平均不
确定度和平均信息量 。
3) 信源熵单位：
二进制, bit/信源符号, 或 bit/信源序列
十进制, det/信源符号, 或 det/信源序列
e进制, nat/信源符号, 或 nat/信源序列
4) 信源熵的三种特殊情况
1o当 p(xi)=0 时 （ p(xi)→ 0）, 则 p(xi) log p(xi)=0
2o信源 X = { x1,x2 ···xn }, 若其中 xi 的概率 p(xi)=1
则其余 xj 的 p(xj) =0,因为
则 H(X)=0 bit / 信源符号
3o当信源中 X所有 n个符号均有相同的概率 p(xi)=1/n，
则 H(X)= -(1/n)log(1/n) = log n bit / 信源符号
0)(l i m
1
1
l i m
1
l o g
l i ml o gl i m
0
2
000
???
?
??
????
?
?
?
?
?
??
????
2o联合熵 （ 共熵 ）
联合熵 是联合符号集合 XY上的每个元素对 xi,yj的自信息
量的概率加权的统计平均值 。
3o条件熵与联合熵的关系
I( x i | y j )=－ log p( x i |y j ), I(x i y j )= － log p( x i y j )
因
全概率公式
? ?? i j jiji yxIyxpXYH )()()(
??
?
??
1
)|()()()(
j
jij
j
jii yxpypyxpxp
? ? ??
? ?
???
??
i i j
ijjii
j
ji
i j
ijiji
yxpyxpxpyxp
yxpxpyxpXYH
)|(l o g)()(l o g)(
)]|()(l o g)[()(
5)条件熵与联合熵
1o条件熵
在给定 y j 条件下, x i 的条件自信息量为：
I(x i | yj)=－ log p(xi | yj)
集合 X的条件熵为：
在给定 Y（ 即各个 yj） 条件下, 集合 X的条件熵定义为：
)|()|()|( jiji
ij
yxIyxpyXH ??
? ? ??
???
??
??
j i j
jiji
i
jijij
i
jiji
j
jj
j
j
yxIyxpyxIyxpyp
yxIyxpypyXHypYXH
)|()()|()|()(
)|()|()()|()()|(
])()|()([ ?? ?
i ii ii
ABpBApBp?
三、互信息
（一）简单的通信模型
若信源发出符号 xi,由于信道存在干扰，收到的不
是 xi 而是 y i,从 y i中获取有关 xi 的信息量称为 互
信息量,用 I (x i ; y i) 表示。
信源 X 有干扰离散信道 信宿 Y
干扰源
所以 H( X Y ) = H(X )＋ H(Y | X )
同理 H( X Y ) = H(Y )＋ H( X | Y )
含义：平均从 Y获得 的关于 X的信息量 。
（ 又称信道 的 信息传输率 R）
? ??
X Y
s i gbitxP yxPxyP /)( )|(l o g)(
（二）平均互信息
)()();( YXHXHYXI ??
? ??
X Y
s i gb i tyPxP xyPxyP /)()( )(l o g)(
? ??
X Y
s i gbityP xyPxyP /)( )|(l o g)(
※ I(X;Y)与熵：
?
?
?
不同点：提供与获得
共同点：统计平均
※ I(X;Y)与 I(x;y)：
I(x;y)表示由随机事件 y中 获得 的关于事件 x的信息。
互信息,
)(
)(log);(
yp
yxpyxI ?
关系,I(X;Y)＝ EXY[I(x;y)]
? ??
X Y xP
yxPxyPYXI
)(
)|(l o g)();(
（二）平均互信息
※ 比较,I(x;y)可正可负,
1,非负性
I(X;Y)≥0
)(
)|(l o g);(
xp
yxpyxI ?
，通信受干扰
，通信中断＝＝
，正常通信当
0);(),()|(
0);(),()|(
0);(),()|(
??
??
yxIxpyxp
yxIxpyxp
yxIxpyxp
（三）平均互信息的性质
※ 当 I(X;Y)=0
全损信道,H(X)=H(X|Y)，
??
?
?
?
?
?
)|()(
)()()(
ijj
jiji
abpbp
bpapbap
说明：
通信的意义 —— 通过消息的传递可获得信息信源 加密
密钥源
信道 解密 信宿
保密通信系统框图
X
Y’
Y
非法用户
全损信道
（三）平均互信息的性质
※ 信息处理的一般规律：通过传输获得的信息量不
大于提供的信息量 。
)();(0 XHYXI ??
※ I(X;Y)=H(X)
无损信道,H(X|Y)=0
2,极值性
,P(x|y)=0 or 1
（三）平均互信息的性质
I(X;Y)=I(Y;X)
? ??
X Y xp
yxpxypYXI
)(
)|(l o g)();(
? ?? ? ??
X YX Y yp
xypxyp
ypxp
xypxyp
)(
)|(l o g)(
)()(
)(l o g)(
);()|()( XYIXYHYH ???
３,交互性（对称性 )
（三）平均互信息的性质
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)=0 or 1 H(Y︱ X)=0I(X； Y)=H(Y)
无损信道 P(x︱ y)=0 or 1 H(X︱ Y)= 0I(X； Y)=H(X)
（三）平均互信息的性质
5,凸状性
I(X;Y)=f [P(x),P(y|x)]
?
?
?
?
?
?
?
?
?
?
??
?
??
? ?
)()|()(
)()|()()(
)(
)|(
l o g)();(
xPxyPxyP
xPxyPxyPyP
xP
yxP
xyPYXI
XX
X Y
（三）平均互信息的性质
Th3.2,对于固定信源分布, 平均互信息 I(X;Y)是信道
传递概率 p(y|x)的 ∪ 型凸函数 。
※ 不同信源通过不同信道传输得到的平均互信息不同；
5,凸状性
Th3.1,对于固定信道, 平均互信息 I(X;Y)是信源概率
分布 p(x)的 ∩ 型凸函数 。
?平均互信息是信源符号概率分布的上凸函数
?平均互信息是信道转移概率的下凹函数
（三）平均互信息的性质
例 1,分析二元信源通过 BSC信道的 I(X;Y)特性
?
?
?
?
?
?
?
??
?
?
?
?
?
?? 1
10
)( xP
X
信源：,信道：
1－ p
1－ p
p
p
0 0
1 1
则
? ??
X Y xP
yxPxyPYXI
)(
)|(l o g)();(
)|()( XYHYH ??
（三）平均互信息的性质
其中,
? ?? ? ??
X YX Y xyP
xyPxPxyPxyPXYH )|( 1l o g)|()()|( 1l o g)()|(
??
?
??
? ???
??
?
??
? ??
pppppppp
1l og1l og)1(1l og1l og ??
pppp
1lo g1lo g ?? )( pH?
（三）平均互信息的性质
，得：
?
?
?
????????
???????
)2(1)1()1(
2)1()0(
ppppyP
ppppyP
????
????
)2()( ppHYH ?? ????
)()2();( pHppHYXI ???? ??
?? ??
XX
xPxyPxyPyP )()|()()(
（三）平均互信息的性质
I,固定信道 （ p一定 ）, ∴ H(p)一定
I(X;Y)∝ H(ω+p－ 2ωp)
由熵上凸性的该 I(X;Y)为 ω的上凸函数
I(X;Y)
1－ H(p)
0 1/2 1 ω
ω＝ 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)
? ?? ? 0)21(1)21()1(
)1()(" ?
??????
??
pppppI ????
??
∴ I(p)为下凹函数
可求,p=1/2,I(X;Y)=0,极小
p=0,I(X;Y)=H(ω)
p=1,I(X;Y)=H(ω)
I(X;Y)
0 1/2 1 p
（三）平均互信息的性质
2,2 信源编码定理
信源编码的无失真编码：接收端信宿要求无
失真精确的复制信源输出的消息。只有对
离散信源才可以实现无失真编码。
实质上是一种统计匹配编码 —— 根据信源的
不同概率分布而选用与之相匹配的编码，
以达到在系统中传送速率最小，且满足在
信宿复制时无失真或低于某一允许的失真
限度值。
2,2,1 信源编码的基本概念
? 信源编码：将信源输出符号，经信源编码器
变换成另外的压缩符号，然后将压缩有信息
经信道传送到信宿。只考虑信源和信宿两个
因素。通信系统模型简化为 P15图 2-1
编码 A器输入为,},,,{),,,,,( 211 nlLl uuussssS ??? ??
编码器输出的码字为,},,,{),,,,,(
211 mkKk bbbssxxX ??? ??
符号 码 1 码 2 码 3 码 4
等长码 变长码
u1 00 0 0 1
u2 01 10 11 01
u3 10 00 00 001
u3 11 01 11 0001
2,2,1 信源编码的基本概念
树图（码树）法：
树根 =码字的起点
树的度 =码元数
分支结点 =码的符号的一部分
终端结点 =待编码符号
满树 =等长码：
树中各结点有相同树枝数，且每层结点树达到最大值。
非满树 =变长码
2,2,1 信源编码的基本概念
? 编码方法：
1）将待编码的字符作为终端结点，构造码树；
2）按一定规则给每个树枝分配一个标记；
3）将从根到终端结点的路径上的编号依次相连，
作为该终端结点所表示的字符的编码。
2,2,1 信源编码的基本概念
? 译码方法：
1）从树根出发，根据接收到的第一个码字符号来选
择应走的第一条路径。
2）沿所选路径走到分支结点，在根据收到的第而个
码字选择应走的第二条路径。直至走到终端结点
为止。
3）根据所走路径，可立即判断出接收到的码符号。
4）重新返回到树根，再作下一个接收码符号的判断。
2,2,1 信源编码的基本概念
分组码 （ 块码 ） 分类
1° 按码字的码长分类
定长码,码集中所有码字的码长相等 。
变长码,码集中所有码字的码长不全相等 。
2° 按信源符号与码字对应关系分类
非奇异码,信源符号与码字是一一对应的 。
奇异码,信源符号与码字不是一一对应的 。
3° 按译码唯一性分类
唯一可译码,对于多个码字组成的有限长码流, 只
能唯一地分割一个个的码字 。 唯一可译码 又称为 单义
码,例 码流 100111000…
码 1 x1→ 0 x2→ 10 x3→ 11 可 分割 10,0,11,10,0,0
码 2 x1→ 1 x2→ 10 x3→ 11 则无法 唯一分割
唯一可译码在传输过程中不需要同步码 。
非 唯一可译码,对有限长码流, 不能唯一地分割
一个个的码字 。
4° 按译码的 即时 性分类
非即时码,接收端收到一个完整的码字后, 不能
立即译码；还需要等到下一个码字开始接收后才
能判断是否可以译码 。
即时码,接收端收到一个完整的码字后, 就能立
即译码；即时码又称为 非延长码 或 异前缀码 。
例 非即时码 码流 01001100…
x1→ 0 x2→ 01 x3→ 11 译码为 x2,x1,x1,x3,x1,?
即时码 码流 01001100…
x1→ 0 x2→ 10 x3→ 11 译码为 x1,x2,x1,x3,x1,x1
异前缀码 (即时码 )指的是码集任何一个码不能是
其他码的前缀,
即时码必定是 唯一可译码,唯一可译码不一定 是
即时码,
5° 有实用价值的分组码
分组码是 非奇异码, 唯一可译码, 即时码
