信息论与编码 张祖平/Zhang Zuping 电子信息工程系 School of Information Science and Engineering,Central South University , zpzhang Information Theory & Coding 2013 秋季 信息111Inf Theory & Coding-张祖平 本章主要内容 (Main Content ) 6.1 单义可译码 6.2 非延长码 6.3 单义可译定理 6.4 平均码长与有效性 6.5 平均码长的界限定理 6.8 霍夫曼（Huffman）编码 6.0 编码概述 6.6 香农码 6.7 费诺码 2013 秋季 信息112Inf Theory & Coding-张祖平 信源信源编码信道编码 信道译码信源译码信宿 信道 6.0 编码概述 2013 秋季 信息113Inf Theory & Coding-张祖平 4 生活中编码实例? 学号、身份证号码、一卡通、汉语等编码。 编码实质：信息的组织方式。对信源的原始符号按一定的数学 规则进行变换。 结论: 信息无处不在 ，编码无处不在。 6.0 编码概述 2013 秋季 信息114Inf Theory & Coding-张祖平 通信的基本问题： 通信的基本问题：如何高速、高质地传送信息。 高速和高质有效性和可靠性。 通信的还需要解决的问题： 1：解决信源发出的消息不适合信道的传输，信源编码 2：希望信道可以尽快的传输信息，信源编码的编码效率 3：信道中有噪声，进入信道以前需要加入抗干扰能力，信道编码 总结得到： 信息质量一定时，如何提高信息传输速度（提高编码效率或压缩比） -信源编码（本章讨论问题），提高信息传输的有效性。 信道传输速度一定时，如何提高信息传输质量（抗干扰能力） ， -信道编码（下一章讨论），提高信息传输的可靠性。 5 6.0 编码概述 2013 秋季 信息115Inf Theory & Coding-张祖平 信源编码定义 将信源输出的消息符号进行有效变换，使其成为适合信道传输的符号 序列，且使该序列组成的新信源的冗余度尽可能地减少。 信源编码目的 符号变换：使信源输出符号与信道的输入符号相匹配。 减少冗余：提高通信的有效性，就是针对信源输出符号序列的统计特 性，寻找一定的把信源输出符号序列变换为最短码字序列的方法。 信源编码基本方法 （1） 解除相关性：使序列中的各个符号尽可能地互相独立。比如 ：一个英文单词视为系列符号从而消除单词内部字母之间的相关性 。 （2） 概率均匀化：使编码中各个符号出现的概率尽可能地相等， 尽可能缩短出现概率大的信源符号的码字，压缩每个信源符号的平均 比特数。即同样多的信息用较少的码率传送，使单位时间内传送的平 均信息量增加，从而提高通信的有效性。 6 6.0 编码概述 2013 秋季 信息116Inf Theory & Coding-张祖平 信源编码的两大定理 信源编码理论是信息论的一个重要分支，其理论基础是两个定理。 无失真信源编码定理：是离散信源/数字信号编码的基础；无失真编 码是可逆的，即当信源符号变换成代码以后，可以从代码无失真地恢 复出原信源符号。 限失真信源编码定理：是连续信源/模拟信号编码的基础，如语音、 图像等信号。在连续信源的情况下，由于信源的信息量趋于无限，显 然不能用离散符号序列来完成无失真编码，而只能进行限失真编码。 香农信息论三大定理 无失真信源编码定理为第一极限定理； 信道编码定理（离散和连续信道）称为第二极限定理； 限失真信源编码定理称为第三极限定理。 7 6.0 编码概述 2013 秋季 信息117Inf Theory & Coding-张祖平 编码器的数学模型 8 编码器可以看作这样一个系统，它的输入端为原始信源 S，其符号集为 ；而信道所能传输的符号集 为 。编码器的功能是用符号集X中的元素， 将原始信源的符号 变换为相应的码字符号 ，所以编码 器输出端的符号集为 称为码字， 为码字 的码元个数，称为码字 的码 字长度，简称码长。码字的集合C 称为码书。 称为码元。 编码器 6.0 编码概述 2013 秋季 信息118Inf Theory & Coding-张祖平 单义可译码 若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源 符号序列，则此码称为惟一可译码（单义可译码） 否则就称为非惟一可译码或非单义可译码。 比如： 信源S的符号集是英文字母和标点 而信道只能传输0,1序列，即信道要求的信源其符号集只能包含0和1 我们需要用0和1组成的码字来表示S中的英文字母和标点 要求1：码字要与S中的每种字符一一对应 要求2：码字序列要与S的N个符号组成的序列一一对应 6.1 单义可译码 2013 秋季 信息119Inf Theory & Coding-张祖平 10 二元码：若码符号集X0，1，即：码元只有2种取值可能、所有码字都是 二元序列，则称为二元码。二元码是数字通信和计算机中最常用的一种码。 二元信道：一种最简单的逻辑信道（信源编码器），信道的基本符号集为0 ，1，输入、输出符号都只有这两种取值。 二元信源：信源输出符号只有这两种取值。 6.1 单义可译码 2013 秋季 信息1110Inf Theory & Coding-张祖平 11 奇异码 非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的 码符号序列，不同信源符号可分辨)，则称为非奇异码。 奇异码：反之，若码组中含有相同的码字则为奇异码。 6.1 单义可译码 2013 秋季 信息1111Inf Theory & Coding-张祖平 12 6.1 单义可译码 2013 秋季 信息1112Inf Theory & Coding-张祖平 13 定长码（等长码）：若一组码中所有码字的码长都相同，则称为定长码。 因为长度相同，相当于每个码字后有一个无形的逗号(点),又叫逗号(点)码 。 变长码：若一组码中所有码字的码长各不相同，则称为变长码。 非奇异的等长码 一定是单义可译码 6.1 单义可译码 2013 秋季 信息1113Inf Theory & Coding-张祖平 14 奇异码非奇异的 等长码 一定是 单义可译码 都是非奇异的 且都是单义可译码 6.1 单义可译码 2013 秋季 信息1114Inf Theory & Coding-张祖平 15 W4，W5 都是非奇异的 且都是单义可译码 非即时码：如果接收端收到一个完整的码字后不能立即译码，必须结合后续 的码元序列才能进行译码，称为非即时码。如码4，收到10无法判断结束。 即时码：在译码时，如果当前已经接收到一个完整的码元序列之后，无需参 考后续的码元符号、立即能够确定对应的码字，这种码制称为即时码。如码 5，每个码字最后符号都是1，收到1好像逗(点)号，又叫逗号(点)码。 6.2 非延长码 2013 秋季 信息1115Inf Theory & Coding-张祖平 16 异前缀码/非延长码：即时码要求任何一个码字都不是其他码字的前缀部分 ，所以也叫做异前缀码/非延长码，反之就叫延长码。 即时码（异前缀码）一定可以单义可译码。因为，如果没有一个码字是其他 码字的前缀，则在译码过程中，当收到一个完整码字的码符号序列时，无需 考虑下一个符号，就能直接把它译成对应的码字或信源符号。 所有码 非奇异码 单义可译码 即时码 6.2 非延长码 2013 秋季 信息1116Inf Theory & Coding-张祖平 17 怎样构建非延长码？ 可用“树图法/码树”来构建非延长码 6.2 非延长码 2013 秋季 信息1117Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 得到一阶节点 标记每条树枝 树枝数为r W1可以二选一 18 6.2 非延长码 2013 秋季 信息1118Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 0 0 1 1 该选哪个节点？ 19 6.2 非延长码 2013 秋季 信息1119Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 0 0 1 1 该选哪个节点？ 20 6.2 非延长码 2013 秋季 信息1120Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 0 0 1 1 01 1 21 6.2 非延长码 2013 秋季 信息1121Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 0 0 1 1 01 1 w1=1 w2=01 w3=001 w4=0001 未用尽 22 6.2 非延长码 2013 秋季 信息1122Inf Theory & Coding-张祖平 q=4, r=2, n1=1, n2=2, n3=3, n4=4 01 01 01 1 w1=1 w2=01 w3=001 w4=0001 未用尽 23 6.2 非延长码 2013 秋季 信息1123Inf Theory & Coding-张祖平 24 根：树的最上端 树枝的个数为r， r=2为二元码树 0 1 0 0 1 1 1 1 01 001 0001 码5的树图 A B C D 中间节点 （空心） 节点：树枝的终 端，从节点生出 树枝，每个节点 伸出r个枝 终端节点 （实心） 码字：从根到终 端节点对应的码 符号，又称树叶 q=4, r=2, n1=1, n2=2, n3=3, n4=4 w1=1 w2=01 w3=001 w4=0001 6.2 非延长码 2013 秋季 信息1124Inf Theory & Coding-张祖平 25 该树的5个终端 节点 W1,W2,W3,W 4,W5分别表示5 个二进制码字 0，100，111 ，1010，1011 码树的性质：任一即时码都可用树图表示。 即时码不是惟一的。 单义可译码成为即时码的充要条件是其中任何一个码字都不是其他码字 的前缀，按树图法构成的码一定满足即时码的充要条件，因为从根到叶 所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前 缀的限制。 6.2 非延长码 2013 秋季 信息1125Inf Theory & Coding-张祖平 26 满树 每个码字的联枝数均相同时(定长码) 非满树 当码字的联枝数不同时(变长码) 全树 每个中间节点的后续分支数均为m 非全树 有些中间节点的后续分支数不足m 满树非全树 树根 终节点中间节点 非满树，全树 6.2 非延长码 2013 秋季 信息1126Inf Theory & Coding-张祖平 27 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 三进制码树 6.2 非延长码 2013 秋季 信息1127Inf Theory & Coding-张祖平 练习练习 28 S：s1，s2，s9，A=0，1，2，q=3 6.2 非延长码 2013 秋季 信息1128Inf Theory & Coding-张祖平 29 设原始信