信息论与编码(傅祖云 讲义)第五章

1、第五章 有噪信道编码 第一节 错误概率与译码规则第二节 错误概率与编码方法第三节 有噪信道编码定理第四节 联合信源信道编码定理第六节 纠错编码的基本思想第七节 常用编码方法第五章 有噪信道编码 前一章已经从理论上讨论了，对于无噪无损信道只要对信源进行适当的编码，总能以信道容量无差错的传递信息。但是一般信道总会存在噪声和干扰，那么在有噪信道中进行无错传输可以达到的最大信息传输率是多少呢？这就是本章所要讨论的问题。本章的核心是香农第二定理。第一节 错误概率与译码规则 为了减少错误，提高通信的可靠性，就必须分析错误概率与哪些因素有关，有没有办法控制，能控制到什么程度。 前边已经讨论过，错误概率与信道

2、的统计特性有关，但并不是唯一相关的因素，译码方法的选择也会影响错误率。第一节 错误概率与译码规则例：有一个BSC信道，如图所示 01011/31/32/32/3若收到“0”译作“0”，收到“1”译作“1”，则平均错误概率为：(0)(1)2(0)(1)3EeePPPPP反之，若收到“0”译作“1”，收到“1”译作“0”，则平均错误概率为1/3，可见错误概率与译码准则有关。第一节 错误概率与译码规则我们来定义译码准则： 输入符号集 输出符号集 译码规则 iAa iBb()jiF ba例：0.50.30.20.20.30.50.30.30.4P第一节 错误概率与译码规则 译码规则的选择应该有一个依据

