10–5无失真信源编码.ppt

5.4.1 香农码 香农第一定理指出，可选择每个码字的长度满足关系式： 或： ? x ? 表示不小于 x 的整数。按不等式选择的码长所构成的码称香农码。香农码满足克拉夫特不等式，所以一定存在对应码字的长度的惟一可译码。 5.4.5 费诺码 费诺编码属于概率匹配编码，但它一般也不是最佳的编码方法，只有当信源的概率分布呈现 分布形式的条件下，才能达到最佳码的性能。 费诺码的编码步骤如下： 1）信源符号以概率递减的次序排列起来； 2）将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号“0”和“1”； 3）将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号； 4）依次下去，直至每个小组只剩一个信源符号为止； 5）信源符号所对应的码字即为费诺码。 例5.9 费诺码具有如下的性质： ①费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。 ②费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。 ③费诺码不一定是最佳码。因为费诺码编码方法不一定能使短码得到充分利用:当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法就会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，从而使平均码长增加。 5.4.2 霍夫曼码 1952年，霍夫曼（Huffman）提出了一种构造最佳码的方法，这是一种最佳的逐个符号的编码方法，一般就称作霍夫曼码。 设信源 ，其对应的概率分布为 ，则对二元霍夫曼码而言，其编码步骤如下： 5.4.2 霍夫曼码 1）将q个信源符号按概率递减的方式排列起来； 2）用“0”、“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个新的符号，从而得到只包含q-1个符号的新信源，称之为S信源的S1缩减信源； 3）将缩减信源中的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”、“1”码符号表示，这样又形成了由q-2个符号构成的缩减信源S2； 4）依次继续下去，直到缩减信源只剩下两个符号为止，将这最后两个符号分别用“0”、“1”码符号表示； 5）从最后一级缩减信源开始，向前返回，沿信源缩减方向的反方向取出所编的码元，得出各信源符号所对应的码符号序列，即为对应信源符号的码字。 例5.7霍夫曼码 表5.15 三种编码方法的比较 说明：霍夫曼码是一种即时码，可用码树形式来表示。 例设有离散无记忆信源 5.4.2 霍夫曼码 哈夫曼编码方法得到的码并非是唯一的。造成非唯一的原因如下： 每次对信源缩减时，赋予信源最后两个概率最小的符号，用0和1是可以任意的，所以可以得到不同的哈夫曼码，但不会影响码字的长度。 对信源进行缩减时，两个概率最小的符号合并后的概率与其它信源符号的概率相同时，这两者在缩减信源中进行概率排序，其位置放置次序是可以任意的，故会得到不同的哈夫曼码。此时将影响码字的长度，一般将合并的概率放在上面，这样可获得较小的码方差 5.4.2 霍夫曼码 例设有离散无记忆信源 5.4.2 霍夫曼码 例设有离散无记忆信源 5.4.2 霍夫曼码 限失真信源编码 由实际生活经验我们知道，一般人们并不要求完全无失真地恢复消息。对人的心理视觉研究表明，人们在观察图像时主要是寻找某些比较明显的目标特征，而不是定量地分析图像中每个像素的亮度，或者至少不是对每个像素都等同地分析。例如观看一段视频或观察一幅图像，人们可能会关注其主要情节，对视频或图像中的细节并不是那么注意，此时便允许视频或图像有一定程度的失真。 由香农第一定理知，无论哪种信道，只要信息传输率R小于信道容量C，总能找到一种编码方法，使得在信道上能以任意小的错误概率，以任意接近的传输率来传送信息。 实际信道中，信源输出的信息传输率R一般都会超过信道容量，因此也就不可能实现完全无失真地传输信源的信息。 由香农第三定理知，在允许一定失真度D的情况下，信源输出的信息传输率可压缩到R(D)值，只要信息传输率R大于R(D)，一定能找到一种编码方法，使得译码后的失真小于D。香农第三定理从理论上给出了信息传输率与允许失真之间的关系，奠定了信息率失真理论的基础。信息率失真理论是进行量化、数模转换、频带压缩和数据压缩的理论基础。 5.5 实用信源编码方法 无失真和限失真信源编码定理，说明了最佳码的存在性，但没有给出具体构造码的方法，实用的编码方法需要根据