信息论PPt(叶中行).ppt

第3章 数据压缩和信源编码 §3.1 等长码 §3.2 变长编码 §3.3 哈夫曼码 §3.4 香农码和费诺玛 3.5 通用信源编码 本节将主要介绍 LZ算法， 改进的LZ-Welcn?算法 Kieffer-Yang算法， LZ算法基于符号串匹配的算法，而LZ-Welcn?算法是基于字典的算法，它们都是利用信源输出符号自身的信息来进行压缩编码。Kieffer-Yang算法（简称YK算法）则兼顾了字符串匹配和算术码结构的优点。 LZ算法 * 信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。 信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。 §3.1 等长码 信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础； 限失真信源编码定理：是连续信源/模拟信号编码的基础。 信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类 离散信源编码：独立信源编码，可做到无失真编码； 连续信源编码：独立信源编码，只能做到限失真信源编码； 相关信源编码：非独立信源编码。 干扰源 信道 信道译码器 信道编码器 信源译码器 信源编码器 信宿 信源 等效信源 等效信宿 等效干扰信道 信息传输系统模型 信源编码示意图 信源 信源编码器 信源译码器 信宿 编码器可以看作这样一个系统，它的输入端为原始信源S，其符号集为 ；而信道所能传输的符号集 为 编码器的功能是用符号集X中的元素，将原始信源的符号 变换为相应的码字符号 ，所以编码器输出端的符号集为   称为码字， 为码字 的码元个数，称为码字 的码字长度，简称码长。 编码器 1、二元码： 码符号集X={0,1}，如果要将信源通过二元信道传输，必须将信源编成二元码，这也是最常用的一种码。 2、等长码： 若一组码中所有码字的长度都相同，称为等长码。 3、变长码： 若一组码中所有码字的长度各不相同，称为变长码。 4、非奇异码： 若一组码中所有码字都不相同，称为非奇异码。 §3.2 变长编码 信源符号 出现概率 码1 码2 码3 码4 s1 s2 s3 s4 1/2 1/4 1/8 1/8 0 11 00 11 0 10 00 01 1 10 100 1000 1 01 001 0001 5、奇异码： 若一组码中有相同的码字，称为奇异码。 6 、同价码: 每个码字占相同的传输时间 8、唯一可译码： 若码的任意一串有限长的码符号序列只能被唯一的译成所对应的信源符号序列，则称此码为唯一可译码。 9、即时码（瞬时编码）：没有一个码字是其他码字的前缀的唯一可译码称为~。 码 非分组码 分组码 奇异码 非奇异码 非唯一可译码 唯一可译码 非即时码 即时码 10、码分类 2、即时码的树图构造法 树根——码字的起点 树枝数——码的进制数 结点——码字或码字的一部分 节数——码长 端点——码字 满树——等长码 非满树——变长码 1 0 0 1 A 1 1 0 0 1 0 0 0 0 1 1 0 1 0 0 1 1 1 1 01 001 0001 码4的树图 *