3无失真信源编码

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

1、第三章 无失真信源编码3.1 编码的相关概念 3.2 定长编码定理 3.3 变长编码定理 3.4 最佳编码无失真信源编码为什么要对进行编码？ 1.信源发出的消息符号可能不适合信道的传输，将 信源发出的消息符号转换为适合信道传输的符号 。 2.信源消息确定后，提高通信的有效性-信源编码 。 3.提高通信的可靠性 , 编码具有发现错误或纠正错 误的抗干扰能力-信道编码 。 4.提高通信的安全性-加密编码。3.1 编码的相关概念3.1.1 信源编码的定义 3.1.2 信源编码的研究方法 3.1.3 编码相关概念 3.1.4 唯一可译码的存在条 件编码的相关概念信源编码的定义 信源编码定义：指定能够满

2、足信道特性/适合于信 道传输的符号序列/码序列，来代表信源输出的消 息。 完成编码功能的器件称为编码器。 离散信源输出的码序列 离散信源输出的消息是由一个个离散符号组成 的随机序列信源符号序列； X=(X1X2XlXL) Xlx1,x2,xi,xn信源编码就是把信源输出的随机符号序列变成 码序列。 Y=(Y1Y2YkYK) Yky1,y2,yj,ym信源编码的研究方法研究方法 研究信源编码时，将信道编码和译码看成是信道 的一部分，而突出信源编码；信道信源编码的研究方法研究信道编码时，将信源编码和译码看成是信源和信 宿的一部分，而突出信道编码。信源信宿信源编码的研究方法讨论无失真信源编码可以先不

3、考虑抗干扰问题，所以 它的数学模型比较简单，如图所示。P(yj /xi)无失真信源编码器XX1,X2,XLYY1,Y2,Ykiy1,y2,ym(Yk是由ki个yj组成的序列)编码相关概念码元和码字 码元(符)集：信道可传输的基本符号的集合, 记为 Y; 设 Y 有m个符号：Y=y1,y2,ym，其中yi称为 码元或码符。 m 元信道: 可传输m个基本符号的信道； 二元信道: 可传输 2个基本符号的信道。这是 一种最常用的信道, 基本符号常用 0 , 1 表示。 码字: 由码元组成的序列称为码字，记为Yi 。 码字Yi的码元个数 Ki 称为Yi的码长。 所有码字Yi的码长 Ki 均相等称为定长码

4、。 码字Yi的码长 Ki不全相等称为变长码。编码相关概念编码与译码 信源编码：将信源符号xi或符号序列X按一种规则 映射成码字Yj的过程。无失真编码：信源符号到码字的映射必须一一对 应。 译码：从码符号到信源符号的映射。 码表：所有映射规则的集合。编码相关概念许用码和禁用码 许用码字：信源的符号xi或符号序列X与码字Yj定 义了对应关系的码字。 禁用码字：信源的符号xi或符号序列X与码字Yj未 定义对应关系的码字。 许用码字的全体称为码集。编码相关概念分组码（块码）分类 按码字的码长分类 定长码：码集中所有码字的码长相等。 变长码：码集中所有码字的码长不全相等。 按信源符号与码字对应关系分类

5、非奇异码：信源符号与码字是一一对应的。 奇异码：信源符号与码字不是一一对应的。编码相关概念/分类按译码唯一性分类 唯一可译码：对于多个码字组成的有限长码流， 只能唯一地分割一个个的码字。唯一可译码又称 为单义码。 唯一可译码在传输过程中不需要同步码。 非唯一可译码：对有限长码流，不能唯一地分割 一个个的码字。 例：码流 100111000 码1：x10 x210 x311 可分割10, 0, 11, 10, 0, 0 码2：x11 x210 x311 则无法唯一分割编码相关概念/分类按译码的即时性分类 非即时码：接收端收到一个完整的码字后，不能 立即译码；还需要等到下一个码字开始接收后才 能判

