五章节信源编码教学讲义

《五章节信源编码教学讲义》由会员分享，可在线阅读，更多相关《五章节信源编码教学讲义（110页珍藏版）》请在金锄头文库上搜索。

1、第五章 信源编码,信息通过信道传输到信宿的过程即为通信。要做到既不失真又快速地通信，需要解决两个问题： 在不失真或允许一定失真条件下，如何提高信息传输速度-这是本章要讨论的信源编码问题. 在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大-这是下章要讨论的信道编码问题.,一般来说，抗干扰能与信息传输率二者相互矛盾。然而编码定理已从理论上证明，至少存在某种最佳的编码能够解决上述矛盾，做到既可靠又有效地传输信息。 信源虽然多种多样，但无论是哪种类型的信源，信源符号之间总存在相关性和分布的不均匀性，使得信源存在冗余度。信源编码的目的就是要减少冗余，提高编码效率。,信源编码的基

2、本途径有两个: 一是编码后使序列中的各个符号之间尽可能地 互相独立，即解除相关性-方法包括预测编 码和变换编码. 二是使编码后各个符号出现的概率尽可能相等，即均匀化分布-方法主要是统计编码.,5.1 编码器及相关概念,为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。,5.1.1 码的分类,一.编码器模型 由于信源编码可以不考虑抗干扰问题，所以它的数学模型比较简单。下图为一个编码器模型:,输入是信源符号集: x为编码器所用的编码符号集，包含r个元素 ，

3、称为码符号(码元) . 由码符号 组成的输出序列 称为码字. 其长度 称为码字长度或码长，全体码字 的集合C称为码或码书 . 编码器将信源符号集中的信源符号 （或长为N的信源符号序列 ）变成由码符号组成的长为的与信源符号一一对应的输出序列。即 :,二.码的分类: 对于编码器而言，根据码符号集合X中码元的个数不同以及码字长度是否一致，有以下一些常用的编码形式：,(1)二元码和r元码 若码符号集 ，编码所得码字为一些适合在二元信道中传输的二元序列，则称二元码。二元码是数字通信与计算机系统中最常用的一种码。若码符号集共有 r 个元素，则所得之码称为 r 元码. (2)等长码 若一组码中所有码字的长度

4、都相同-（即 ），则称为等长码.,(3) 变长码 若一组码中码字的码长各不相同（即码字长度 不等），则称为变长码 . 如表中“编码1”为等长码，“编码2”为变长码。,(4)分组码 若每个信源符号按照固定的码表映射成一个码字，则称为分组码。否则就是非分组码. 如果采用分组编码方法，需要分组码具有某些属性，以保证在接收端能够迅速而准确地将接收到的码译成与信源符号对应的消息。下面讨论分组码的一些直观属性。,1）非奇异码和奇异码 若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列)，则称为非奇异码。反之，则为奇异码。如表中的“编码2”是奇异码，其他码是非奇异码。,概率,2）同价码 若码符

5、号集X： 中每个码符号所占的传输时间都相同，则所得的码为同价码。 我们一般讨论同价码，对同价码来说等长码中每个码字的传输时间相同，而变长码中每个码字的传输时间就不一定相同。,3）码的N次扩展码 假定某一码，它把信源 中的符号 一一变换成码C中的码字 ，则码C的N次扩展码是所有N个码字组成的码字序列的集合。,例如：若码 满足： 则码C的N次扩展码集合 ,其中： 即码C的N次扩展码中，每个码字 与信源的N次扩展信源 中的每个信源符号 是一一对应的：,4）惟一可译码 若任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（或称单义可译码）。否则就称为非惟一可译码或非单

6、义可译码。 若要使某一码为惟一可译码，则对于任意给定的有限长的码符号序列，只能被惟一地分割成一个个的码字。,例如：对于二元码 ，当任意给定一串码字序列，例如“10001101”，只可唯一地划分为1,00,01,1,01，因此是惟一可译码；而对另一个二元码 ，当码字序列为“01001”时，可划分为0,10,01或01,0,01，所以是非惟一可译的。,对惟一可译码又分为即时码和非即时码：如果在接收端收到一个完整的码字后，就能立即进行译码，这样的码叫做即时码；而在接收端收到一个完整的码字后，还需等下一个码字接收后才能判断是否可以译码，这样的码叫做非即时码。 即时码又称为非延长码，对即时码而言，在码本

7、中任意一个码字都不是其它码字的前缀部分。对非即时码来说，有的码是惟一可译的，有的码是非惟一可译的，主要取决于码的总体结构。,综上所述，可将码作所示的分类：,5.1.2 码树,对于给定码字的全体集合，可以用码树来描述。 对于r进制的码树，如下页图所示，其中图(a)为二元码树，图(b)为三元码树。在码树中点是树根，从树根伸出个树枝，构成元码树。树枝的尽头是节点，一般中间节点会伸出树枝，不伸出树枝的节点为终端节点，编码时应尽量在终端节点安排码字。,码树中自树根经过一个分枝到达一阶节点，一阶节点最多为r个，二阶节点的可能个数为r2个，n阶节点最多有rn个，若将从每个节点发出的个分枝分别标以0，1，r-

