有躁信道编码

第六章 有躁信道编码与译码

在前面，我们已经学习了如何进行信源编码以及信道的性质，在这一章，我们要考虑的问题是如何实现信息在信道的编码与译码。

我们知道信息在信道的传输过程中会有一部分损失，这就使得在信宿端对传输过来的信息进行译码时会有一些译码错误。这时候我们就会想到如果我们采用不同的译码规则，那么错误的概率肯定会不一样，于是就会想到这样两个问题：

（1）如何找到最佳的译码规则，使得译码错误概率最小。

（2）信息信源编码后信道传输之前是否可以进行信道编码：在里面加入一些多余码，以使得信息能更准确地传输到对方（就象在计算机中采用的奇偶校验一样）；在采用信道编码以后，将采用什么样的译码方法以使得译码错误概率最小。

先考虑第一个问题：

在信息序列M中没有多余码元的情况下的译码规则。 先考虑译码规则的定义：

定义1：设信道输入的符号集为X?{xi,i?1,2,...,r},输出的符号集为

Y?{yj,j?1,2,...,s},若对每一个输出符号yj都有一个确定的函数F(yj),

使yj对应于唯一的一个输入符号xi，则称这样的函数为译码规则，记为：

F(yj)?xi,i?1,2,...,r;j?1,2,...,s。

显然，对于有r个输入，s个输出的信道而言，译码规则共有：r.个。

对于一个译码规则，我们要讨论它的条件正确概率与条件错误概率。 定义2：设译码规则为F(yj)?xi,i?1,2,...,r;j?1,2,...,s。 已知信道输出端接收到的符号为yj，若发送端发送的信号为xi， 则按该规则得到的译码为正确译码；若发送端发送的信号为xk,k?i，

则按该规则得到的译码为错误译码。

在确定译码规则之前，我们先要知道如何计算一种译码规则的正确译码与错误译码的概率：

若采用译码规则F(yj)?xi(i?1,2,...,r;j?1,2,...,s)，则当信宿接收到的是yj时，在对yj进行译码时的条件正确概率为：p(xi|yj)。

而条件错误概率为：p(e|yj)?1?p(xi|yj)?1?p[F(yj)|yj]。 于是我们得到该译码规则的平均错误概率pE为：

s

pE?E[p(e|yj)]??p(yj)p(e|yj)。

j?1s这样假设我们不仅知道信道的性质p(yj|xi)(i?1,..,r,j?1,..,s),，还需要知道信源的概率分布p(xi)(i?1,2,...,r)，那么我们可以采用如下的方式进行译码：

F(yj)?x? 满足条件p(x?|yj)?p(xi|yj),我们把规则F称为最大后验概率译码规则。 该规则又称为理想观测者规则，其原因在于：

对?i，

它不仅需要知道信道的性质p(yj|xi)，还需要知道信源的性质p(xi)。 我们一般无法确定xi(1?i?n)的概率。

作业1：试求最佳译码时的平均错误概率

注意 ：最佳译码规则应该是最大后验概率译码规则。 由信源概率分布与信道概率分布矩阵我们得到：

111111111p(x1y1)???,p(x2y1)???,p(x3y1)???,224462443121113p(y1)????,于是得到:4241282p(x1|y1)?p(x1y1)/p(y1)?,同理有:312p(x2|y1)?,p(x3|y1)?p(x3y1)/p(y1)?.99于是有:F(y1)?x1.由于111111111p(x1y2)???,p(x2y2)???,p(x3y2)???,2364284624于是有:111113p(y2)????,而p(x1|y2)?,p(x2|y2)?,68243281p(x3|y2)?,于是有:8F(y2)?x1.111111由于p(x1y3)???,p(x2y3)???,261243121117p(x3y3)???p(y3)?,42824223而p(x1|y3)?,p(x2|y3)?,p(x3|y3)?,777于是有:F(y3)?x3.

33?21174pE??????8332247

11111????86624当我们无法知道信源的概率分布，而仅仅知道信道的性质时， 我们会假定输入符号为等概率分布，即：p(xi)?这时我们得到了极大似然译码规则：

极大似然译码规则： 若F(yj)?x? 满足条件：

1,ri?1,2,...,r.

p(yj|x?)?p(yj|xi),对?i。

则称为极大似然译码规则。

极大似然译码规则的平均错误概率：

pE?Y,X?x??p(xy)，而平均正确概率为：p??p(xy)，

*EY若输入为等概率分布，则

