第五章 有噪信道编码
第一节 错误概率与译码规则
第二节 错误概率与编码方法
第三节 有噪信道编码定理
第四节 联合信源信道编码定理
第六节 纠错编码的基本思想
第七节 常用编码方法
第五章 有噪信道编码
前一章已经从理论上讨论了,对于无噪无损信道只要
对信源进行适当的编码,总能以信道容量无差错的传递
信息。但是一般信道总会存在噪声和干扰,那么在有噪
信道中进行无错传输可以达到的最大信息传输率是多少
呢?这就是本章所要讨论的问题。本章的核心是香农第
二定理。
第一节 错误概率与译码规则
为了减少错误,提高通信的可靠性,就必须分析错误
概率与哪些因素有关,有没有办法控制,能控制到什么程
度。
前边已经讨论过,错误概率与信道的统计特性有关,
但并不是唯一相关的因素,译码方法的选择也会影响错误
率。
第一节 错误概率与译码规则
例:有一个 BSC信道,如图所示
0
1
0
1
1/3
1/3
2/3
2/3
若收到, 0”译作, 0”,收到, 1”译作, 1”,则平均错误概率
为:
( 0 ) ( 1 ) 2( 0 ) (1 ) 3E e eP P P P P? ? ?
反之,若收到, 0”译作, 1”,收到, 1”译作, 0”,则平
均错误概率为 1/3,可见错误概率与译码准则有关。
第一节 错误概率与译码规则
我们来定义译码准则:
输入符号集
输出符号集
译码规则
{}iAa?
{}iBb?
()jiF b a?
例,0.5 0.3 0.2
0.2 0.3 0.5
0.3 0.3 0.4
P
??
???
????
第一节 错误概率与译码规则
译码规则的选择应该有一个依据,一个自然的依据就
是使平均错误概率最小
有了译码规则以后,收到 的情况下,译码的条件正
确概率为:
( ( ) / ) ( / )j j i jP F b b P a b?
jb
可以设计译码准则,A,11()F b a?
22()F b a?
33()F b a?
和 B:
11()F b a?
23()F b a?
32()F b a?
第一节 错误概率与译码规则
而错误译码的概率为收到 后,推测发出除了 之
外其它符号的概率,jb ia
( / ) 1 ( / )j i jP e b P a b??
可以得到平均错误译码概率为:
11
( ) ( / ) ( ) ( 1 ( / ) )
ms
e j j j i j
jj
P p b P e b p b P a b
??
? ? ???
它表示经过译码后平均没收到一个符号所产生错误的
大小,也称 平均错误概率 。
第一节 错误概率与译码规则
下面的问题就是如何选择,经过前边的讨论可以看
出,为使 最小,就应选择 为最大,
即选择译码函数 并使之满足条件:
( / )ijP a b
( ( ) / )jjP F b b( / )jP e b
*()jF b a?
**( / ) ( / )j i j iP a b P a b a a??
也就是说,收到一个符号以后译成具有最大后验概率
的那个输入符号。这种译码准则称为, 最大后验概率准
则, 或, 最小错误概率准则, 。
根据贝叶斯定律,上式也可以写成
**( / ) ( ) ( / ) ( )
( ) ( )
j j i i
jj
P b a P a P b a P a
P b P b?
第一节 错误概率与译码规则
即,**( / ) ( ) ( / ) ( )
j j i iP b a P a P b a P a?
当信源等概分布时,上式为:
*( / ) ( / )j j iP b a P b a?
这称为最大似然译码准则,方法是收到一个 后,
在信道矩阵的第 j列,选择最大的值所对应的输入符号作
为译码输出。
jb
可进一步写出平均错误概率:
( ) ( / ) { 1 [ ( ) / ] } ( )E j j j j j
YY
P P b P e b P F b b P b? ? ???
,
( ) [ ( ) ]i j j j
X Y Y
p a b P F b b????1 [ ( ) ]jjY P F b b?? ?
*
,
( ) [ ]i j j
X Y Y
p a b P a b????
*,
()ij
X Y a
P a b
?
? ?
第一节 错误概率与译码规则
也可写成:
*,
( / ) ( )E j i i
X Y a
P P b a P a
?
? ?
上式也可写成对行求和:
? ?( ) ( / ) ( )E i j i j
XY
P P a P b a F b a ?????
()() iie
X
P a P? ?
如果先验概率相等,则:
()1 i
EeXPPr? ?
第一节 错误概率与译码规则
例,0.5 0.3 0.2
0.2 0.3 0.5
0.3 0.3 0.4
P
??
???
????
根据最大似然准则可选择译码函数为 B:
11
23
32
()
()
()
F b a
F b a
F b a
??
? ?
?
? ??
*,
11 ( / ) [ ( 0.2 0.3 ) ( 0.3 0.3 ) ( 0.2 0.4) ] 0.567
33E Y X aP P b a?? ? ? ? ? ? ? ??
第一节 错误概率与译码规则
若采用前边讲到的译码函数 A,则平均错误率为:
*
'
,
11 ( / ) [ ( 0.3 0.2 ) ( 0.3 0.3 ) ( 0.2 0.5 ) ] 0.6
33E Y X aP P b a?? ? ? ? ? ? ? ??
若输入不等概分布,其概率分布为:
1 2 3
1 1 1( ),( ),( )4 4 2P a P a P a? ? ?
*
''
,
1 1 1 1( / ) ( 0,3 0,2) ( 0,3 0,3 ) ( 0,2 0,5 ) 0,6
3 4 4 2E Y X aP P b a?? ? ? ? ? ? ? ??
第一节 错误概率与译码规则
若采用最小错误概率译码准则,则联合矩阵为:
0.125 0.075 0.05
( ) 0.05 0.075 0.125
0.15 0.15 0.2
ijP a b
??
???? ?
??
??
所得译码函数为,C:
13
23
33
()
()
()
F b a
F b a
F b a
??
? ?
?
? ??
平均错误率为:
*
'''
,
1 ( / ) ( 0.1 25 0.0 5 ) ( 0.0 75 0.0 75 ) ( 0.0 5 0.1 25 ) 0.5
3E Y X aP P b a?? ? ? ? ? ? ? ??
第二节 错误概率与编码方法
一般信道传输时都会产生错误,而选择译码准则并不会
消除错误,那么如何减少错误概率呢?下边讨论通过编码
方法来降低错误概率。
0
1
0
1
0.99
0.99
0.01
0.01
例:对于如下二元对称信道
20.01 10EP ???
第二节 错误概率与编码方法
如何提高信道传输的正确率呢?可以尝试用下面的方法
没有使用
的码字
001
010
011
100
101
110
用作消息
的码字
000
111
输出端接
收序列
000
001
010
011
100
101
110
111
二元对称信道的
三次扩展信道
第二节 错误概率与编码方法
则:
3 2 2 2 2 2 2 3
3 2 2 2 2 2 2 3
p p p p p p p p p p p p p pP
p p p p p p p p p p p p p p
??? ??
??
根据最大似然译码准则,可得译码函数为:
F(000)=000 F(001)=000 F(010)=000 F(011)=111
F(100)=000 F(101)=111 F(110)=111 F(111)=111
3*
4( ) ( / ) 3 * 1 0E i j i
Y C a
P P P? ? ? ?
?
???
此时,译码可以采用, 择多译码,,即根据接收序列中 0
多还是 1多,0多就判作 0,1多就判作 1。错误概率降低了两
个数量级,这种编码可以纠正码字中的一位码元出错。若
重复多次可进一步降低错误率
第二节 错误概率与编码方法
但是又出现了一个新的问题,n很大时,信息传输率会
降低很多,
log MR
n?
在上例中,M=2
当 n=1时 R=1
当 n=3时 R=1/3
当 n=5时 R=1/5
......
第二节 错误概率与编码方法
这显然是一个矛盾,有没有解决的办法呢?香农第二定
理可以解决这一问题。
我们分析前边的例子,我们只用了扩展信源的两个字符,
因此信息率降低了,如果我们把 8个字符全用上,信息传输
率就会回到 1,但是此时错误率为 比单符号时还大三
倍。我们可以总结如下:在二元信道的 n次扩展信道中,选
取其中的 M个作为消息,则 M大一些,跟着大,R也大,
M小一些,跟着小,R也小。
EP
EP
如果在上例中,取 M= 4,如:取 000 011 101 110为
消息,其他的不用,则
则与 M=8比较,错误率降低了,而信息率也降低了。
2 22 * 1 0 3EPR???
23*10?
第二节 错误概率与编码方法
还存在另外一个问题,M=4时,有 70种选取方法,而
选取方法不同,错误率也不同。我们比较下面两种选取方
法:第一种,000 011 101 110
第二种,000 001 010 100
可以计算得第一种方法的错误率为
第二种方法的错误率为
22*10?
22.28 *10 ?
比较可知,第一种方法好,仔细观察发现,在第一种方
法中,如果 000有一位出错,我们就可以判定出错了;而在
第二种方法中,如果 000中任何一位出错,就变成了其他的
合法的码字,我们无法判断是否出错。再仔细观察,发现第
二种方法中,码字之间太, 象, 了,或者说太, 近, 了。
第二节 错误概率与编码方法
我们再讨论一个例子,取 M= 4,n= 5,这 4个码字按
如下规则选取:
设输入序列为,
1 2 3 4 5()i i i i i ia a a a a a?
满足方程:
3 1 2
41
5 1 2
i i i
ii
i i i
a a a
aa
a a a
???
? ?
?
? ???
若译码采取最大似然准则:
2
5R?
第二节 错误概率与编码方法
00000
00001
00010
00100
00000
01000
10000
10001
00011
?
?
?
?
?
?
?
?
?
?
?
?
?
01101
01100
01111
01001
01101
00101
11101
11100
01110
?
?
?
?
?
?
?
?
?
?
?
?
?
10111
10110
10101
10011
10111
11111
00111
00110
10100
?
?
?
?
?
?
?
?
?
?
?
?
?
11010
11011
11000
11110
11010
10010
01010
01011
11001
?
?
?
?
?
?
?
?
?
?
?
?
?
此码能纠正所有码字中一位码元错误,也能纠正其中两个
两位码元的错误。
5 4 3 252EP p p p p p? ? ?
5 4 3 2 41 1 ( 5 2 ) 7,8 10EEP P p p p p p ?? ? ? ? ? ? ? ?
第二节 错误概率与编码方法
我们引进这样一个概念,汉明距离 。
在二元码中:
1
(,) ni j ik jk
k
D ? ? ? ?
?
???
如,101111
i? ? 111100j? ?

(,) 3ijD ?? ?
在某一码书中,任意两个码字的汉明距离的最小值称为
该码 C的最小距离 。
m in m i n{ (,) }i j i jd D C C C C??
我们来讨论前边的 5种码的距离:
第二节 错误概率与编码方法
码 A 码 B 码 C 码 D
码字 000
111
000
011
101
110
000
001
010
100
000 001
010 011
100 101
100 111
消息数 M 2 4 4 8
最小距离
dmin
3 2 1 1
信息传输率 R 1/3 2/3 2/3 1
错误概率
43*10? 22*10? 22.28 *10 ? 23*10?
第二节 错误概率与编码方法
很明显,越大,越小,在 M相同的情况下也是一样mind EP
在二元对称信道的情况下,译码规则可以如下:
*()jF b a?选择
使之满足 **(,) (,)j i j iDD? ? ? ? ? ???
它称为 最小距离译码准则,它等价与最大似然译码准则,
也就是收到一个码字后,把它译成与它最近的输入码字,
这样可以使平均错误率最小。
另外,我们应该选择这样的编码方法:应尽量设法使
选取的 M个码字中任意两两不同码字的距离尽量大。
第三节 有噪信道编码定理(香农第二定理)
1,有噪信道编码定理
如一个离散无记忆信道,信道容量为 C。当信息传输
率 R≤C时,只要码长足够长,总可以在输入符号集中
找到 M 个码字组成的一组码 和相应的译码
准则,使信道输出端的平均错误译码概率达到任意小。
nX
( 2 )nR? (2,)nR n
第三节 有噪信道编码定理(香农第二定理)
2,有噪信道编码逆定理
如一个离散无记忆信道,信道容量为 C。当信息传输
率 R>C时,则无论码长 n多长,总找不到一种编码
使信道输出端的平均错误译码概率达到任意小。
(2,)nR n
第三节 有噪信道编码定理
这个定理是信道编码的理论依据,可以看出:信道容量
是一个明确的分界点,当取分界点以下的信息传输率时,
以指数趋进于 0;当取分界点以下的信息传输率时,以指
数趋进于 1;因此在任何信道中,信道容量都是可达的、最
大的可靠信息传输率。
这个定理是一个存在定理,它没有给出一个具体可构造
的编码方法,在它的证明过程中,码书是随机的选取的,它
有助于指导各种通信系统的设计,有助于评价各种系统及编
码的效率。
EP
EP
第四节 联合信源信道编码定理
从香农第一、第二定理可以看出,要做到有效和可靠的
传输信息,我们可以将通信系统设计成两部分的组合,即
信源编码和信道编码两部分,首先通过信源编码,用尽可
能少的信道符号来表达信源,尽可能减少编码后信源的数
据的剩余率,然后针对信道,对信源编码后的数据独立的
进行信道编码,适当增加一些剩余度,使能纠正和克服信
道中引起的错误和干扰。
我们可以证明,只要满足香农第一定理和第二定理,
用两步编码的方法传输信息和一步编码的方法传输信息其
效果是一样的。