信息论与编码纠错第3章

《信息论与编码纠错第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章离散信源无失真编码内容提要用尽可能少的符号来传输信源消息，目的是提高传输效率，这是信源编码应考虑的问题，这章讨论在不允许失真情况下的信源编码。等长编码定理给出了等长编码条件下，其码长的下限值，变长编码定理（香农第一定理）给出了信源无失真变长编码时其码长的上、下限值。本章还介绍了三种通用信源编码方法：香农编码法、费诺编码法和霍夫曼编码法。§3.1概述一．信源编码的模型为了实现高质量、高效率的通信，引入了信源编码和信道编码。信源编码和信道编码主要需要解决以下两个问题。（1）提高传输效率：用尽可能少的信道传输符号来传递信源消息，目的是提高传输效率，

2、这是信源编码主要应考虑的问题。这里又分两种情况讨论，即允许接收信号有一定的失真或不允许失真。（2）增强通信的可靠性：如何增加信号的抗干扰能力，提高传输的可靠性，这是信道编码主要考虑的问题。解决这一问题，一般是采用冗余编码法，赋予信码自身一定的纠错和检错能力，只要采取适当的信道编码和译码措施，就可使信道传输的差错概率降到允许的范围之内。综上所述，提高抗干扰能力往往是以降低信息传输效率为代价的，而为了提高传输效率又往往削弱了其抗干扰能力。这样，设计者在取舍之间就要作均衡考虑。信源编码的概念：对信源的原始符号按一定的数学规则进行变换的一种代码。信源编码包

3、括两个功能：（1）将信源符号变换成适合信道传输的符号；（2）压缩信源冗余度，提高传输效率。信源编码模型：{a1,a2,…,ak}为信源符号集，序列中每一个符号uml都取自信源符号集。{b1,b2,…,bD}是适合信道传输的D个符号，用作信源编码器的编码符号。编码输出码字cm=cm1cm2…cmn，cmk∈{b1,b2,…,bD}，k=1,2,…,n，n表示码字长度，简称码长。【例】中文电报编码：信源编码器I：1－10000个汉字分别对应0000－9999信源编码器II：每位数字对应五位二进制等重码。对应关系如下：（1→01011，2→11001，.

4、..，9→10011，0→01101）如：二．码的分类信源编码可看成是从信源符号集到码符号集的一种映射，即将信源符号集中的每个元素（可以是单符号，也可以是符号序列）映射成一个长度为n的码字。对于同一个信源，编码方法是多种的。【例】用{u1，u2，u3，u4}表示信源的四个消息，码符号集为{0,1}，下表列出了该信源的几种不同编码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)1111111000一般，可以将码简单的分成如下几类:1．二元码若码符号集为{0，1}，

5、则码字就是二元序列，称为二元码，二元码通过二进制信道传输，这是数字通信和计算机通信中最常见的一种码，例子列出的4种码都是二元码。2．等长码在一组码字集合C中的所有码字cm(m=1,2,…,M)，其码长都相同，则称这组码C为等长码，例中的码1、码2就码长n=2等长码。3．变长码若码字集合C中的所有码字cm(m=1,2,…,M)，其码长不都相同，称码C为变长码，例中列出的码3、码4就是变长码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110004．奇异

6、码对奇异码来说，从信源消息到码字的映射不是一一对应的。例中的码1，信源消息u2和u4都用码字11对其编码，因此这种码就是奇异码，奇异码不具备惟一可译性。5．非奇异码从信源消息到码字的映射是一一对应的，每一个不同的信源消息都用不同的码字对其编码，例中的码2、码3和码4都是非奇异码。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110u3p(u3)101000100u4p(u4)11111110006．原码C的N次扩展码原码C的N次扩展码中的每个元素是N次扩展信源中的序列所对应的N个码字组成的序列。原码的N次扩展码是

7、将信源作N次扩展得到的新信源符号序列u（N）=u1…uN=(u11u12…u1L)…(uN1uN2…uNL)，对应码符号序列c（N）=c1…cN=(c11c12…c1n)…(cN1cN2…cNn)，记集合C(N)={c1(N),c2(N),…}，C(N)即原码C的N次扩展码。7．唯一可译码定义：如果码的任意N次扩展码都是非奇异码，则称该码为惟一可译码。例中的码1不是唯一可译码。对于定长码，若原码是惟一可译码，则它的N次扩展码也是惟一可译的，而对于变长码则不尽然。信源消息各消息概率码1码2码3码4u1p(u1)000001u2p(u2)1101110

8、u3p(u3)101000100u4p(u4)1111111000信源消息各消息概率码1码2码3u1p(u1)011u2p