信息论 基础理论与应用第三版(傅祖芸) 第六章 讲义

这就是本章所要讨论的问题。本章的核心是香农 第二定理。
6.1 错误概率与译码规则
为了减少传输错误，提高通信的可靠性，就必须分 析错误概率与哪些因素有关，有没有办法控制？能控制 到什么程度？ 一般地，错误概率与如下因素相关： 信道的统计特性
译码规则
例：有一个BSC信道，如图所示
P(0)
信源
0 2/3 2/3
PE P(b j ) P(e / b j ) {1 P[ F (b j ) / b j ]}P(b j )
Y Y
P[ F (bj )bj ]
X ,Y Y
p(aib j ) P[a*b j ]
最小错误概率准则（最大后验概率准则）
如何设计译码规则 F (bj ) ai ，使平均错误概率最小？
决定于译码规则
PE E P(e / b j ) P(b j ) P(e / b j )
j 1


s
min PE P(b j ) min P(e / b j )
j 1 s
s

4
码D
8
码字
000 111
000 011 101 110
当n=5时 当n=7时 当n=9时 当n=11时
PE 105 PE 4 107 PE 108 PE 5 10
10
但是n很大时，信道的信息传输率会降低很多：（M为许用码 字的个数，即输入消息个数，n为编码后码字的长度）
在上例中：M=2
当n=1时 当n=3时 当n=5时 R=1 R=1/3 R=1/5
010
011 100 101 110
1 2 3 4 5 6 7 8
011
100 101 110 111
111 （表示1）
1 2 3 4 5 6 7 8
则信道矩阵为：
000
001
010
011
100
101
110
111
p 3 p 2 p p 2 p pp 2 p 2 p pp 2 pp 2 p 3 000 P 3 2 2 2 2 2 2 3 pp pp p p pp p p p p p 111 p 根据最大似然译码准则，当p=0.01，可得译码函数为：
k 1
如：
i 101111
则
j 111100
D(i , j ) 3
在某一码中，任意两个码字Ci、Cj的汉明距离的最小值称为该 码C的最小距离。
dmin min{D(Ci , C j )}
Ci C j
讨论4种码的距离和错误概率（码长=3）：
码A
消息数M 2
码B
4
码C
PE P(0) 1 P

