信息科学第五章.ppt

第五章 有噪信道编码 第一节 错误概率与译码规则第二节 错误概率与编码方法第三节 有噪信道编码定理第四节 联合信源信道编码定理第六节 纠错编码的基本思想第七节 常用编码方法第五章 有噪信道编码 前一章已经从理论上讨论了，对于无噪无损信道只要 对信源进行适当的编码，总能以信道容量无差错的传递 信息但是一般信道总会存在噪声和干扰，那么在有噪 信道中进行无错传输可以达到的最大信息传输率是多少 呢？这就是本章所要讨论的问题本章的核心是香农第 二定理第一节 错误概率与译码规则为了减少错误，提高通信的可靠性，就必须分析错误 概率与哪些因素有关，有没有办法控制，能控制到什么程 度前边已经讨论过，错误概率与信道的统计特性有关， 但并不是唯一相关的因素，译码方法的选择也会影响错误 率第一节 错误概率与译码规则例：有一个BSC信道，如图所示 01011/31/32/32/3若收到“0”译作“0”，收到“1”译作“1”，则平均错误概率为：反之，若收到“0”译作“1”，收到“1”译作“0”，则平均错误 概率为1/3，可见错误概率与译码准则有关第一节 错误概率与译码规则我们来定义译码准则：输入符号集输出符号集译码规则例：第一节 错误概率与译码规则译码规则的选择应该有一个依据，一个自然的依据就 是使平均错误概率最小有了译码规则以后，收到 的情况下，译码的条件正 确概率为：可以设计译码准则：A：和B：第一节 错误概率与译码规则而错误译码的概率为收到 后，推测发出除了 之 外其它符号的概率： 可以得到平均错误译码概率为： 它表示经过译码后平均没收到一个符号所产生错误的 大小，也称平均错误概率。

第一节 错误概率与译码规则下面的问题就是如何选择 ，经过前边的讨论可以看 出，为使 最小，就应选择 为最大， 即选择译码函数 并使之满足条件： 也就是说，收到一个符号以后译成具有最大后验概率 的那个输入符号这种译码准则称为“最大后验概率准则” 或“最小错误概率准则”根据贝叶斯定律，上式也可以写成第一节 错误概率与译码规则即：当信源等概分布时，上式为：这称为最大似然译码准则，方法是收到一个 后， 在信道矩阵的第j列，选择最大的值所对应的输入符号作 为译码输出 可进一步写出平均错误概率：第一节 错误概率与译码规则也可写成：上式也可写成对行求和：如果先验概率相等，则：第一节 错误概率与译码规则例：根据最大似然准则可选择译码函数为B：第一节 错误概率与译码规则若采用前边讲到的译码函数A，则平均错误率为：若输入不等概分布，其概率分布为：第一节 错误概率与译码规则若采用最小错误概率译码准则，则联合矩阵为：所得译码函数为：C：平均错误率为：第二节 错误概率与编码方法一般信道传输时都会产生错误，而选择译码准则并不会 消除错误，那么如何减少错误概率呢？下边讨论通过编码 方法来降低错误概率。

01010.990.990.010.01例：对于如下二元对称信道第二节 错误概率与编码方法如何提高信道传输的正确率呢？可以尝试用下面的方法没有使用 的码字001010011100101110用作消息 的码字000111输出端接 收序列000001010011100101110111二元对称信道的 三次扩展信道第二节 错误概率与编码方法则：根据最大似然译码准则，可得译码函数为：F(000)=000 F(001)=000 F(010)=000 F(011)=111F(100)=000 F(101)=111 F(110)=111 F(111)=111此时，译码可以采用“择多译码”，即根据接收序列中0多 还是1多，0多就判作0，1多就判作1错误概率降低了两个 数量级，这种编码可以纠正码字中的一位码元出错若重 复多次可进一步降低错误率第二节 错误概率与编码方法但是又出现了一个新的问题，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也小如果在上例中，取M＝4，如：取000 011 101 110为 消息，其他的不用，则 则与M=8比较，错误率降低了，而信息率也降低了第二节 错误概率与编码方法还存在另外一个问题，M=4时，有70种选取方法，而 选取方法不同，错误率也不同我们比较下面两种选取方 法：第一种： 000 011 101 110第二种： 000 001 010 100可以计算得第一种方法的错误率为第二种方法的错误率为比较可知，第一种方法好，仔细观察发现，在第一种方 法中，如果000有一位出错，我们就可以判定出错了；而在 第二种方法中，如果000中任何一位出错，就变成了其他的 合法的码字，我们无法判断是否出错。

再仔细观察，发现第 二种方法中，码字之间太“象”了，或者说太“近”了第二节 错误概率与编码方法我们再讨论一个例子，取M＝4，n＝5，这4个码字按 如下规则选取：设输入序列为:满足方程：若译码采取最大似然准则：第二节 错误概率与编码方法此码能纠正所有码字中一位码元错误，也能纠正其中两个 两位码元的错误第二节 错误概率与编码方法我们引进这样一个概念：汉明距离在二元码中： 如：则在某一码书中，任意两个码字的汉明距离的最小值称为 该码C的最小距离我们来讨论前边的5种码的距离：第二节 错误概率与编码方法码A码B码C码D码字000 111000 011 101 110000 001 010 100000 001 010 011 100 101 100 111消息数M2448最小距离 dmin3211信息传输 率 R1/32/32/31错误 概率第二节 错误概率与编码方法很明显， 越大， 越小，在M相同的情况下也是一样在二元对称信道的情况下，译码规则可以如下： 选择使之满足它称为最小距离译码准则，它等价与最大似然译码准则 ，也就是收到一个码字后，把它译成与它最近的输入码字 ，这样可以使平均错误率最小。

另外，我们应该选择这样的编码方法：应尽量设法使 选取的M个码字中任意两两不同码字的距离尽量大第三节 有噪信道编码定理（香农第二定理）1、有噪信道编码定理如一个离散无记忆信道，信道容量为C当信息传输 率R≤C时，只要码长足够长，总可以在输入符号集中 找到M 个码字组成的一组码 和相应的译码 准则，使信道输出端的平均错误译码概率达到任意小第三节 有噪信道编码定理（香农第二定理）2、有噪信道编码逆定理如一个离散无记忆信道，信道容量为C当信息传输 率R>C时，则无论码长n多长，总找不到一种编码 使信道输出端的平均错误译码概率达到任意小第三节 有噪信道编码定理这个定理是信道编码的理论依据，可以看出：信道容量 是一个明确的分界点，当取分界点以下的信息传输率时， 以指数趋进于0；当取分界点以下的信息传输率时， 以指 数趋进于1；因此在任何信道中，信道容量都是可达的、最 大的可靠信息传输率这个定理是一个存在定理，它没有给出一个具体可构造 的编码方法，在它的证明过程中，码书是随机的选取的，它 有助于指导各种通信系统的设计，有助于评价各种系统及编 码的效率。

第四节 联合信源信道编码定理从香农第一、第二定理可以看出，要做到有效和可靠的 传输信息，我们可以将通信系统设计成两部分的组合，即 信源编码和信道编码两部分，首先通过信源编码，用尽可 能少的信道符号来表达信源，尽可能减少编码后信源的数 据的剩余率，然后针对信道，对信源编码后的数据独立的 进行信道编码，适当增加一些剩余度，使能纠正和克服信 道中引起的错误和干扰我们可以证明，只要满足香农第一定理和第二定理， 用两步编码的方法传输信息和一步编码的方法传输信息其 效果是一样的。