第5章 信源编码• 通信的根本问题是如何将信源输出的信息在接 收端（信宿）精确地或近似地复制出来 • 前面的章节介绍了信源熵的概念，知道了传送 信源信息只需要具有信源极限熵极限熵或在限失真条件 下的信息率失真函数信息率失真函数大小的信息率 • 但是在实际通信系统中，用来传送信源信息的 信息率远大于远大于极限熵 • 将信源信息通过信道传送给信宿，怎样才能做 到尽可能不失真而又快速呢？ • 这就需要解决两个问题：第一，在不失真或允 许一定失真的条件下，如何用尽可能少的符号来 传送信源信息；第二，在信道受干扰的情况下， 如何增加信号的抗干扰能力，同时又使得信息传 输率最大 • 为了解决这两个问题，就要引入信源编码和信 道编码• 其中，信源编码又分为无失真信源编码和限失 真信源编码 • 由于这些定理都要求符号数很大才能使它的值 接近所规定的值，因而这些定理被称为极限极限定理 一般地： • 无失真信源编码定理称为第一极限定理； • 信道编码定理(包括离散和连续信道)称为第二 极限定理； • 限失真信源编码定理称为第三极限定理 • 这些定理的完善化，是香农信息论的主要内容 • 由于信源符号之间存在分布不均匀和相关性，使得信 源存在冗余度，信源编码的主要任务就是减少冗余，提 高编码效率。
具体说，就是针对信源输出符号序列的统 计特性，寻找一定的方法把信源输出符号序列变换为最最 短短的码字序列 • 相应地，信源编码的基本途径有两个，一是使序列中 的各个符号尽可能地互相独立，即解除相关性（例如英 文文献信源：在忽略单词之间的相关性的前提下，所有 单词、字母、标点符号全部视为单符号信源的消息输出 ，因而通过将一个完整单词视为一个单独的符号从而消 除单词内部字母之间的相关性 ！） ；二是使编码中各 个符号出现的概率尽可能地相等，即概率均匀化• 信源编码的基础是信息论中的两个编码定理： • 无失真编码定理； • 限失真编码定理• 无失真编码只适用于离散信源对于连续信源 ，只能在失真受限制的情况下进行限失真编码无失真编码• 无失真编码是可逆编码的基础 • 可逆是指当信源符号转换成代码后，可从代码 无失真地恢复原信源符号当已知信源符号的概 率特性时，可讨论它的符号熵H，这表示每个信 源符号所载有的信息量• 编码定理不但证明了必然存在一种编码方法， 使代码的平均长度可任意接近但不能低于符号熵 ，而且还阐明了达到这目标的途径，就是使概率概率 与码长匹配与码长匹配 • 无失真编码或可逆编码只适用于离散信源。
离 散信源的无失真信源编码实质上是一种概率匹配 编码它还可以进一步分为无记忆与有记忆两类 信源的概率匹配编码而从编码本身的构造可以 分为等长码、不等长码、分组码和非分组码限失真编码 • 对连续信源而言，信源输出的信息量是无限大 ，编成代码后就无法无失真地恢复原来的连续值 ，因为取值可有无限多个， 因此是不可能实现 无失真信源编码的此时只能根据限失真编码定 理进行限失真编码 • 有时，接收端并不要求完全精确地恢复信源输 出的信息，比如允许产生一定程度的失真，这是 符合大多数实际情况的因为在很多实际问题中 ，精确复制既无可能，也无必要连续信源就属 这一类，而且由于实际信道总是存在干扰，同时 信宿不论是人还是机器都存在一定的灵敏度和分 辨力• 超过信宿的灵敏度和分辨力所传送的信息是毫 无意义的，也是完全没有必要的比如话声信源 ，界别过多的划分，人耳就很难分辨图像信源 亦是如此，人们看电影，当图片超过每秒25张以 上时，人眼就能将离散的照片在人脑内反映成连 续画面 • 此时，就应该引入限定失真条件下的信源编码 问题 • 当信源编码定理出现后，编码方法就趋于合理 化了• 本章主要讨论离散离散信源无失真编码，从无失真 信源编码定理出发，重点讨论以香农码、费诺码 和哈夫曼码为代表的最佳码，然后介绍了限失真 编码定理、一些其它常用的信源编码方法。
5.1 编码的定义• 将信源消息分成若干组，即若干个：符号序列 Xi，Xi＝(Xi1，Xi2.Xil.XiL)，序列中的每个符 号取自于符号集A，Xil∈A＝{a1，a2，…，ai， …，an}而每个符号序列Xi依照固定的码表映 射成一个码字Yi，这样的码称为分组码分组码，有时也 叫块码 • 只有分组码才有对应的码表，而非分组码中则 不存在码表信源编码器信道码表图5-1 信源编码器示意图• 一个信源编码器，它的输入是信源的消息符号 X={x1，x2，…，xn}或符号序列，同时存在另 一符号Y={y1，y2，…，ym} ，一般来说，元素 yj是适合信道传输的，称为码元 (或者码符号) （码元是指各种编码器的输出符号，包括信源、 信道、加密等编码 • 编码器的功能就是将信源符号集中的符号X(或 者长为L的信源符号序列)变换成由yj(j=1，2…， m)组成的长度为l的一一对应的序列 • 输出的码元的序列称为码码/ /码字码字/ /码符号序列码符号序列 / /码码 元序列元序列 ，长度l称为码字长度或简称码长• 可见，一种编码方法（码制）就是从信源符号 或符号序列到码字或码元序列的一种映射关系。
例如ASCII码、原码、反码、补码、音频、图像 、视频压缩编码方法等• 信源编码实质上是指信源输出的原始消息符号 或符号序列，按一定的数学规则经信源编码器编 码后转换成另外的压缩符号 • 无失真信源编码：可精确无失真地复制信源输 出的消息无失真信源编码不考虑干扰问题，所 以它的数学描述比较简单若要实现无失真编码 ，则这种映射必须是一一对应的，即可逆的二元码• 若码元符号集为X={0，1}，即：码元只有2种 取值可能、所有码字都是二元序列，则称为二元 码二元码是数字通信和计算机系统中最常用的 一种码 • 如图5-1所示，如果信源输出符号序列长度L＝ 1，信源符号集A(a1，a2，…，an)• 信源概率空间为• 若将信源X通过二元信道传输，就必须把信源 符号ai变换成由0，1符号组成的码元序列，这个 过程就是信源编码 • 这是一种最简单的逻辑信道（信源编码器）－ 二元信道，信道的基本符号集为{0，1}• 类似地，二元信源是指：信源输出符号只有两 种取值；二进制信道是指输入、输出符号都只有 两种取值定长码和变长码• 码可分为两类： • 一、固定长度的码，如果一组码中所有码字的 码长都相同，则称为等长码或定长码。
如下表5- 1中的码1，8位ASCII码，BCD码等• 二、可变长度码，一组码中的所有码字的码长 各不相同，则称为变长码 ，如表中码2、哈夫曼 编码、大多数CPU的指令系统中的二进制机器指 令代码等表5-1 定长码与变长码信 源 符 号 ai信源 符号 出现 概率 p(ai)码表码 1码 2a1p(a1)0 00a2p(a2)0 10 1a3p(a3)1 00 0 1a4p(a4)1 11 1 1码的分类• 码的分类：码分类图奇异码和非奇异码• 若一组码中所有码字都不相同，即信源符号和 码字是一一对应的，则该码为非奇异码 • 若一组码中有相同的码字，则称为奇异码• 如表5-2中的码1是奇异码，码2是非奇异码表5-2 码的不同属性信源符号ai符号出现概率p(ai)码1码2码3码4a11/20011a21/411101001a31/80000100001a41/8110110000001唯一可译码• 若码的任意一串有限长的码元/码符号序列只能唯一 地分割成一个个的码字，即所对应的信源符号序列，则 此码称为唯一可译码否则就称为非唯一可译码• 如表5-2中的码2不是唯一可译码，码3是 • 又如，码字{0，10，11}是一种唯一可译码。
因为任 意一串有限长码序列，例如100 111 000，只能被分 割成10，0，11，10，0，0任何其他分割法都会产生 一些非定义的码字• 显然，奇异码不可能是唯一可译码，而非奇异码中有 非唯一可译码和唯一可译码• 显然，唯一可译码是可逆（无失真）编码的基 本要求即时码与非即时码 • 唯一可译码中又分为即时码与非即时码 • 如果接收端收到一个完整的码字后，不能立即 译码，必须结合后续的码元序列才能进行译码， 称为非即时码 • 在唯一可译的变长码变长码中，在译码时，往往希望 ：如果当前已经接收到一个完整的码元序列之后 ，无需参考后续的码元符号、立即能够确定对应 的码字，这种码制称为即时码即时码 • 即时码要求任何一个码字都不是其他码字的前 缀部分，所以也叫做异前缀码/非延长码如表5- 2中的码4• 可见，唯一可译码不一定是即时码，因为非即 时码(延长码)也具有唯一可译性• 即时码（异前缀码）一定是唯一可译码因为 ，如果没有一个码字是其他码字的前缀，则在译 码过程中，当收到一个完整码字的码符号序列时 ，无需考虑下一个符号，就能直接把它译成对应 的码字或信源符号码符号的分类码奇异码非分组码分组码非奇异码非唯一可译码非即时码即时码(非延长码)唯一可译码码树• 即时码的一种简单构造方法是采用树图法。
对给定码 字的全体集合来说，可以用码树来描述它 • 所谓树，具有根、树枝、 节点（根、分支/中间、叶 子/终端） 如图所示， A、B、C、D、E皆为节点： 图中最顶端A为根节点，A、B、C、D为中间节点，E 为叶子节点 • 在即时码的码树中，中间节点不安排码字，而只在叶 子节点安排码字，每个叶子节点所对应的码字就是从根 节点出发到叶子节点走过的路径(树枝)上所对应的码元 符号组成，如图的叶子节点E，走过的路径为ABCDE ，所对应的码符号分别为0、0、0、1，则E对应的码字 为0001可以看出，按树图法构成的码一定满足即时码 的定义(一一对应，异前缀码)ABCD000E11111010010001二进制码树• 通常可用码树来表示各码字的构成 0 10 1 0 10 1 0 1 0 1 0 10 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1三进制码树0 1 20 1 2 0 1 2 0 1 20 1 20 1 2• 从码树上可以得知，当第i阶的节点作为叶子 节点，且分配码字，则码字的码长为i。
（根节 点为0阶） • 任一即时码都可以用树图法来表示当码字长 度给定后，用树图法安排的即时码不是唯一的 如图，如果把左树枝安排为1，右树枝安排为0， 则得到不同的结果 • 对于一个给定的码，画出其对应的树，如果有 中间节点安排了码字，则该码一定不是即时码 • 每个中间节点上都有m个分支的树称为满树， 否则为非满树• 树根←→码字的起点 • 树枝←→码字中的一个码元 • 树的度←→码元符号取值的种数m(m元码) • 分支结点←→码字的一部分 • 叶子结点←→待编码符号、对应一个完整码字 • 满树←→等长码 • 非满树←→变长码• 即时码的码树图同样可以用来译码译码 • 当收到一串码符号序列后，首先从根节点出发 ，根据接收到的第一个码符号来选择应走的第一 条路径，再根据收到的第二个符号来选择应走的 第二条路径，直到走到叶子节点为止，就可以根 据终端节点对应的码字，立即判断出所接收。