信息论与编码无失真信源编码.pptVIP

4.3.2 香农码 香农第一定理指出，选择每个码字的长度Ki满足下式的整数： －logmpi≤Ki＜1－logmpi 例4-4设无记忆信源的概率空间为： 4.3.2 香农码 以二进制编码为例，香农编码方法如下： ⑴ 将信源消息符号按其出现的概率大小依次排列 p(u1)≥p(u2)≥…≥ p(un) ⑵ 确定码长Ki (整数) ： Mi= [ ] ——取整； Ki =Mi+1,如果 Mi是小数； Ki =Mi, 如果Mi是整数 ⑶ 为了编成唯一可译码，计算第i个消息的累加概率 4.3.2 香农码 ⑷ 将累加概率Pi变换成二进制数。 ⑸ 取pi二进制数的小数点后Ki位即为该消息符号的二进制数。 例4-5 对 信源进行香农编码。 4.3.2 香农码 4.3.2 香农码 以i=3为例，计算各符号的码字长度： K3=[－log0.2]=3 累加概率P4=0.7 —— 0.10110… —— 101 4.3.2 香农码 4.3.2 香农码 香农编码给予你什么启示？ 香农编码中如何保证编码是异前缀的？ 香农编码何时可以达到无损压缩的理论极限？ 考虑有记忆和无记忆信源序列概率（概率和条件概率）分布具有平稳性，对单个符号进行本编码和对序列进行编码，编码的效率相比较如何？ 4.3.3 费诺码 费诺码属于概率匹配编码，又称为香农-费诺码（Shannon-Fano编码），但它一般也不是最佳的编码方法。编码过程如下： (1)信源符号以概率递减的次序排列起来; (2)将排列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号0和1; (3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号; (4)依次下去，直至每个小组只剩一个信源符号为止; (5)信源符号所对应的码字即为费诺码。 4.3.3 费诺码 例4-6 对信源 进行费诺编码 表4-2是忽略了排序过程的编码，4-3排序。 4.3.3 费诺码 费诺码具有如下的性质： ①费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。 ②费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。 ③费诺码不一定是最佳码。 4.3.4 哈夫曼码 哈夫曼编码的步骤如下： ⑴ 统计信源消息符号的概率，将信源消息符号按其出现的概率大小依次排列 p(u1)≥p(u2)≥…≥p(un) ⑵ 取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队，合并后的信源称为缩减信源。 ⑶ 对重排后的两个概率最小符号重复步骤⑵的过程。 ⑷ 不断继续上述过程，直到最后两个符号配以0和1为止。 ⑸ 从最后一级开始，逆向向前返回得到各个信源符号所对应的码元序列，即相应的码字。 例4-7 给定离散信源如下： 例4-7 给定离散信源如下： 4.4 其他实用基于统计的信源编码方法 在编码理论的指导下，先后出现了许多性能优良的编码方法，本节介绍一些实用的统计编码方法。前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上的，这种编码方法我们通常称为块码或分组码，此时信源符号一般应是多元的，而且不考虑信源符号之间的相关性。如果要对最常见的二元序列进行编码，则需采用游程编码或合并信源符号等方法，把二元序列转换成多值符号，转换后这些多值符号之间的相关性也是不予考虑的。这就使信源编码的匹配原则不能充分满足，编码效率一般就不高。为了克服这种局限性，就需要跳出分组码的范畴，研究非分组码的编码方法。下面要介绍的游程编码和算术编码即为非分组码。 4.4.1 游程编码 游程是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度或游长。 游程编码(Run-Length Coding，简记RLC)就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。 4.4.2 算术编码 在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推形式进行编码的方法。算术编码（Arithmetic Coding）跳出了分组编码的范畴，从全序列出发，采用递推形式的连续编码。 4.4.2 算术编码 算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔（Interval），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 1、算术码的主要概念 2、累积概率 4.4.2 算术编码 图4-9信源符