1
第十二章 信息理论
12.1 离散信源的熵
熵的定义:
设:信源 X 能发出 n个不同的消息 x1,x2,…,xi,…,xn,
则定义熵为信源的平均信息量 H(X):
式中,I (xi) = - log2 P(xi) (b)
I (xi)表示消息 xi含有的信息量
熵 H(X)可以理解为信源的平均不确定度。
n
i
iii xPxPxIEXH
1
2 )(lo g)()]([)(
2
二进制信源的熵
设,信源仅有,0”和,1”两种消息。
发送,1”的概率 P(1) =?,
则 发送,0”的概率 P(0) = 1 -? =?
信源的熵等于
若一个消息是一个码元,则熵 H(?)的单位:比特 / 码元
H(?)~?曲线
当?= 1/2时,此信源的熵最大;这时的两个消息是等概率出现的,其不确定度最大。
当 1/2时,一个消息比另一个消息更可能出现,因此不确定度减小。
若?或? 等于 0,则不确定度为 0。
)1(l o g)1(l o g
)0(l o g)0()1(l o g)1()(
22
22


PPPPH
3
n 进制信源的熵
设:信源有 n种可能出现的消息,并用 Pi表示第 i个消息的出现概率,
则由熵的定义可以写出此信源的熵
熵的最大值:
令上式对 Pk的导数等于 0,求 H的最大值。
由于故当 Pk变时,可仅使 Pn随之变化,并保持其他 Pi为常数。
于是得到利用求导数公式上式变为或
)(1 121 nin PPPPP
n
i
ii PPH
1
2lo g
)lo glo g( 22 nnkk
kk
PPPPdP ddPdH
dx
due
uudx
d
aa lo g
1lo g?
n
n
nk
k
k
k
PePPPePPdPdH 2222 lo glo g1lo glo g1
k
n
k P
P
dP
dH
2lo g?
4
令等于 0,就可以求出 H的最大值。
当 Pk = Pn,上式等于 0。由于 Pk是任意一个消息的出现概率,所以有将上式代入得到 H的最大值:
k
n
k P
P
dP
dH
2lo g?
nPPP n
1
21
nH 2lo g?
n
i
ii PPH
1
2lo g
5
12.2 离散信道模型
二进制无记忆编码信道的模型
信道的特性:由下列信道转移概率矩阵所完全确定式中,P(yj /xi) - 发送 xi,收到 yj 的条件概率。
信道输入和输出概率关系若输入概率矩阵为则由可以计算出
11
P(1 / 0)
P(0 / 1)
0 0
P(0 / 0)
P(1 / 1)
发送端 接收端
)/()/( )/()/()/(
2221
1211
xyPxyP
xyPxyPXYP
)()()( 21 xPxPXP?
)()()( 21 yPyPYP?
)/()()( XYPXPYP?
6
输入输出的联合概率矩阵 P(X,Y)
将 [P(X)]写成对角线形式:
并与相乘,得到联合概率矩阵 P(X,Y):
式中,
- 发送 xi 收到 yj 的联合概率
)(0 0)()(
2
1
xP
xPXP
)/()/( )/()/()/(
2221
1211
xyPxyP
xyPxyPXYP


),(),(
),(),(
)/()()/()(
)/()()/()(
)/()/(
)/()/(
)(0
0)(
)/()(),(
2212
2111
222212
121111
2221
1211
2
1
yxPyxP
yxPyxP
xyPxPxyPxP
xyPxPxyPxP
xyPxyP
xyPxyP
xP
xP
XYPXPYXP
)/()(),( ijiji xyPxPyxP?
7
例 1:设有一个二进制信道,如图所示,
其转移矩阵为:
若信道输入的概率为试求输出概率矩阵 P(Y)和联合概率矩阵 P(X,Y)。
[解 ] 输出概率矩阵,
联合概率矩阵,
0.3
0.4
x1 y1
y2x2
0.7
0.6
发送端 接收端



6.04.0
3.07.0)/( XYP
5.0)(5.0)( 21 xPxP 和
45.055.06.04.0 3.07.05.05.0)(YP
3.02.0 15.035.06.04.0 3.07.05.00 05.0),( YXP
8
12.3 联合熵和条件熵设:一信道有 n个可能输入和 m个可能输出,
则可用输入概率 P(xi),输出概率 P(yj),转移概率 P(yj/xi)和联合概率 P(xi,yj)定义下列不同的熵函数:
- 信源的平均不确定度;
- 接收码元的平均不确定度;
-给定发送 X后接收码元的平均不确定度;
-收到一个码元后发送码元的平均不确定度;
-整个通信系统的平均不确定度。
联合熵公式:
n
i
ii xPxPXH
1
2 )(lo g)()(
m
i
jj yPyPYH
1
2 )(lo g)()(


n
i
m
j
ijji xyPyxPXYH
1 1
2 )/(l o g),()/(


n
i
m
j
jiji yxPyxPYXH
1 1
2 )/(l o g),()/(


n
i
m
j
jiji yxPyxPYXH
1 1
2 ),(l o g),(),(
)()/(),( YHYXHYXH )()/(),( XHXYHYXH
9
12.4 无噪声信道容量
互信息量 I (X; Y)
定义:在收到发送码元后,此发送码元的平均不确定度的下降量式中,H(X) - 信源的平均不确定度;
H(X / Y) - 收到一个码元后发送码元的平均不确定度上式可以改写为
性质:
信道容量 C
定义:互信息量的最大值
( b/码元)
性质,C 仅是信道转移概率的函数;
C是一个码元能够传输的最大平均信息量。
)/()();( YXHXHYXI
)/()();( XYHYHYXI
0);(?YXI
);(m a x YXIC?
10
例 2:试求下图中的无噪声离散信道的容量。
【 解 】 由式及式可知,对于无噪声信道,
当 i? j 时,P(xi,yj) = 0,P(xi / yj) = 0;
当 i = j 时,P(xi / yj) = 1。
因此,H(X / Y) = 0,I(X; Y) = H(X)
若信源中所有码元是等概率的,则信源的熵 H(X)最大。
因此,
x1
x2
xn
y1
y2
yn
1
1
1
无噪声离散信道
)/()();( YXHXHYXI


n
i
m
j
jiji yxPyxPYXH
1 1
2 )/(l o g),()/(
nnnYXIC n
i
2
1
2 lo glo g
1);(m a x
11
例 3:试求图中二进制对称信道的容量。
其中 P(x1) =?,P(x2) = 1 -?。
【 解 】 根据信道容量的定义式,
需要求出的最大值。
上式右端第二项为将 P(x1) =?,P(x2) = 1 -?和转移概率 p,q代入上式,得出上式可以化简为将上式代入得到
p
p
q
q发送端 接收端
x2
x1 y1
y2)/()();( XYHYHYXI


2
1
2
1
2 )/(l o g),()/(
i j
ijji xypyxpXYH
qqqppppXYH 2222 l o g)1(l o gl o g)1(l o g)/(
qqppXYH 22 l o gl o g)/(
)/()();( XYHYHYXI
qqppYHYXI 22 l o gl o g)();(
12
当 H(Y)为最大时,上式达到最大。 H(Y)的最大值等于 1,故按照上式画出的曲线:
二进制对称信道的误码率 Pe
式中,P( e/xi )为给定输入 xi 条件下的误码率,所以有上式表明无条件误码率 Pe等于条件误码率 P( yj / xi ),i? j。
qqppYHYXI 22 l o gl o g)();(
)(1l o gl o g1)];(m ax [ 22 pHqqppYXIC
C
2
1
)()/(
i
iie xPxePP
qxqPxqPP e )()( 21
13
12.5 信源编码
12.5.1无噪声信道编码原理
信源的信息速率 Rs:
式中,H(X) - 信源的熵 ( b/码元);
r - 码元速率 (波特 = 码元 /s)。
无噪声信道编码定理(香农第一定理):
给定一个信道和一个信源,若此信源以小于信道容量 C的速率 Rs产生信息,则一定能够以某种方式对信源的输出编码,
使得编码输出能够无差错地通过此信道传输;但是若信源输出速率 Rs大于容量 C,则不可能无差错地传输。
)/()( sbXrHR s?
14
例:
设:有一个二进制信源,它有两个可能的输出 A和 B,
P(A) = 0.9,P(B) = 0.1
信源输出的码元速率 r = 3.5 (码元 /s)
信道无误传输的码元速率 S = 2 (码元 /s)
则从例 3可知,在 p = 1时,信道容量 C = 1 ( b / 码元)。
故现在信道的信息速率 = SC = 2 (b / s)
现在,r > S,所以信源的码元不能直接送入信道。
然而,信源的熵为它相当于信源信息速率为
∵ 现在,信源的信息速率 rH(X) < 信道的信息速率 SC,
∴ 有可能传输,但需要在传输之前作信源编码。
二进制信源 信源编码器 二进制信道信源的码元速率:
r = 3.5 码元 /s
C = 1b/码元
S = 2 码元 /s
SC = 2 b/s
)/(469.09.0l o g9.01.0l o g1.0)( 22 码元bXH
)/(6 4 2.1)4 6 9.0(5.3)( sbXrH
15
信源的扩展:把信源中的 n个码元编成一组,称为码字。
将最短的码字分配给最有可能出现的信源码元组,并将最长的码字分配给最少可能出现的信源码元组。这样,信源编码就降低了平均码元速率,使信源能和信道匹配。
这种编码称为信源的扩展。
信源的 n阶扩展:将原始信源中的 n个码元编成一组。
1阶扩展:
这时编码器输出的码元速率等于信源的码元速率。
故在信道输入端的码元速率仍然大于信道的传输能力。
信源码元 码元概率 P(xi) 码字 码字长度 li P(xi)li
A 0.9 0 1 0.9
B 0.1 1 1 0.1
L=1.0
16
2阶扩展:将原始信源中的 2个码元编成一组,构成原始信源的 2阶扩展平均码字长度 L等于式中,P(xi) - 扩展信源中第 i个码组的概率,
li - 第 i个码组对应的码字的长度。
每个信源码元在编码后码字中占用的平均码元数为编码器输出的码元速率为它仍然高于信道的传输能力( 2码元 /s),
故码元速率还需要进一步减小。
信源码元 码元概率 P(xi) 码字 码字长度 li P(xi)li
AA 0.81 0 1 0.81
AB 0.09 10 2 0.18
BA 0.09 110 3 0.27
BB 0.01 111 3 0.03
L=1.29
29.1)(2
1

n
i
ii lxPL
645.0229.1)(1 ii lxPnnL
2 5 8.2)6 4 5.0(5.3nLr
17
3阶扩展:
平均码字长度,L = 1.598
每个信源码元在编码后码字中占用的平均码元数为编码器输出的码元速率为这一速率可以为信道所接受,所以能用 3阶扩展传输。
信源码元 码元概率 P(xi) 码字 码字长度 li P(xi)li
AAA 0.729 0 1 0.729
AAB 0.081 100 3 0.243
ABA 0.081 101 3 0.243
BAA 0.081 110 3 0.243
ABB 0.009 11100 5 0.045
BAB 0.009 11101 5 0.045
BBA 0.009 11110 5 0.045
BBB 0.001 11111 5 0.005
L=1.598
533.03598.1)(1 ii lxPnnL
864.1)533.0(5.3nLr
18
L/n和 n的关系曲线从曲线可以看出,L/n永远大于信源的熵,并且当 n增大时收敛于信源的熵。
19
12.5.2 信源编码的分类和效率
有关定义
字母表:若干个符号的集合
码字:由一个字母表中的若干符号构成
字长:码字中符号的数目
码元:在信道中传输的符号
信源编码的分类
非分组码
分组码:码长是固定的
唯一可译码:
其码字不用空格区分就可以译出。
瞬时码
非瞬时码,需要参考后继码字译码例:
信源符号 非瞬时码 瞬时码
x1 0 0
x2 01 10
x3 011 110
x4 0111 1110
20
信源编码的效率
效率定义:
码字的最小平均字长 Lmin 和码字的平均字长 L 之比式中,P(xi) - 第 i 个信源符号的概率,
li - 对应第 i 个信源符号的码字的长度。
可以证明,最小平均字长等于式中,H(X) - 被编码的消息集合的熵,
D - 编码字母表中的符号数目
将上两式合并,得到
对于二进制 (D = 2)而言,上式变成由上式看出,若效率为 100%,则平均字长 L应等于熵 H(X)。
n
i
ii lxPLLL
1
m i nm i n )(//效率
DXHL 2m i n l o g/)(?
DLXH 2l o g/)(?效率
LXH /)(?效率
21
12.5.3 扩展二进制信源的熵
可以证明,一个离散无记忆信源的第 n阶扩展的熵等于
所以,扩展信源的效率为
若当 n趋向于无穷大时,效率趋近 100%,则 L/n趋近于扩展信源的熵。这可以从下图看出。
nL
XH
L
XnH
/
)()(效率
)()( XnHXH n?
22
12.5.4 香农 -费诺码 -- 编码方法举例
首先将信源符号 xi按照出现概率不增大的次序排列;
然后将信源符号划分成两组(用虚线 A-A‘标出),使每组中符号的概率尽可能相等;
将,0”分配给上组,,1”分配给下组;
如此进行下去,直至不能再划分为止。
若每次划分都能给出等概率的分组,则这种方法能给出 100%
效率的编码。
此例的效率,信源符 号 出现概率 码字 码长 码长?概率
x1 0.2500 00 2 0.5
x2 0.2500 01 2 0.5
A -----A’
x3 0.1250 100 3 0.375
x4 0.1250 101 3 0.375
x5 0.0625 1100 4 0.25
x6 0.0625 1101 4 0.25
x7 0.0625 1110 4 0.25
x8 0.0625 1111 4 0.25
平均字长= 2.75
%100175.2 75.2)( L XH效率
23
信源输出 x7和 x8合并的结果消息 概率 消息 概率
x1 0.2500 x1 0.2500
x2 0.2500 x2 0.2500
x3 0.1250 x3 0.1250 0
x4 0.1250 x4 0.1250 1
x4? 0.1250 0
x5 0.0625 x5 0.0625 0
x6 0.0625 x6 0.0625 1
x7 0.0625 0
x8 0.0625 1
编码得到的码字
x1 10
x2 11
x3 010
x4 011
x5 0010
x6 0011
x7 0000
x8 0001
0
0
1 1
1
0
1
12.5.5 霍夫曼码
对于给定熵的信源,霍夫曼码能得到最小平均字长。
编码过程举例
将信源消息 xi 按照概率不增大的次序排列 ;
将概率最小的两个信源消息 x7 和 x8 合并 ;
为 x7分配,0”,x8分配,1”,作为其码字的最后一个符号;
将 x7和 x8合并后看成是一个复合消息 x4?;
24
令复合消息 x4?的 概率等于 x7和 x8的概率之和,即 0.1250 ;
将消息 x1,x2,x3,x4,x5,x6和 x4?仍按概率不增大的次序排列 ;
将消息 x5和 x6合并,将合并结果再和 x4?合并;
如此进行到最后,得到了一个树状结构;
从树的最右端向左追踪,就得到了编码输出码字。
信源输出 x7和 x8合并的结果消息 概率 消息 概率
x1 0.2500 x1 0.2500
x2 0.2500 x2 0.2500
x3 0.1250 x3 0.1250 0
x4 0.1250 x4 0.1250 1
x4? 0.1250 0
x5 0.0625 x5 0.0625 0
x6 0.0625 x6 0.0625 1
x7 0.0625 0
x8 0.0625 1
编码得到的码字
x1 10
x2 11
x3 010
x4 011
x5 0010
x6 0011
x7 0000
x8 0001
0
0
1 1
1
0
1
25
从霍夫曼编码得到的码字与香农 -费诺编码得到的不同,因为将复合消息插入到哪些点是有任意性的。将二进制数字,0”
和,1”分配给上面或下面的消息也是任意的。
然而,这两种编码的平均字长是一样的。在这个例子中,
因为香农 -费诺码给出 100%的效率,所以霍夫曼码自然不会比它差。
但是,一般而言,这两种编码方法给出的平均字长不一定相等。
26
12.6 白色加性高斯噪声信道的容量
香农第二定理:给定一个容量为 Cc的离散无记忆信道和一个正速率为 R的信源,若 R < Cc,则必定有一种编码,当其足够长时,使信源的输出能以任意小的错误概率通过此信道传输。
对于白色加性高斯噪声的连续信道,它能够传输的最大信息速率由下式给出:
-- 香农 -哈特莱 (Shannon-Hartley)定律式中,B - 信道带宽( Hz),
S/N - 信号噪声功率比。
Cc - 信道传输的最大信息速率 (b / s)。
)/()1(l o g 2 sbNSBC c
27
容量 Cc的特性
保持 Cc不变,带宽 B和信噪比 S/N可以交换。
对于无噪声情况( S/N =?),只要带宽不为 0,则容量 Cc
将是无穷大。
在有噪声情况下,当 B时,Cc趋向于如下极限值:
【 证 】 令 x = S/n0B,代入得到因为当 x? 0时,ln(1 +x)1/x? 1,所以上式变为
)/(44.1lim
0
sbnSC c
B

)/()1(l o g 2 sbNSBC c



Bn
SBC
BcB 02 1lo glimlim
x
BBcB
xnSBn SSBnnSC /12
00
2
0
0
1lo gli m1lo gli mli m



00
44.12lnli m nSn SC cB
28
Cc与 B的关系:按照右式画出
Cc与 Eb/n0的关系:当以速率 Rb = Cc 传输时,
码元能量:
式中,Tb = 1/Cc - 每比特的持续时间将上式代入式:
得出当 B 时,
或上式表明,对于 Rb = Cc 的理想情况,当 B 时,仅需
Eb /n0 = -1.6 dB就能实现无误传输。
cbbb CSRSSTE //
BS/n0
S/n0
S/n0ln2Cc
)/()1(l o g 2 sbNSBC c
2lnlim 0n
SC
cB
00 2ln
1
2ln
1
n
CE
n
SC cb
c dBn
E b 6.12ln
0

29
Eb/n0与 Cc/B的关系曲线:
在 Rb < Cc区域,能够得到任意小的错误概率(工作区)
在 Rb > Cc区域,不能使错误概率达到任意小
若信源比特率 Rb一定,且带宽 B足够大,使 B>>Rb,则仅需 Eb/n0略大于 -1.6 dB就可以工作在 Rb < Cc区域。
— 功率受限工作状态。
若带宽受限制,使 Rb>>B,则需要很大的 Eb/n0值才能工作在 Rb < Cc区域。 -带宽受限工作状态 。
30
信噪比和带宽关系
设:原始信号的带宽为 B1,在以信噪比 S1/N1传输时,其最大信息传输速率 R1为将此信号调制(或)编码后,若仍保持原来的信息传输速率 R1,但是带宽变成 B2,所需信噪比变成 S2/N2,则应有将上两式合并,得到或当信噪比很大时,上式变为信噪比的改善和带宽比 B2/B1成指数关系。
)1(lo g
1
1211
N
SBR
)1(lo g
2
2221
N
SBR
)1(l o g)1(l o g
2
222
1
121
N
SB
N
SB
12 /
2
2
1
1 11
BB
N
S
N
S






12 /
2
2
1
1
BB
N
S
N
S





31
带宽 B和比特能量 Eb的关系由香农 -哈特莱定律公式看出:因 n0可以认为是常数,所以增大带宽 B,可以换取 Eb的减小,即带宽和比特能量之间也同样有交换关系。
)1(l o g)/1(l o g)1(l o g
0
2
0
22 n
EB
Bn
TEB
N
SBC bbb
c
32
例 4:设 1帧黑白电视图像由 30万个像素组成,每个像素能取
10个亮度电平,并且这 10个亮度电平是等概率出现的。若每秒发送 25帧图像,要求图像信噪比达到 30 dB,试求所需传输带宽。
【 解 】 因为每个像素以等概率取 10个可能电平,所以每个像素的信息量等于而每帧图像的信息量 If 等于因为每秒有 25帧图像,故要求信息传输速率为信道容量 Cc 必须不小于此值。由于要求信噪比为 30 dB,故将这些数值代入式得出即要求
)(5.296.9/)109.24( 6 M H zB
)/(32.310l o g 2 p i xbI P
0 0 0,9 9 632.30 0 0,3 0 0fI
)/(109.240 0 0,9 0 0,24250 0 0,9 9 6 6 sb
BBB 96.91000l o g)10001(l o g109.24 226
)/()1(l o g 2 sbNSBC c
33
12.7 小结