信息论与编码 第5章(1)教材.ppt
《信息论与编码 第5章(1)教材.ppt》由会员分享,可在线阅读,更多相关《信息论与编码 第5章(1)教材.ppt(55页珍藏版)》请在一课资料网上搜索。
1、2021/1/29,1,信源编码,第5章(第1讲,2021/1/29,2,数字通信系统的一般模型,2021/1/29,3,信息通过信道传输到信宿的过程即为通信。要做到既不失真又快速地通信,需要解决两个问题: 在不失真或允许一定失真条件下,如何提高信息传输速度-这是本章要讨论的信源编码问题. 在信道受到干扰的情况下,如何增加信号的抗干扰能力,同时又使得信息传输率最大-这是下章要讨论的信道编码问题,2021/1/29,4,2021/1/29,5,信源编码分为无失真和限失真。 无失真编码,又名冗余度压缩编码:仅对信源的冗余度进行压缩,不改变信源的熵;可逆编码的基础,只适用于离散信源,主要用于文字、数
2、据信源的压缩。 限失真编码,又名熵压缩编码:在失真受限的情况下进行限失真编码。只适用于连续信源,主要用于图像、语音信源的压缩。 信源编码的基础是信息论中的两个编码定理 无失真信源编码 第一极限定理 限失真信源编码 第三极限定理 信道编码定理(离散和连续信道) 第二极限定理,2021/1/29,6,信源编码的主要任务 减少冗余,提高编码效率。具体的说,就是针对信源输出符号序列的统计特性,寻找一定的把信源输出符号序列变换为最短码字序列的方法。 符号变换:使信源输出符号与信道的输入符号相匹配。 信源编码的基本途径有两个: 一是编码后使序列中的各个符号之间尽可能地互相独立,即解除相关性-方法包括预测编
3、码和变换编码. 二是使编码后各个符号出现的概率尽可能相等,即均匀化分布-方法主要是统计编码,2021/1/29,7,本章主要介绍信源编码的基本思路与主要方法,讨论离散信源编码,首先从无失真编码定理出发,重点讨论以香农码、费诺码和哈夫曼码为代表的最佳无失真码。然后介绍了限失真编码定理。最后简单介绍了一些其它常用的信源编码方法。期望通过本章学习能建立起信源压缩编码的基本概念,2021/1/29,8,5.1 编码的定义 5.2 无失真信源编码 5.3 限失真信源编码 5.4 常用信源编码方法简介,主 要 内 容,2021/1/29,9,5.1 编码的定义,2021/1/29,10,编码的定义,编码定
4、理证明: 必存在一种编码方法,使代码的平均长度可任意接近但不能低于符号熵; 达到这目标的途径就是使概率与码长匹配。 统计匹配编码: 根据信源的不同概率分布而选用与之匹配的编码,以达到在系统中传信速率最小,2021/1/29,11,编码器的作用: 将信源符号集X中的符号 变换成由码符号集y中的码元 组成的长度为KL的一一对应的码字 。 码字集合叫做代码组Y;码字 所含码元的个数称为该码字的码长,记为KL,编码的定义,2021/1/29,12,如果信源输出符号序列长度L1,信源符号集A(a1,a2,an),信源概率空间为,若将信源X通过二元信道传输,就必须把信源符号ai变换成由0,1符号组成的码符
5、号序列,这个过程就是信源编码,编码的定义,2021/1/29,13,若码集为0,1,所得码字为二元序列,称为二元码 例如,信源符号Xa1,a2,a3,a4,对应不同码字如表,编码的定义,2021/1/29,14,编码的定义,等长码:码中所有码字的长度都相同 可变长码:码中的码字长短不一,两种码:固定长度和可变长度的编码,2021/1/29,15,分组码的属性,1)奇异码和非奇异码,非奇异码:如果信源符号和码字是一一对应的,则称该码为非奇异码。如码0,2,3,4 奇异码:如果信源符号和码字不是一一对应的,则称该码为奇异码。如码1,分组码/块码:将信源符号集X中的每个符号 映射成一个固定的码字 。
6、这种码必须具有某些属性,才能保证在接收端能够迅速可靠地译码,编码的定义,2021/1/29,16,编码的定义,2)唯一可译码: 任意有限长的码元序列,只能被唯一地分割成一个个的码字。 例:0,10,11是一种唯一可译码。 任意一串有限长码序列,如100111000,只能被分割成10,0,11,10,0,0。任何其他分割法都会产生一些非定义的码字。 奇异码不是唯一可译码 非奇异码 唯一可译码 码3 100,1,1,1000 非唯一可译码 码2 10000100,2021/1/29,17,2)唯一可译码,例如,对于码元序列100111000110,分别用编码1, 编码3,编码4,试判断那种是唯一可
7、译码,2021/1/29,18,编码的定义,2)唯一可译码 非即时码: 如果接收端收到一个完整的码字后不能立即译码,还需等下一个码字开始接收后才能判断是否可以译码 即时码(非延长码,异前缀码): 在译码时无需参考后续的码符号就能立即作出判断,译成对应的信源符号。 任意一个码字都不是其它码字的前缀部分 在延长码中,有的码是唯一可译的,取决于码的总体结构,如码3, “1,10,100,1000,2021/1/29,19,例如,试判断编码4和编码5是否为即时码,2021/1/29,20,编码的定义,码,非分组码 分组码,奇异码 非奇异码,非唯一可译码 唯一可译码,非即时码 即时码 (非延长码,202
8、1/1/29,21,码树从树根开始向下长出m个树枝,成为m进制码树,树枝代表码元,树枝与树枝的交点叫做节点。经过r个树枝才能到达的节点称为r阶节点。向下不长出树枝的节点称为终端节点或端点。m进制码树各节点(包括树根)向下长出的树枝不会超过m,若树码的各个分支都延伸到最后一级端点称为满树(整树),否则称为非满树非整树。 码树上任一节点都对应一个码字,组成该码字的码元就是从树根开始到该节点所经过的树枝(码元)。 一个码,如果其所有的码字均处于终端节点,即端点,则该码就为非延长码,编码的定义-用码树来构造码字,2021/1/29,22,码树:表示各码字的构成(m进制,A,0,1,0,0,0,0,0,
9、0,0,0,0,0,0,0,0,1,1,1,1,1,1,1,0,1,1,1,1,1,二进制码树,2,0,0,0,0,0,1,1,1,1,1,2,2,2,2,2,三进制码树,树根码字的起点,分成m个树枝码的进制数,终端节点码字1101,中间节点码字的一部分,节数码长,2021/1/29,23,树码 如果有n个信源符号,那么在码树上就要选择n个终端节点,用相应的r元基本符号表示这些码字,任一即时码都可用树图法来表示。 当码字长度给定,即时码不是唯一的,2021/1/29,24,1,10,1000,100,1,0,0,0,码3对应的树如下图,编码的定义,该码树从根到终端节点所经路径上每一个中间节点皆
10、为码字,因此满足前缀条件。 虽然码3不是即时码,但它是唯一可译码,2021/1/29,25,编码的定义,满树: 每个节点上都有r个分枝的树等长码 非满树: 变长码 用树的概念可导出唯一可译码存在的充分和必要条件,即各码字的长度Ki应符合Kraft不等式,式中: m是进制数 n是信源符号数,2021/1/29,26,例:设二进制码树中X=(a1 , a2 , a3 , a4), K1=1,K2=2,K3=2,K4=3,应用Kraft不等式,得,不存在满足这种Ki的唯一可译码,0,0,0,1,1,0,10,110,11,中间节点,如果将各码字长度改成K1=1,K2=2,K3=3,K4=3,则,这样



- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 信息论与编码 第5章1教材 信息论 编码 教材
