信息论与编码第4无失真信源编码.ppt

《信息论与编码第4无失真信源编码.ppt》由会员分享，可在线阅读，更多相关《信息论与编码第4无失真信源编码.ppt（44页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、信息论与编码第4无失真信源编码 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第4章 编码类型（1）在不失真或允许一定失真条件下，如何提高信息传输速度，这种编码称为信源编码。根据是否允许失真，信源编码又可以分为无失真信源编码（当失真可以逼近于0时，在信息论中也当做无失真编码讨论）和限失真信源编码。（2）在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息的有效传输率最大，达到这种目的的编码称为信道编码。它是为了对抗信道中的噪音和衰减，通过增加冗余，如校

2、验码等，来提高抗干扰能力以及纠错能力。第4章 编码类型（3）在可以监听的信道上如何进行安全的通信，使得在信道上监听的人也无法获取消息，需要进行加密。对应的加密转换方法称为加密编码。4.1 编码器和相关概念为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。对于加密编码也是如此。简单地说，通信系统模型中的各种编码都是可选的，我们可以忽略其他编码，而专门讨论我们研究的那种编码。4.1.1 码的分类图4-1 信源编码器模型4.1.1 码的分类图4-2 码的分类

3、4.1.1 常用码的定义1.二元码和r元码,若码符号集为X=0;1，所有码字都是一些二元序列，则称为二元码（Binary Code）2.等长码,若一组码中所有码字的码长都相同，即li=l(i=1,2,q)，则称为等长码（定长码，fixed length code）3.变长码，若一组码组中所有码字的码长各不相同，则称为变长码（variable length codes）4.1.1 常用码的定义4.非奇异码，若一组码中所有码字都不相同，则称为非奇异码（nonsingular code，nonsigular code）5.奇异码，若一组码中有相同的码字，则称为奇异码。该码可能具有什么用途，又有什么缺

4、陷？6.唯一可译码7.非即时码和即时码8.分组码与非分组码4.1.2 码树对于给定码字的全体集合 C=W1,W2,Wq，可以用码树来描述。码树有助于研究唯一可译码的判别。图4-3 码树图4.1.3 Kraft不等式利用码树可以判断给定的码是否为惟一可译码，但需要画出码树。在实际中，我们可以利用克拉夫特（又译克劳夫特，Kraft）不等式，直接根据各码字的长度来判断惟一可译码是否存在，即各码字的长度应符合克拉夫特不等式：4.1.3 Kraft不等式 定理定理4-1 Kraft定理：对于码符号为X=x1,x2,xr的任意唯一可译码，其码字为W1,W2,Wq，所对应的码长为l1，l2，lq，则必定满足

5、克拉夫特不等式定理定理4-2 将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字，则可判断此码C为唯一可译码。4.2 定长编码定理4-3 定长（等长）编码定理：由L个符号组成的、每个符号熵为HL(X)的无记忆平稳信源符号序列X1X2X3XL用KL个符号Y1Y2YKL（每个符号有m中可能值）进行定长变码。对任意，只要则当L足够大时，必可使译码差错小于；反之，当 时，译码差错一定是有限值，当L足够大时，译码几乎必定出错。4.2 定长编码 4.2 定长编码例4-3设离散无记忆信源概率空间为信源熵为4.2 定长编码自信息方差为4.2 定长编码对信源符号采用定长二元编码，要求编码

6、效率，无记忆信源有因此可以得到如果要求译码错误概率，则由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。4.3 变长编码定理4-4 香农单符号变长编码定理：若离散无记忆信源的符号熵为H(S)，每个信源符号用r进制码元进行变长编码，一定存在一种无失真编码（唯一可译编码）方法，其码字的平均长度满足：4.3 变长编码定理4-5 香农离散平稳无记忆序列变长编码定理，即：若对信源离散无记忆信源S的N次扩展信源SN进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：4.3.1

7、 编码空间在信源编码的时候，我们可以如何使得编码最短，但是越短的编码，也容易造成唯一不可译。以异前缀编码为例，如果编的过短，会使得大量的码字不可用，如果较长，则影响不大。为了便于理解，我们这里提出一种新概念-编码空间。4.3.1 编码空间实际上它是一个相对量，是指一个编码占用的可以使用的编码的比例，考虑异前缀编码，显然一个二进制的编码，如果将0作为码字，所有以0开头的编码都不能再用，则有一半的编码将不能继续作为码字，如果是两位，则有四分之一的码字不能使用，对于十进制，一个一位的十进制占用的比例为十分之一，依此，一个n位的k进制占用的编码空间为1/kn，当占用的编码空间小于等于1的时候，异前缀码

8、是可能存在的，如果大于1，则不可能存在。4.3.2 香农码香农第一定理指出，选择每个码字的长度Ki满足下式的整数：logmpiKi1logmpi 例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 香农

