信息论与编码无失真编码

《信息论与编码无失真编码》由会员分享，可在线阅读，更多相关《信息论与编码无失真编码（96页珍藏版）》请在金锄头文库上搜索。

1、1,第4章 离散无记忆信源无失真编码,2,第二章简单回顾 第二章讨论的是信源。重点是信源的统计特性和数学模型，以及各类信源（离散无记忆单符号信源、离散有记忆单符号信源、连续信源、离散信源序列）的信息测度-熵及其性质，给出了自信息量、互信息量、熵、冗余度等的概念、定义、性质以及它们之间的关系。,3,主要内容,4.1 信源编码概论 4.2 码的唯一可译性 4.3 定长编码定理和定长编码方法 4.4 变长编码定理 4.5 变长编码方法,4,通信的实质是信息的传输。而高速度、高质量地传送信息是信息传输的基本问题。将信源信息通过信道传送给信宿，怎样才能做到尽可能不失真而又快速呢？这就需要解决两个问题：

2、第一，在不失真或允许一定失真的条件下，如何用尽可能少的符号来传送信源信息； 第二，在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。为了解决这两个问题，就要引入信源编码和信道编码。,4.1 信源编码概论,5,一般来说，提高抗干扰能力（降低失真或错误概率）往往是以降低信息传输率为代价的；反之，要提高信息传输率常常又会使抗干扰能力减弱。二者是有矛盾的。然而在信息论的编码定理中，已从理论上证明，至少存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既可靠又有效地传输信息。这些结论对各种通信系统的设计和估价具有重大的理论指导意义。,信源编（译）码和信道编（译）码 信源发出

3、的消息序列通常不能直接送给信道传输，需要经过两次变换，分别称为信源编码和信道编码，然后送给信道传送，信道输出经过两次反变换，即信道译码和信源译码，就可送给信宿接受了。,信息传输系统编码和译码示意图,7,传输之前的两次变换：信源编码、信道编码。 传输之后的两次反变换：信道译码、信源译码。 变换与反变换是成对出现的。 采取适当信道编码和译码措施后，可使信道传送的差错率降到允许的范围之内，因此，图中虚框部分可近似地视为一个等效的无损确定信道，简称为无噪信道，这一点是我们讨论信源编码的前提。,1、基本概念,8,信源编码分类：无失真编码、有失真编码。 无失真编码：只对信源的冗余度进行压缩，不会改变信源的

4、熵，又称冗余度压缩编码，它能保证码元序列经译码后能无失真地恢复成信源符号序列。 有失真编码：又称熵压缩编码，将在第6章讨论。,无失真信源编码的作用：,（1）符号变换：使信源的输出符号与信道的输入符号相匹配；,（2）冗余度压缩：使编码之后的新信源概率分布均匀化，信息含量效率等于或接近于100%。,9,9,信源编码器,码表,信源,信道,信源编码: 将信源输出符号,经信源编码器后变换成另外的压缩符号,然后将压缩后信息经信道传送给信宿 信源符号之间存在分布不均匀和相关性,使得信源存在冗余度,信源编码的主要任务就是减少冗余,提高编码效率。 针对信源输出符号序列的统计特性,寻找一定的方法把信源输出符号序列

5、变换为最短的码字序列。,X,Y,10,下图是一个信源编码器.它的输入是信源符号集S=s1,s2,sq，同时存在另一符号集X=x1,x2, xr，一般来说，元素xj是适合信道传输的，称为码符号（或者码元, 码符）。编码器的功能就是将信源符号集中的符号si（或者长为N的信源符号序列）变换成由xj (j=1,2,r)组成的长度为li 的一一对应的序列。 从理论上讲，编码实现的是序列到序列的映射。在具体实现时，要考虑到时延的限制和计算复杂性的限制。为此，编码实现时通常将信源输出序列分组后按一定的映射顺序依次逐步完成。根据不同的分组方式及其随后的映射关系，可以构成不同结构的码，如分组码，树码。,图 无失