pE?

1p(y|x)。 ?rY,X?x?1312161?6?1??， 3?1?2???1?2?1例子：设信道矩阵为：??6?1??3A,B为两种译码规则：

?F(y1)?x1?A:?F(y2)?x2 ?F(y)?x33??F(y1)?x1?A:?F(y2)?x3 ?F(y)?x32?讨论这两种译码规则的平均错误概率：

pE(A)?11111111p(y|x)?[(?)?(?)?(?)]?3Y,X?x*3633663111?[3?]?322

和

pE(B)?11111111p(y|x)?[(?)?(?)?(?)]?3Y,X?x*363326211542?[??]?32663

关于错误概率pE与信道疑义度H(X|Y)的关系，有如下估计：

H(X|Y)?H(pE,1?pE)?pElog(r?1)。

现在我们来考虑第二个问题：

（2）信息信源编码后信道传输之前是否可以进行信道编码：在里面加入一些多余码，以使得信息能更准确地传输到对方（就象在计算机中采用的奇偶校验一样）；在采用信道编码以后，将采用什么样的译码方法以使得译码错误概率最小。 我们主要是考虑多余码有哪几种方式假如到码元中去？

第一种方法： 简单重复编码 例子说明：

设一二元对称信道的信道矩阵为：P???0.990.01??，

0.010.99??选择最佳译码规则为：F(y1)?x1,F(y2)?x2。 在输入分布为等概率分布条件下的平均错误概率为：

pE?11p(y|x)?(0.01?0.01)?10?2。 ?rY,X?x?2现采用简单重复编码，规定信源符号为“0”（或“1”）时，则重复发送

三个“0”（或“1”），如此发送的信道可看成是二元对称信道的三次扩展信道， 记p?0.99,p?0.01，若采用极大似然译码规则进行译码，则我们得到

1平均错误概率为：C3。 ?(10?2)2?3?10?4（？）

第二种方法：在一个二元信道的n次扩展信道中，取2个符号序列中的M 个作为消息符号传递。

第三种方法：线性码（把多余码看作是数字码的模二和）。 例子：

n?0.990.01?仍设该二元对称信道的信道矩阵为：P???，

0.010.99??设M?4,n?5，输入符号的四个码字采用下述编码方法：

ai?ai1ai2ai3ai4ai5，其中ai1与ai2为数字码，而 ai3ai4ai5

为多余码，并且它们的关系如下：

ai3?ai1?ai2,ai4?ai1,ai5?ai1?ai2

采用极大似然译码规则，可计算得到正确译码概率为：

14pE?p5?C5pp?2p3p2?1?7.8?10?4。

在介绍第四种方法之前，我们先来定义汉明距离。

汉明距离：设X?(x1,x2,...,xn),Y?(y1,y2,...,yn) 为两个n 长的二元码字，则码字X和Y之间的汉明距离定义为：

D(X,Y)??xk?yk。

i?1n该式的含义是：两个码字之间的汉明距离就是它们在相同位上不同 码符号的数目的和（解释?：模二和运算）。

第四种方法：通过让任意两个码字之间的距离都比较大来实现检错与纠错。 该方法在译码时采用的方法是这样的：

设发送的信息集合为：{xi|1?i?n}，若在接收端接收到的信息为：yj.

则在译码时必须求出yj与集合{xi|1?i?n}中每一个元素之间 的距离D(xi,yj)，如果发现：

D(xi0,yj)?D(xi,yj)(1?xi0?n,1?xi?n,i?i0)，则会把yj翻译为xi0。

该方法基于如下两个假设： （1）：在发送端，每个码字的概率是一样的。

（2）信道是对称的，即符号0与1在传送的过程中间出现 错误的概率都是一样的。

也就是说，如果这两个假设是成立的，则该译码规则是最佳的，但在一般情形， 该译码规则不是最佳的。

该方法的效果见书上题目6.8:

设码字为：x1,...,xn.设发送的信息为：xi(1?i?n)，而接收端接收到的信息为：yj.则由于：D( xi,yj)?Dmin/2,故有：D( xk,yj)?D( xi,xk)?D( xi,yj)?Dmin?Dmin/2?Dmin/2(k?i).从而有：D( xi,yj)?D( xk,yj)(k?i).于是我们得到该二元信道能纠正小于Dmin/2个错误的所有组合．

如果仅仅考虑该译码方法能发现多少错误，则有如下结果：

本文来源：https://www.bwwdw.com/article/07mh.html