《信息论与编码基础》第5章 基本的信源和信道编码定理.pptVIP

信息论与编码基础 第五章 基本的信源和信道编码定理 信息科学与技术学院 计算机科学系 蔡国扬 isscgy@mail.sysu.edu.cn 第五章 基本的信源和信道编码定理 本章主要内容 无失真信源编码定理 编码器的概念 等长码 等长信源编码定理 变长码 变长信源编码定理 有噪信道编码定理 错误概率与编译码规则 有噪信道编码定理 联合信源信道编码定理 5.1 无失真信源编码定理 通信的实质是信号的传输。高效率、高质量地传输信息是信息传输的基本问题。要做到既不失真又快速地通信，需要解决两个问题： 信源编码问题：在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以提高信息传输率。 信道编码问题：在信道受到干扰的情况下，如何增加信号的抗干扰能力，提高信息传输的可靠性，同时又使得信息传输率最大。 一般地，提高抗干扰能力（降低失真或错误概率）往往以增加信源冗余度，降低信息传输率为代价；反之，要提高信息传输率则需要降低信源冗余度，这常常又使得抗干扰能力减弱。二者是有矛盾的。 5.1 无失真信源编码定理 信息论的编码定理从理论上证明了，存在某种最佳的编码或信息处理方法，能够解决上述矛盾，做到既有效又可靠地传输信息。这些结论对各种信息系统的设计和估价具有重大的理论指导意义。 信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。 信源编码常分为无失真信源编码和限失真信源编码，前者主要用于文字、数据信源的压缩，后者主要用于图像、语音信源的压缩。 本节讨论对离散信源进行无失真编码的方法和理论极限，引出香农第一定理。 5.1 无失真信源编码定理 5.1.1 编码器 编码是对信源的原始符号按一定的数学规则进行的一种变换。从下面的讨论可以进一步理解，它实际上是从信源符号到码符号的一种映射。若要实现无失真编码，则必须保证这种映射是一一对应的、可逆的。 为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码问题。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码问题。 编码器模型：由于信源编码可以不考虑抗干扰问题，它的数学模型比较简单。下图为一个编码器模型： 5.1 无失真信源编码定理 无失真信源编码器模型 5.1 无失真信源编码定理 输入是信源符号集：S={s1, s2, …, sq}，X 为编码器所用的编码符号集，包含 r 个元素 {x1, x2, …, xr }，一般元素 xj 是适合信道传输的，称为码符号（或码元）。编码器将信源符号集中的信源符号 si（或长为N的信源符号序列 ? i ）变换成由码符号 xj 组成的长为 li 的与信源符号一一对应的输出序列 Wi 。即： 5.1 无失真信源编码定理 5.1.2 码的分类 对于编码器而言，根据码符号集合 X 中码元的个数不同以及码字长度是否一致，有以下一些常用的编码形式： (1) 二元码和 r 元码 若码符号集为 {0, 1}，编码所得码字为一些适合在二元信道中传输的二元序列，则称之为二元码。二元码是数字通信与计算机系统中最常用的一种码。若码符号集共有 r 个元素，则所得之码称为 r 元码. (2) 等长码 若一组码中所有码字的长度都相同（即 li = l , i =1,2,..,q），则称之为等长码。 5.1 无失真信源编码定理 (3) 变长码 若一组码中码字的码长各不相同（即码字长度 li 不等），则称之为变长码。 如表中“编码1”为等长码，“编码2”为变长码。 5.1 无失真信源编码定理 (4) 分组码 若每个信源符号按照固定的码表映射成一个码字，则称之为分组码。否则就是非分组码。 如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。 (5) 非奇异码和奇异码 若一组码中所有码字都不相同（即所有信源符号分别映射到不同的码符号序列），则称之为非奇异码。反之，则为奇异码。如下表中的“编码2”是奇异码，其他码是非奇异码。 5.1 无失真信源编码定理 表中的“编码2”是奇异码，其他码是非奇异码。 5.1 无失真信源编码定理 (5) 同价码 若一组码的码符号集 X={x1, x2, …, xr} 中每个码符号所占的传输时间都相同，则称该码为同价码。否则称为非同价码。 一般情况下我们讨论的是同价码。对同价码而言，等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。 例：电报中常用的摩尔斯码是非同价码，其码符号(.) 和划(-)所占的传输时间不相同。 (6) 码的 N 次扩展码 假定某码 C