(0) e
P(1)1 P
(1) e
可见错误概率与译码规则有关。
译码规则：
输入符号集 输出符号集 译码规则
例：某信道转移矩阵
A {ai }, i 1,2,...r
B {b j }, j 1,2,...s
F (bj ) ai
0.5 0.3 0.2 P 0.2 0.3 0.5 0.3 0.3 0.4
3
一般地，有如下规律： 在二元信道的n次扩展信道中，选取其中的M个作为消息，则 M大一些， PE 跟着大，R也大；M小一些， PE 跟着小，R也小。 如果上例中，取M＝4，如：取000 011 101 110为消息，则 2 2 PE 2*10 R 3 与M=8比较，错误率降低了，而信息率也降低了。
而在第二种方法中，如果000中任何一位出错，就变成了其他的 合法的码字，我们无法判断是否出错。
再仔细观察，发现第二种方法中，码字之间太相似。
码字距离：
长度为n的两个码字对应位置上不同码元的个数。通常称 为汉明距离：
在二元码中，码字的汉明距离：
n
D( i , j ) ik jk
可以设计译码准则： A：
和
B：
F (b1 ) a1
F (b1 ) a1
F (b2 ) a2
F (b3 ) a3
F (b2 ) a3
F (b3 ) a2
总的译码规则数目 r s
信道的s个输出符号的每一个译码输出有 r 种选择，因此，总的 译码规则总数为
r
s
译码规则的选择依据
一个自然的依据就是使平均错误概率最小。 为了选择译码规则，需要计算平均错误概率。
平均错误概率：
PE'''
Y , X a*
P(a )P(b
i
j
| ai )
Y , X a*

P(ai b j )
(0.125 0.05) (0.075 0.075) (0.05 0.125) 0.5 PE''
6.2 错误概率与编码方法
一般信道传输时都会产生错误，而选择译码准则并 不会消除错误，那么如何减少错误概率呢？下边讨论通 过编码方法来降低错误概率。 例：对于如下二元对称信道

条件错误概率 条件正确概率
s
P(b j ) min( 1 P(ai / b j )) P(b j ) 1 max P(ai / b j )
j 1 j 1


*


因此应选择译码规则 F (bj ) a 满足关系：
i为待定
P(a / bj ) P(ai / bj )
0.125 0.075 0.05 0.05 0.075 0.125 P ( a b ) P(aib j ) P(ai ) P(b j | ai ) i j 0.2 0.15 0.15 F (b1 ) a3 所得译码函数为：C： F (b ) a 2 3 F (b ) a 3 3
X ,Y Y
平均正确概率

Y , X a*
P(a b ) P(a )P(b
i j i Y , X a*
j
| ai )
信道传递概率
上式中，平均错误概率计算是在联合概率矩阵[P(ai)P(bj|ai)]中： 1）先求每一列除去F(bj)=a*所对应的P(a*bj)以外的元素之和；
2）然后，对所有列求和。
另外一个问题，消息数固定而编码选取方法不同，错误率也不同。 比较两种选取方法：
第一种： 000 011 101 110
第二种： 000 001
010 100
可以计算得第一种方法的错误率为 第二种方法的错误率为
2*102 2.28*10
2
比较可知，第一种方法好。仔细观察发现： 在第一种方法中，如果 000 有一位出错，就可以判定出错了；
1 1 1 P(a1 ) , P(a2 ) , P(a3 ) ，则错误概率为： 4 4 2
PE''
Y , X a*

P(a) P(b | a)
1 / 4(0.3 0.2) 1 / 4(0.3 0.3) 1 / 2(0.2 0.5) 0.6
2）采用最小错误概率译码准则，则联合矩阵为：
（选讲）当然，也可以对联合概率矩阵[P(ai)P(bj/ai)]中： 1）先求每一行中除去F(bj)=ai*所对应的P(aibj)以外的元素之和; 2）然后，对各行的和求和。
具体计算如下：
PE
即：
Y , X a*
P(a ) P(b
i
X
j
| ai )
X Y ( a*对应的 b j )
1/ 2 p3 p p 2 p p 2 p p 2 p p 2 p p 2 p p 2 p3 p 3 3 p p 2 3 10 4 ( p 0.01)
PE 0.01 102

Y 3C *
P(
j
| i )

现在码元个数n=3，已经将错误概率降低了两个数量级；若重 复更多次，n=5，7，…，还可以进一步降低错误概率，上例中：
平均错误概率分析：
译码规则确定后，设信道输出端收到 bj时一定译为 ai。 如果发送端刚好发送的就是 确概率为：
ai，则为正确译码，译码的条件正
P(F (bj ) / bj ) P(ai / bj )
而错误译码的概率为收到 bj 后翻译为 ai ，但发送端实际上 发送的却不是 ai ，则为错误译码，其条件错误概率为：
即
P(a*b j ) P(aib j )
最大似然译码准则
当信源等概分布时，则最小错误概率准则变为
P(bj / a* ) P(bj / ai )
这称为最大似然译码准则，方法是收到一个 bj 后，在信道矩 阵的第j列元素中选择最大的值所对应的输入符号作为译码输出。
平均错误概率的计算
当译码规则确定后，可进一步计算平均错误概率：
0.5 0.3 0.2 P 0.2 0.3 0.5 0.3 0.3 0.4
1 1 PE P(b / a) [(0.2 0.3) (0.3 0.3) (0.2 0.4)] 0.567 3 Y , X a* 3
若输入不等概分布
0 0.01 0.01 1 0.99 1 0.99
0
按照最大似然准则译码， PE 0.01 102
如何提高信道传输的正确率呢？可用重复消息的方法，即尝试 扩展信道的方法。
未用的码字 （禁用码字） 001 用作消息的码字 （许用码字） 000 （表示0） 输出端 接收序列 000 001 010 二元对称信 道的三次扩 展信道
P(e / bj ) 1 P(ai / bj )
e表示：除了