6、断是否可以译码。 即时码：接收端收到一个完整的码字后，就能立 即译码；即时码又称为非延长码或异前缀码。 例：非即时码 ，码流 01001100 x10 x201 x311 译码为 x2, x1, x1, x3, x1, ? 即时码，码流 01001100 x10 x210 x311 译码为 x1, x2, x1, x3, x1, x1结论：即时码指的是码集任何一个码不能是其他码 的前缀，即时码必定是唯一可译码, 唯一可译码不 一定是即时码。编码相关概念/分类/举例例：码1：显然不是惟一可译码。x2和x4对应于同一码字“11”，码 1本身是一个奇异码。码2：是非奇异码，不是惟一可译码。当收到一串

7、码符号 “01000”时，可将它译成“x4 x3 x1”，也可译为“x4x1x3”， “x1x2x3”或“x1x2x1x1”等，这种码从单个码字来看虽然不是 奇异的，单从有限长的码序列来看，它仍然是一个奇异码。 码3：虽然是惟一可译码，但它要等到下一个“1”收到后才能 确定码字的结束，译码有延时。 码4：既是惟一可译码，又没有译码延时。码字中的符号“1” 起了逗点的作用，故称为逗点码。xip(xi)码1码2码3码4 x11/20011 x21/411101001 x31/80000100001 x41/8110110000001前缀条件码/异前置码/异字头码/逗点码/即时码/ 非延长码：如果一

8、个码的任何一个码字都不是其 它码字的前缀。唯一可译码的存在条件码树图 码树图: 用码树来描述给定码集各码字的方法。码树图有树根、树枝、节点：一般中间节点（一 级节点、二级节点 ）用表示, 终端节点用表 示。 传输m个基本符号信道的码可用。例：二元（进制）码树x1x2x301011x11 x201 x3001唯一可译码的存在条件/码树图如果节点过多，也可以用如下方法表示码树图。唯一可译码的存在条件/码树图用码树图构造码的方法 在树的生长过程中，中间节点生出树枝，各树枝 标出相应的码元； 为了清晰起见相同码元的树枝方向相同，终端节 点表示信源符号； 从树根到终端节点所经过的树枝旁的码元按经过 的顺

9、序组成的序列构成码字。 用码树图构造即时码的条件 如果表示信源符号的终端节点不再延伸，即信源 符号都在终端节点上，这样构造的码满足即时码 条件。唯一可译码的存在条件前提条件：非奇异码 唯一可译码存在定理：设n为信源符号或信源符号序 列个数，m 为码元个数或进制数，Ki 为信源各符号 或信源符号序列对应的码长; 则唯一可译码存在的充 分和必要条件是满足Kraft不等式：注意： Kraft不等式是一个存在定理，不是唯一可译码的 判定定理。 如果n 、m、Ki 满足该不等式, 则存在唯一可译码 如果是唯一可译码, 则n 、m、Ki 必定满足该不等 式。唯一可译码的存在条件例：设二进制码树中Xx1,x

10、2,x3,x4，K1=1，K2=2 ，K3=2，K4=3，应用上述判断定理，可得因此，不存在满足这种Ki 的唯一可译码,用树码进 行检查如图所示。唯一可译码的存在条件信息率 若信源输出符号序列长度L1变换成由KL个符号组成的码序列/码字变换要求：能够无失真或无差错地从Y恢复X， 同时传送Y时所需要的信息率最小。唯一可译码的存在条件/信息率Yk有m种可能值，能编成的码字个数 所以平均每个符号输出的最大信息量为logm，KL长 码字最大信息量为KLlogm。 用该码字表示长度为L的信源序列，则送出一个信 源符号所需要的信息率平均为所谓信息率最小，就是找到一种编码方式使 KLlogm/L最小。几个问