3、，一个自然的依据就是使平均错误概率最小 有了译码规则以后，收到 的情况下，译码的条件正确概率为：( ()/)(/)jjijP F bbP abjb可以设计译码准则：A：11( )F ba22()F ba33( )F ba和B：11( )F ba23()F ba32( )F ba第一节 错误概率与译码规则 而错误译码的概率为收到 后，推测发出除了 之外其它符号的概率： jbia( /)1(/)jijP e bP ab 可以得到平均错误译码概率为： 11()( /)()(1(/)msejjjijjjPp bP e bp bP ab 它表示经过译码后平均没收到一个符号所产生错误的大小，也称平均错误概

4、率。第一节 错误概率与译码规则下面的问题就是如何选择 ，经过前边的讨论可以看出，为使 最小，就应选择 为最大，即选择译码函数 并使之满足条件： (/)ijP ab( ()/)jjP F bb( /)jP e b*()jF ba*(/)(/)jijiP abP abaa 也就是说，收到一个符号以后译成具有最大后验概率的那个输入符号。这种译码准则称为“最大后验概率准则”或“最小错误概率准则”。 根据贝叶斯定律，上式也可以写成*(/) ()(/) ( )()()jjiijjP ba P aP ba P aP bP b第一节 错误概率与译码规则即：*(/) ()(/) ( )jjiiP ba P aP

5、 ba P a当信源等概分布时，上式为：*(/)(/)jjiP baP ba 这称为最大似然译码准则，方法是收到一个 后，在信道矩阵的第j列，选择最大的值所对应的输入符号作为译码输出。jb可进一步写出平均错误概率：() ( /)1 ()/ ()EjjjjjYYPP b P e bP F bbP b,() ()ijjjX YYp abP F b b1 ()jjYP F b b *,()ijjX YYp abP a b*,()ijX Y aP ab第一节 错误概率与译码规则也可写成：*,(/) ( )EjiiX Y aPP ba P a上式也可写成对行求和：( )(/)()EijijXYPP aP

6、 baF ba( )( )iieXP a P如果先验概率相等，则：( )1iEeXPPr第一节 错误概率与译码规则例：0.50.30.20.20.30.50.30.30.4P根据最大似然准则可选择译码函数为B：112332( )()()F baF baF ba*,11( / )(0.20.3)(0.30.3)(0.20.4)0.56733EY XaPP b a第一节 错误概率与译码规则若采用前边讲到的译码函数A，则平均错误率为：*,11( / )(0.30.2)(0.30.3)(0.20.5)0.633EY XaPP b a若输入不等概分布，其概率分布为：123111(), (), ()442

7、P aP aP a*,1111( / )(0.30.2)(0.30.3)(0.20.5)0.63442EY XaPP b a第一节 错误概率与译码规则若采用最小错误概率译码准则，则联合矩阵为：0.1250.0750.05()0.050.0750.1250.150.150.2ijP ab 所得译码函数为：C：132333( )()()F baF baF ba平均错误率为：*,1( / )(0.1250.05)(0.0750.075)(0.050.125)0.53EY XaPP b a第二节 错误概率与编码方法 一般信道传输时都会产生错误，而选择译码准则并不会消除错误，那么如何减少错误概率呢？下边

8、讨论通过编码方法来降低错误概率。01010.990.990.010.01例：对于如下二元对称信道20.0110EP第二节 错误概率与编码方法 如何提高信道传输的正确率呢？可以尝试用下面的方法没有使用的码字001010011100101110用作消息的码字000111输出端接收序列000001010011100101110111二元对称信道的三次扩展信道第二节 错误概率与编码方法则：3222222332222223pp pp pppp ppppppPpppppp pppp pp pp根据最大似然译码准则，可得译码函数为：F(000)=000 F(001)=000 F(010)=000 F(011

9、)=111F(100)=000 F(101)=111 F(110)=111 F(111)=1113*4() (/)3*10EijiY C aPPP 此时，译码可以采用“择多译码”，即根据接收序列中0多还是1多，0多就判作0，1多就判作1。错误概率降低了两个数量级，这种编码可以纠正码字中的一位码元出错。若重复多次可进一步降低错误率第二节 错误概率与编码方法 但是又出现了一个新的问题，n很大时，信息传输率会降低很多，logMRn 在上例中：M=2当n=1时 R=1当n=3时 R=1/3当n=5时 R=1/5.第二节 错误概率与编码方法 这显然是一个矛盾，有没有解决的办法呢？香农第二定理可以解决这一

10、问题。 我们分析前边的例子，我们只用了扩展信源的两个字符，因此信息率降低了，如果我们把8个字符全用上，信息传输率就会回到1，但是此时错误率为 比单符号时还大三倍。我们可以总结如下：在二元信道的n次扩展信道中，选取其中的M个作为消息，则M大一些， 跟着大，R也大，M小一些， 跟着小，R也小。EPEP 如果在上例中，取M4，如：取000 011 101 110为消息，其他的不用，则 则与M=8比较，错误率降低了，而信息率也降低了。222*103EPR23*10第二节 错误概率与编码方法 还存在另外一个问题，M=4时，有70种选取方法，而选取方法不同，错误率也不同。我们比较下面两种选取方法：第一种：

11、 000 011 101 110 第二种： 000 001 010 100 可以计算得第一种方法的错误率为 第二种方法的错误率为22*1022.28*10 比较可知，第一种方法好，仔细观察发现，在第一种方法中，如果000有一位出错，我们就可以判定出错了；而在第二种方法中，如果000中任何一位出错，就变成了其他的合法的码字，我们无法判断是否出错。再仔细观察，发现第二种方法中，码字之间太“象”了，或者说太“近”了。第二节 错误概率与编码方法 我们再讨论一个例子，取M4，n5，这4个码字按如下规则选取： 设输入序列为:12345()iiiiiiaaaaaa满足方程：31241512iiiiiiiia

12、aaaaaaa若译码采取最大似然准则：25R 第二节 错误概率与编码方法000000000100010001000000001000100001000100011011010110001111010010110100101111011110001110101111011010101100111011111111001110011010100110101101111000111101101010010010100101111001 此码能纠正所有码字中一位码元错误，也能纠正其中两个两位码元的错误。543252EPpp pp p5432411 (52)7.8 10EEPPpp pp p 第二节 错

13、误概率与编码方法 我们引进这样一个概念：汉明距离。在二元码中：1(,)nijikjkkD 如：101111i111100j则(,)3ijD 在某一码书中，任意两个码字的汉明距离的最小值称为该码C的最小距离。minmin (,)ijijdD C CCC我们来讨论前边的5种码的距离：第二节 错误概率与编码方法 码A码B码C码D码字000111000011101110000001010100000 001010 011100 101100 111消息数M2448最小距离dmin3211信息传输率R 1/32/32/31错误概率43*1022*1022.28*1023*10第二节 错误概率与编码方法

14、很明显， 越大， 越小，在M相同的情况下也是一样mindEP 在二元对称信道的情况下，译码规则可以如下：*()jF ba选择 使之满足*(,)(,)jijiDD 它称为最小距离译码准则，它等价与最大似然译码准则，也就是收到一个码字后，把它译成与它最近的输入码字，这样可以使平均错误率最小。 另外，我们应该选择这样的编码方法：应尽量设法使选取的M个码字中任意两两不同码字的距离尽量大。第三节 有噪信道编码定理（香农第二定理）1、有噪信道编码定理有噪信道编码定理 如一个离散无记忆信道，信道容量为C。当信息传输率RC时，只要码长足够长，总可以在输入符号集中 找到M 个码字组成的一组码 和相应的译码准则，

15、使信道输出端的平均错误译码概率达到任意小。nX(2 )nR(2 , )nRn第三节 有噪信道编码定理（香农第二定理）2、有噪信道编码逆定理有噪信道编码逆定理 如一个离散无记忆信道，信道容量为C。当信息传输率RC时，则无论码长n多长，总找不到一种编码 使信道输出端的平均错误译码概率达到任意小。(2 , )nRn第三节 有噪信道编码定理 这个定理是信道编码的理论依据，可以看出：信道容量是一个明确的分界点，当取分界点以下的信息传输率时， 以指数趋进于0；当取分界点以下的信息传输率时， 以指数趋进于1；因此在任何信道中，信道容量都是可达的、最大的可靠信息传输率。 这个定理是一个存在定理，它没有给出一个具体可构造的编码方法，在它的证明过程中，码书是随机的选取的，它有助于指导各种通信系统的设计，有助于评价各种系统及编码