6、真信源编码器,11,11,ASCII码是人们最为熟悉一种信源编码结 果，它是由两位16进制数00FF构成的码字集合，与一些控制字符（回车，换行等）、可打印字符（09，AZ，az，+， ，*，/ 等）以及图形符号一一对应。通常称这些字符、图符为ASCII字符。,ASCII（America Standard Code II）码,12,图 ASCII码编码器的模型,字符集合：ASCII字符 代码集合：16进制数 信道基本符号集合：ASCII码 编码器：产生它们之间相互关系的装置,13,中文电报的基本编码方法是将每一个汉字或字符用4位十进制数来表示，每一个十进制数再用5位二进制数来表示。 例如，“信息

7、论”三个字的电码分别是(0207)，(1873)，(6158)。以“信”为例，首先将它编成4位十进制的码0207，再将它们变换成20位二进制的码:01101 11001 01101 11100，由此可见，其编码过程为 汉字 电码 二进制码字组,中文电报的编码方法,14,从汉字的电报码可以看出如下问题： （1）若每个汉字都用4位十进制数来表示，则汉字电报电码最多只能有1万个（00009999）， 将汉字字符分为常用和非常用两大类，将常用汉字字符直接用4位十进制数表示； 对非常用汉字字符则根据汉字的结构，用多个常用汉字字符的组合来表示，这就是“电码作字办法”。 就汉字总体而言，中文电报是非等长编码

8、，而其中的常用字是等长编码。,15,（2）1个常用汉字用20位的二进制数来表示，但20位的二进制数可表示的汉字字符数为220= 1 048 576个，因此尽管汉字到电码再到二进制码的变换是一一对应的，但反过来就不是一一对应了。 这样做是不是浪费了很多二进制码？这种编码是不是最好？能不能找一个判定编码优劣的判据？ 电报编码具体的变换关系为 001101，101011，211001，310110，411010，500111，610101，711100，801110，910011。 这种编码只能检测错误但不能纠正错误，称为检错码。,16,输出的码符号序列称为码字，长度li 称为码字长度或简称码长。可

9、见，编码就是从信源符号组到码符号组的一种映射。若要实现无失真编码，则这种映射必须是一一对应的，并且是可逆的。,信源编码器示意图 信源符号集合； 码元组成的集合； 信道能够传送的符号，称为码元； 信源编码，一一对应映射 ， 把信源 输出的符号 变换成的码元序列，称为码字； 所有码字组成的集合，称为码或码字集。 所含码元的个数，称为该码字的码长，单位“码元/符号”或“r 进 制单位/符号”。,18,2、编码器模型,码长li ：码字wi 所含码元的个数。单位：码元/符号，r进制单位/符号。 定长码(FLC，Fixed Length code) ：码中所有码字均有相同的码长l ；否则称为变长码(VLC

10、，Variable Length code)。 平均码长：,码W 码字集W,码字wi,码元集 X,码元xi,信源编码f ：一一对应的变换。,码元/符号,定长码：,码元/符号,平均码长是衡量码的性能的重要参数，“平均码长小”说明平均一个码元所携带的信息量大，信息的冗余就小。,19,例：编码,设DMS的概率空间为,对其单个符号进行二进制编码。,码元/符号,码元/符号,编码策略：经常出现（概率大）的符号采用较短的码字，不经常出现（概率小）的符号采用较长的码字 。,编码策略：采用等长的码字 。,3、编码器的输出 信源编码器输出可视为一个新信源，该信源若以码字集作为符号集，则为信源W ，若以码元集当作符

11、号集，则为信源X ，如图所示。 将信源编码器的输出视为新信源W 或X 无失真编码信源符号 与码字 是一一对应的，故 ， 所以编码前后的熵保持不变： bit /码字或bit /符号 即无失真信源编码是保熵的。,21,3、编码器的输出,f 是一一对应的映射,bit/码字或bit/符号,编码后的信息率R ：平均一个码元携带的信息量。,bit/码元,平均码长越小，每个码元携带的信息量就越多，传输一个码元就传输了较多的信息。,22,4、编码效率,为了衡量编码效果，定义编码效率：编码后的实际信息率与编码后的最大信息率之比。,注 ：编码效率实际上也是新信源X的信息含量效率或熵的相对率。,新信源的冗余度也是码