11、题：信息率最小为多少时，才能无失真译码？若小于这个信息率是否还能无失真译码？3.2 定长编码定理3.2.1 平均码长和编码有效性 3.2.2 定长编码定理平均码长和编码有效性平均码长 单符号信源空间，其中信源符号 xi 对应的码字为Yi （i = 1, 2, , n）,码 字Yi 对应的码长为 Ki（i = 1, 2, , n ） 。 所有的Ki相等为定长码，记为K, 不相等时为变长 码。 单符号对应变长码的平均码长码符/信源符号平均码长和编码有效性/平均码长符号序列信源空间XL其中XL是X的L次扩展。 信源符号序列 对应的码字为Yi （i = 1, 2, , nL ）, 码字Yi 对应的码长

12、为 Ki（i = 1, 2, , nL） 。符号序列对应变长码的平均码长码符/信源符号序列码符/信源符号平均码长和编码有效性/编码效率编码效率（码率） 定义：平均一个码符所携带的平均信息量称为编 码效率，记作；平均码长和编码有效性例：信源空间 H(X) = - ( 1/2 log1/2+1/4 log1/4+1/8 log1/8+1/8 log1/8 ) =1.75 bit/消息 信源符号个数为n=4，二元码符0 , 1, 码符个数为 m=2，Ki为信源各符号对应的码字长, 且满足Kraft 不等式。 定长码: K1= K2= K3= K4=2 2-2+2-2+2-2+2-2=1 码字: Y1

13、=00 , Y2=01 , Y3=10 , Y4=11 编码效率= H(X)/K=1.75 2 = 0.825平均码长和编码有效性/举例变长码: K1=1, K2=2, K3=3, K4=3 满足不等式：2-1+2-2+2-3+2-3=1 码字: Y1=0 , Y2=10 , Y3=110 , Y4=111 方案1 : x10，x210，x3110，x4111=11/2+21/4+31/8+31/8 =1.75 码符/信源符号 = 1.75 1.75 = 1 方案2 : x1111，x2110，x310，x40= 31/2+31/4+21/8+11/8 =2.625 码符/信源符号 = 1.7

14、5 2.625 = 0.667平均码长和编码有效性讨论1：为什么定长码的编码效率小于1，而变长码的 编码效率能达到1？ 原因： 因为H(X)=1.75，是个小数，而定长码的码长不可 能为小数，所以编码效率小于1。除非H(X)为整数 。 但变长码的平均码长可以为小数，可能等于H(X) 。平均码长和编码有效性讨论2：编码后码字集合确定，符号对应的码字长度 不同，为什么编码效率不同？ 原因： 不同符号的先验概率不同，对应的码字长度不同 ，计算出的平均码长也不同，编码效率也就不同 。 总结： 一般情况下，变长编码的编码效率可能达到1； 对于变长编码，若概率大的符号对应短码,概率小 的符号对应长码，编码

15、效率越高；反之越低。这 也是后面最佳编码的思路。定长编码定理定理：由L个符号组成的、每个符号的熵为HL(X)的 无记忆平稳信源符号序列X1X2XlXL，可用KL个 符号（每个符号有m种可能值）进行定长编码。对任 意0，0，只要则当L足够大时，必可使译码差错小于；反之，当时，译码差错一定是有限值，而当L足够大时，译码 几乎必定出错。定长编码定理定理中的公式改写成表明：不等式左边表示长为KL的码字能载荷的最大 信息量，右边代表长为L的信源序列平均携带的信息 量。 所以定长编码定理告诉我们：只要码字传输的信息 量大于信源携带的信息量，总可实现几乎无失真编 码。定长编码定理信源熵HL(X)就是一个界限/临界值。当编码器输出 的信息率超过这个临界值时，就能无失真译码，否 则就不行。 信源编码定理从理论上说明了编码效率接近于1， 即 的理想编码器的存在性，代价是在实际 编码时取无限长的信源符号(L)进行统一编码。 只要足够小，就可实现几乎无失真译码；若足够 小，编码效率就接近于1。说明：定长编码定理是在平稳无记忆离散信源的条