第5章信源编码技术解析.ppt

第5章 信源编码技术 5.1 最佳变长编码 回顾： 1、根据信源编码理论，将能够荷载一定信息量，且码字的平均长度最短，可分离的变长码字集合称为最佳变长码。 2、最佳变长码编码的基本原则是：概率大的信源符号分配短的码字，而概率小的信源符号分配长码字，从而使得平均码长最短。 具有代表性变长编码方法有：香农码，费诺码和哈夫曼码等。 5.1.1 香农码 香农码的根据：离散无记忆信源的自信息量 设离散无记忆信源所对应的概率空间为 香农码编码方法 (1)将信源消息符号按其出现的概率大小依次排列为 总结： 1、由于每个信源符号码长是根据信源符号的信息量选择，从局部来看每个码长的取值都是最佳的。所以从局部看，香农码是最佳码。 但是香农码构造码字时没有综合使用信源统计特性，所以码长并非最短的。 2、香农码编码采用累计概率小数部分的二进制表示作为码字，从而保证了码字是唯一可译码的。 5.1.2费诺码 费诺码的基本思想： 1、按照累加概率尽可能相等的原则对信源符号进行分组： 对于二元码，则每次分为两组; 对于d元码，则每次分为d个组。 并且给不同的组分配一个不同的码元符号。 2、对其中的每组按照累计概率尽可能相等的原则再次进行分组，并指定码元符号，直到不能再分类为止。 3、然后将每个符号指定的码元符号排列起来就得到相应的码字。 费诺二元码的编码步骤 1、将源消息符号按概率大小排序： 2、将依次排列的信源符号分为两大组，使每组的概率和尽可能相等，且每组赋与二进制码元“0”和“1”。 3、将每一大组的信源符号再分为两组，使每组的概率和尽可能相等，且每组赋与二进制码元“0”和“1”。 4、如此重复，直至每组只剩下一个符号。 信源符号所对应的码字即费诺码。 例5.2对例5.1的信源进行费诺编码,，具体编码过程参见表5.2 总结： 1、费诺码要比上述香农码的平均码长小，编码效率高。 2、从上面的例子可以看出，p(a4)p(a2)，而码长L4L2，从统计角度来看，平均码长一定不是最短的; 如果将两个符号对应的码字互换，这样编码得到的平均码长肯定小于原来的平均码长。 3、费诺码的平均码长满足 费诺码的最佳性 1、保证每个集合概率和近似相等，保证d个码元近似等概率，每个码字承载的信息量最大，码长近似最短。 2、是次最佳的编码方法，只在当信源符号概率满足： 时达最佳。 5.1.3哈夫曼码 基本思想： 1、概率大的符号分配短码字，而概率小的信源符号分配长码字 2、首先为小概率符号分配码元 3、分配码元后的符号进行概率合并 4、然后按照大小顺序重排概率，并对概率小的符号或者符号集合分配码元，直到概率合并结束为止。 5、然后逆向有哪些信誉好的足球投注网站参与概率合并时分配的码元符号，形成对应的码字。 Huffman码的最佳性 最佳性：所有可能的编码方法中，平均码长最短。 定理1 对于给定的信源，有最佳唯一可译二元码，其最小概率的两个码字Ck-1和Ck的长度最长并且相等①，它们之间仅最后一位码元的取值不同②（一个为0、一个为1）。 关于含义①： 对于符号a1,a2，码长分别为n1,n2 如果p(a1)p(a2),那么当n1n2时，平均常常最短。 假如n1n2，则有 n2 p(a1)+n1 p(a2) n1 p(a1)+n2 p(a2) 所以，定理的第①部分成立。 关于含义②：二元Huffman码不可能出现单分支。 对信源 且假定 对aK-1和aK的码字最后一位分别指定0、1，然后合并，产生辅助符号a’k-1,做一辅助集 排序后 对剩下的符号重复合并最小概率符号，分配码元0、1，到最后对两个符号重复上述操作，编码完成。 定理2 编码对辅助集最佳，对原始集也最佳。（平均码长最短） 二元码的哈夫曼编码步骤 (1)将信源消息符号按其出现的概率大小依次排列为 (2)取两个概率最小的两个信源符号分别分配码元0和1，并将这两个概率相加作为一个新符号的概率，与未分配的二进符号的符号一起重新进行概率排序。 (3)对重排后的两个概率最小符号重复步骤（2）的 过程。 (4)不断继续上述过程，直到最后两个符号配以0和1 为止。 (5)从最后一级开始，反向有哪些信誉好的足球投注网站参与编码的符号，得 到各个信源符号所对应的码元序列，即相应的码 字。 例5.3 对例5.1的信源符号进行哈夫曼编码，给出编码过程，每个信源符号的码字，码长，求平均码长、编码效率。 平均码长 编码效率 关于哈夫曼编码的讨论 1、每次对信源缩减时，赋予信源最后两个概率最小的符号，分配码元0和1是可以任意的，即大概率符号或者合并后的符号集合可以分配码元0也可以是1，这种选择任意性可以得到不同的哈夫曼码，但不会影响码