9、码4.3.2 香农码以i=3为例，计算各符号的码字长度：K3=log0.2=3累加概率P4=0.7 0.10110 1014.3.2 香农码4.3.2 香农码香农编码给予你什么启示？香农编码中如何保证编码是异前缀的？香农编码何时可以达到无损压缩的理论极限？考虑有记忆和无记忆信源序列概率（概率和条件概率）分布具有平稳性，对单个符号进行本编码和对序列进行编码，编码的效率相比较如何？4.3.3 费诺码费诺码属于概率匹配编码，又称为香农-费诺码（Shannon-Fano编码），但它一般也不是最佳的编码方法。编码过程如下：(1)信源符号以概率递减的次序排列起来;(2)将排列好的信源符号按概率值划分成两大

10、组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号0和1;(3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予一个二元码符号;(4)依次下去，直至每个小组只剩一个信源符号为止;(5)信源符号所对应的码字即为费诺码。4.3.3 费诺码例4-6 对信源进行费诺编码表4-2是忽略了排序过程的编码，4-3排序。4.3.3 费诺码费诺码具有如下的性质：费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。费诺码不一定是最佳码。4.3.4 哈夫曼码哈夫曼编码的

11、步骤如下：统计信源消息符号的概率，将信源消息符号按其出现的概率大小依次排列p(u1)p(u2)p(un)取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队，合并后的信源称为缩减信源。对重排后的两个概率最小符号重复步骤的过程。不断继续上述过程，直到最后两个符号配以0和1为止。从最后一级开始，逆向向前返回得到各个信源符号所对应的码元序列，即相应的码字。例4-7 给定离散信源如下：例4-7 给定离散信源如下：4.4 其他实用基于统计的信源编码方法在编码理论的指导下，先后出现了许多性能优良的编码方法，本节介绍一些实用的统计编码方法。前面所

12、讨论的无失真编码，都是建立在信源符号与码字一一对应的基础上的，这种编码方法我们通常称为块码或分组码，此时信源符号一般应是多元的，而且不考虑信源符号之间的相关性。如果要对最常见的二元序列进行编码，则需采用游程编码或合并信源符号等方法，把二元序列转换成多值符号，转换后这些多值符号之间的相关性也是不予考虑的。这就使信源编码的匹配原则不能充分满足，编码效率一般就不高。为了克服这种局限性，就需要跳出分组码的范畴，研究非分组码的编码方法。下面要介绍的游程编码和算术编码即为非分组码。4.4.1 游程编码游程是指符号序列中各个符号连续重复出现而形成符号串的长度，又称游程长度或游长。游程编码(Run-Lengt

13、h Coding，简记RLC)就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。如果知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。4.4.2 算术编码在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推形式进行编码的方法。算术编码（Arithmetic Coding）跳出了分组编码的范畴，从全序列出发，采用递推形式的连续编码。4.4.2 算术编码算术编码的基本原理是将编码的消息表示成实数0和1之间的一个间隔（Interval），消息越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。1、算术码的主要

14、概念 2、累积概率4.4.2 算术编码图4-9信源符号序列的累积分布函数F(s)及其对应的区间4.4.2 算术编码4.5 通用编码哈夫曼编码与算术编码都要预先知道信源符号的概率分布。实际问题中往往无法知道或没有必要去统计信源各个符号的概率，希望有一种通用的非概率的编码方法。我们把这种不依靠概率知识就能进行压缩编码的方法叫做通用编码（Universal Coding）。由于通用，因而具有普遍适用性。它已经成为一种应用广泛的文件压缩技术。现已找到多种通用编码方法，如目前在计算机上常用的ZIP、RAR等。4.5.1 LZ77与LZSS编码LZ77和LZSS编码属于指针编码，其原理为：当待编字符串在早

15、先输出的数据流中已经出现过时，则不必重复输出，而用指向早先那个字符串（称为匹配字符串）的指针（指示匹配字符串的位置）来代替。LZ77算法原理为：所找到的最长的匹配字符串，用指针(x,y)来表示，并用它代替当前待编字符串。其中：x表示匹配字符串出现在当前待编字符串之前的位置（按字符个数计算)，y表示匹配字符串的长度。C表示当前待编字符串的下一个待编字符。因为当前匹配字符串再接上这个字符后，就成为前面找不到的字符串了。4.5.2 LZ78与LZW编码LZ78与LZW编码都属于字典编码。LZ78采用了一种完全不同的字典建立方案，取消了文本窗口，保留以前建立的字典，只有当新字符串出现时才将字符串加入字

16、典中。LZ78的编码方法是从空的字典开始，字典给每一个短语编号。读入字符，并在字典中搜索。输出搜索中发现的最长字符串的编号，然后紧接着输出未匹配的第一个字符，同时将发现的最长匹配字符和未匹配的第一个字符组成一个新短语并编入字典中，赋以新的编号，为下一个字符串编码做准备。4.5.3 常用压缩文件格式ZIP：ZIP文件格式是一种流行的数据压缩和文档储存的文件格式RAR：RAR是一种受专利保护的压缩文件格式，用于数据压缩与归档打包7z：7-Zip是一个开放源码的数据压缩程CAB：CAB是微软的一种安装文件压缩格式JAR：JAR文件就是Java Archive File，是Java的一种文档格式TAR：TAR为后辍的文件能用WinZip或WinRar打开我们致力于编写上达思想与方法，下及实现与应用的教材，但是力所不及，欢迎多提宝贵意见至http:/