12、的冗余度：,23,例 已知信源空间为 X: x1 x2 P(X): 0.2 0.8 信道基本符号为0,1。若编码规则为：x1s1=0，x2s2=1，求平均长度和编码效率；,解 先求信源熵，再求平均长度和编码效率，结果如下：,24,4.2 码的唯一可译性,f为一一对应的变换只是无失真编码的必要条件，并不充分; 要保证将码元序列无失真地恢复成信源符号序列，还要求编出的码自身具有独特的结构。 有实用价值的码应该具有唯一可译性，即能从码字序列（也是码元序列）唯一地恢复成信源符号序列。,25,唯一可译码（UDC，Uniquely Decodable Code）,唯一可译码（UDC）：该码的码字组成的任意

13、有限长码字序列都能恢复成唯一的信源序列。否则称为非唯一可译码。 码是唯一可译码的充分必要条件是：由码中的码字组成的任意有限长的码字序列（也是码元序列），都能唯一划分成一个个的码字，且任一码字只与唯一一个信源符号对应。 奇异码：含相同码字的码。否则称为非奇异码。,26,我们给出常见码的定义。 1. 二元码 若码符号集为X=0,1，所有码字都是一些二元序列，则称为二元码。二元码是数字通信和计算机系统中最常用的一种码。 2. 等长码 若一码中所有码字的码长都相同，即li=l (i=1,2,q)，则称为等长码。 3. 变长码 若一码中所有码字的码长各不相同，则称为变长码。,27,4. 非奇异码 若一码

14、中所有码字都不相同，则称为非奇异码。 5. 奇异码 若一码中有相同的码字，则称为奇异码。 6. 唯一可译码 若由码的码字组成的任意一串有限长的码符号序列只能唯一地被译成所对应的信源符号序列，则此码称为唯一可译码，否则就称为非唯一可译码。,28,7. 非即时码和即时码 如果接收端收到一个完整的码字后，不能立即译码，还要等下一个码字开始接收后才能判断是否可以译码，这样的码叫做非即时码，也叫延时码。 如果收到一个完整的码字以后，就可以立即译码，则叫做即时码，也叫非延时码。即时码要求任何一个码字都不是其他码字的前缀部分，也叫做异前缀码。,29,W1、W2：定长码。,W3、W4、 W5：变长码。,W2：

15、奇异码。奇异码肯定不是UDC。,W1：定长非奇异码。是UDC。,非续长码：码中任一码字都不是另一码字的续长（加长）。否则为续长码。,W3：变长码、非奇异码、续长码。,W3：不是UDC。,W5：变长码、非奇异码、续长码。是UDC。,W4：变长码、非奇异码、非续长码。是UDC。,非续长码肯定是UDC，并且是及时可译的，又称及时码或立即码。,30,码,非分组码 分组码,奇异码 非奇异码,非唯一可译码 唯一可译码,非即时码 即时码 (非延长码),31,表,奇异码,奇异码,非即时码,即时码,32,33,2、非续长码的编码-码树,码树从树根开始向上长出树枝，树枝代表码元，树枝与树枝的交点叫做节点 。 r进

16、制码树：码元个数为r，各节点（含树根）向上长出的树枝数不大于r。 l阶节点：经过l 根树枝才能到达的节点。 终端节点或端点：向上不长出树枝的节点。 码字：与码树上的节点对应，组成该码字的码元就是从树根开始到该节点所经过的树枝（或码元）。 非续长码：所有码字均处于终端节点，即端点上。 整树：r进制码树各节点（包括树根）向上长出的树枝数均等于r。,W1=00，01，10，11,W4=0，10，110，111,W5=0，01，011，111,(a)和(b)是整树，(c)为非整树,34,即时码的树图构造法,1、码树的构造过程 （1）根：从根出发伸出树枝，树枝的数目等于码符号的总数r 例如: r =2，伸出两条树枝。,（2）节点：树枝的尽头为节点。从节点出发再伸出树枝，每次每个节点伸出