第五章信源编码技巧.ppt

信息论与编码技术 展爱云 zayscj@ecjtu.jx.cn 通信工程教研室 本课程的相关要求 课程基础（概率论） 上课要求 学习要求 实验要求（C\C++) 本课程的重点 信息的基本概念 信息量的计算 典型的几种信源编码方法 典型的几种信道编码方法 第5章 信源编码 霍夫曼编码实例 游程编码（Run-Length Encoding）：它通过将信源中相同符号序列转换成一个计数字段再加上一个重复字符标志实现压缩。 基本思想：算术编码不是将单个信源符号映射成一个码字，而是把整个信源表示为实数线上的0到1之间的一个区间，其长度等于该序列的概率，再在该区间内选择一个代表性的小数，转化为二进制作为实际的编码输出。消息序列中的每个元素都要用来缩短这个区间。消息序列中元素越多，所得到的区间就越小，当区间变小时，就需要更多的数位来表示这个区间。 采用算术编码每个符号的平均编码长度可以为小数。 算术编码举例 6 词典编码 词典编码主要利用数据本身包含许多重复的字符串的特性。例如：吃葡萄不吐葡萄皮，不吃葡萄倒吐葡萄皮。 我们如果用一些简单的代号代替这些字符串，就可以实现压缩，实际上就是利用了信源符号之间的相关性。字符串与代号的对应表就是词典。 实用的词典编码算法的核心就是如何动态地形成词典，以及如何选择输出格式以减小冗余。 词典编码举例 词典法的想法是企图查找正在压缩的字符序列是否在以前输入的数据中出现过，然后用已经出现过的字符串替代重复的部分，它的输出仅仅是指向早期出现过的字符串的“指针”。 第5章 信源编码 2、费诺编码 1）步骤 A 将概率按从大到小的顺序排列 B 按编码进制数将概率分组，使每组概率和尽可能接近或相等。 C 给每组分配一位码元 D 将每一分组再按同样原则划分，重复b和c，直到概率不再可分为止 第5章 信源编码 2）编码过程 例、有离散无记忆信源[X]=[x1,x2,x3,x4,x5,x6],相应的概率矩阵为［P(X)］=[0.25 0.25,0.2,0.15 , 0.1, 0.05],对该信源进行二进制费诺编码。 第5章 信源编码 xi p(xi) ? ? ? ? 码字 X1 0.25 0 0 ? ? 00 X2 0.25 1 ? ? 01 X3 0.20 ? 1 0 ? ? 10 X4 0.15 1 0 ? 110 X5 0.10 1 0 1110 X6 0.05 1 1111 第5章 信源编码 H(X)=2.42bit/符号 L=0.25*2+0.25*2+0.20*2+0.15*3+0.10*4+0.05*4 =2.45bit/符号 η =98.77% 思考一下，什么时候可 以使编码效率高呢？ Huffman 编码就是利用变字长最佳编码实现信源符号按概率大小顺序排列。 第5章 信源编码 3、哈夫曼编码（Huffman) 第5章 信源编码 1）步骤 A 把信源符号按概率大小顺序排列， 并设法按逆次序分配码字的长度。 B 在分配码字长度时，首先将出现概率 最小的两个符号的概率相加合成一个概率 C 把这个合成概率看成是一个新组合符号地概率，重复上述做法直到最后只剩下两个符号概率为止。 D 完成以上概率顺序排列后，再反过来逐步向前进行编码，每一次有二个分支各赋予一个二进制码，可以对概率大的赋为零，概率小的赋为1。 2)编码过程 例、有离散无记忆信源[X]=[x1,x2,x3,x4,x5,x6, x7],相应的概率矩阵为［P(X)］=[0.2 0.19,0.18,0.17 , 0.15, 0.10，0.01],对该信源进行二进制哈夫曼编码。 第5章 信源编码 第5章 信源编码 x1 0.20 01 x2 0.19 00 x3 0.18 111 x4 0.17 110 x5 0.15 101 x6 0.10 1001 x7 0.01 1000 1 0 1 1 1 0 0 0.