8、1，则每个n阶节点需要用n个r元数字表示。如果指定某个n阶节点为终端节点，用于表示一个信源符号，则该节点就不再延伸，相应的码字即为从树根到此端点的分枝标号序列，该序列长度为n，用这种方法构造的码满足即时码的条件，因为从树根到每一个终端节点所走的路径均不相同，所以一定满足对即时码前缀的限制。如果有个q信源符号，那么在码树上就要选择q个终端节点，用相应r的元基本符号表示这些码字。,若树码的各个分支都延伸到最后一级端点，此时将共有个码字，这样的码树称为整树，如图(a)所示。否则就称为非整树，如图(b)所示，这时的码字就不是等长码了。 因此，码树与码之间具有如下一一对应的关系： 树根码字起点； 树枝数

9、码的进制数； 节点码字或码字的一部分； 终端节点码字； 阶数码长； 非整树变长码； 整树等长码。,5.1.3 Kraft不等式,利用码树可以判断给定的码是否为惟一可译码，但需要画出码树。在实际中，我们可以利用克拉夫特（Kraft）不等式，直接根据各码字的长度来判断惟一可译码是否存在，即各码字的长度应符合克拉夫特不等式： 式中，r为进制数也即码符号的个数，q为信源符号数。,Kraft不等式是惟一可译码存在的充要条件，其必要性表现在如果码是惟一可译码，则必定满足Kraft不等式;充分性表现在如果满足Kraft不等式，则这种码长的惟一可译码一定存在，但并不表示所有满足Kraft不等式的码一定是惟一可

10、译码。 因此，克拉夫特不等式是惟一可译码存在的充要条件，而不是惟一可译码的充要条件。,5.2 变长编码,变长码往往在码长的平均值不很大时，就可编出效率很高而且无失真的码，其平均码长受香农第一定理所限定，即： 若对信源离散无记忆信源S的N次扩展信源 进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：,且当 时有： 其中， 为N次扩展信源的平均码长， 为信源符号扩展序列 的码长. 为对扩展信源进行编码后，每个信源符号 编码所需的等效的平均码长。,要做到无失真的信源编码，平均每个信源符号所需最少的r元码元数为信源的熵 。 即 它是无失真信源压缩的极限值。

11、若编码的平均码长小于信源的熵值 ，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。 通过对扩展信源进行变长编码，当N时，平均码长,无失真信源编码的实质： 对离散信源进行适当的变换，使变换后形成的新的码符号信源(即信道的输入信源)尽可能为等概率分布，以使新信源的每个码符号平均所含的信息量达到最大，使信道的信息传输率达到信道容量，实现信源与信道理想的统计匹配。这实际上就是香农第一定理的物理意义。,为了衡量各种编码是否达到极限情况，定义变长码的编码效率为： 常通过编码效率来衡量各种编码的优劣. 为了衡量各种编码与最佳码的差距，定义码的剩余度为： 信息传输率定义为： 注意:虽然与在数值上相同

12、，但它们的单位不同，编码效率没有单位，而信息传输率的单位是比特/码符号。,在二元无噪无损信道中 在二元信道中，若编码效率 =1，R=1比特码符号，则达到信道的信道容量，此时编码效率最高，码的剩余度为零。 前面已经说明，对于某一个信源和某一符号集来说，凡是满足克拉夫特不等式的惟一可译码可以有多种，在这些惟一可译码中，如果有一种（或几种）码，其平均编码长度小于所有其他惟一可译码的平均编码长度，则该码称为最佳码（或紧致码）。,为了使得平均编码长度为最小，必须将概率大的信息符号编以短的码字，概率小的符号编以长的码字。能获得最佳码（或次最佳码）的编码方法有很多，本节重点介绍：香农(shannon) 编码

13、、费诺(Fano) 编码、霍夫曼(Huffman)编码。,5.2.1 香农码,香农第一定理指出，可选择每个码字的长度满足关系式： 或： x 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。,一般情况下，按照香农编码方法编出来的码，其平均码长不是最短的，也即不是紧致码(最佳码)。只有当信源符号的概率分布使不等式左边的等号成立时，编码效率才达到最高。,香农码的编码步骤如下： 1）将个信源符号按概率递减的方式进行排列： 2）按香农不等式计算出每个信源符号的码长 ； 3）为了编成惟一可译码，计算第i个信源符号的累加概率 4

14、）将累加概率 用二进制数表示。 5）取 对应二进制数的小数点后位构成该信源符号的二进制码字。,例:设信源共有七个信源符号，其概率分布如表所示，试对该信源进行香农编码。 解:计算过程见下页 码的性能分析： 通过计算可得此信源的熵: (比特符号) 而码的平均长度: (二元码符号符号) 编码效率：,概率,累加概率,码长,5.2.2 费诺码,费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。,费诺码的编码步骤如下： 1）信源符号以概率递减的次序排列起来； 2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对

15、每组各赋予一个二元码符号“0”和“1”； 3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号； 4）依次下去，直至每个小组只剩一个信源符号为止； 5）信源符号所对应的码字即为费诺码。,例:将下列消息按二元费诺码方法进行编码。 解:其编码过程如下页： 码的性能分析： 此信源的熵 (比特符号)， 而码的平均长度 (二元码符号符号) 显然，该码是紧致码，编码效率： 该码之所以能达到最佳，是因为信源符号的概率分布正好满足式，否则，在一般情况下是无法达到编码效率等于“1”的。,费诺码具有如下的性质： 费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。 费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。 费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。 r 元费诺码 前面讨论的费诺码是二元费诺码，对r元费诺码，与二元费诺码编码方法相同，只是每次分组时应将符号分成概率分布接近的r个组。,5.2.3 霍夫曼码,1952年，霍夫曼（Huffm