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

第4章 无失真信源编码,前面的章节中，我们对信息问题从理论的角度进行了一些度量和分析。从本章开始，我们将讨论在信息论的基础上进行各种编码。 本章主要介绍编码的基本概念，信源编码的基本思路与主要方法，以无失真、统计编码为主，期望通过本章学习能建立起信源压缩编码的基本概念。,第4章 编码类型,（1）在不失真或允许一定失真条件下，如何提高信息传输速度，这种编码称为信源编码。根据是否允许失真，信源编码又可以分为无失真信源编码（当失真可以逼近于0时，在信息论中也当做无失真编码讨论）和限失真信源编码。 （2）在信道受到干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息的有效传输率最大，达到这种目的的编码称为信道编码。它是为了对抗信道中的噪音和衰减，通过增加冗余，如校验码等，来提高抗干扰能力以及纠错能力。,第4章 编码类型,（3）在可以监听的信道上如何进行安全的通信，使得在信道上监听的人也无法获取消息，需要进行加密。对应的加密转换方法称为加密编码。,4.1 编码器和相关概念,为了分析方便和突出问题的重点，当研究信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研究信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。对于加密编码也是如此。简单地说，通信系统模型中的各种编码都是可选的，我们可以忽略其他编码，而专门讨论我们研究的那种编码。,4.1.1 码的分类,图4-1 信源编码器模型,4.1.1 码的分类,图4-2 码的分类,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. 奇异码，若一组码中有相同的码字，则称为奇异码。该码可能具有什么用途，又有什么缺陷？ 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，则必定满足克拉夫特不等式 定理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 定长编码,对信源符号采用定长二元编码，要求编码效率，无记忆信源有 因此 可以得到 如果要求译码错误概率， 则 由此可见，在对编码效率和译码错误概率的要求不是十分苛刻的情况下，就需要个信源符号一起进行编码，这对存储和处理技术的要求太高，目前还无法实现。,4.3 变长编码,定理4-4 香农单符号变长编码定理：若离散无记忆信源的符号熵为H(S)，每个信源符号用r进制码元进行变长编码，一定存在一种无失真编码（唯一可译编码）方法，其码字的平均长度满足：,4.3 变长编码,定理4-5 香农离散平稳无记忆序列变长编码定理，即： 若对信源离散无记忆信源S的N次扩展信源SN进行编码，则总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：,4.3.1 编码空间,在信源编码的时候，我们可以如何使得编码最短，但是越短的编码，也容易造成唯一不可译。以异前缀编码为例，如果编的过短，会使得大量的码字不可用，如果较长，则影响不大。为了便于理解，我们这里提出一种新概念-编码空间。,4.3.1 编码空间,实际上它是一个相对量，是指一个编码占用的可以使用的编码的比例，考虑异前缀编码，显然一个二进制的编码，如果将0作为码字，所有以0开头的编码都不能再用，则有一半的编码将不能继续作为码字，如果是两位，则有四分之一的码字不能使用，对于十进制，一个一位的十进制占用的比例为十分之一，依此，一个n位的k进制占用的编码空间为1/kn，当占用的编码空间小于等于1的时候，异前缀码是可能存在的，如果大于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 香农码,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信源符号序列的累积分布函数F(s)及其对应的区间,4.4.2 算术编码,4.5 通用编码,哈夫曼编码与算术编码都要预先知道信源符号的概率分布。实际问题中往往无法知道或没有必要去统计信源各个符号的概率，希望有一种通用的非概率的编码方法。 我们把这种不依靠概率知识就能进行压缩编码的方法叫做通用编码（Universal Coding）。由于通用，因而具有普遍适用性。它已经成为一种应用广泛的文件压缩技术。现已找到多种通用编码方法，如目前在计算机上常用的ZIP、RAR等。,4.5.1 LZ77与LZSS编码,LZ77和LZSS编码属于指针编码，其原理为：当待编字符串在早先输出的数据流中已经出现过时，则不必重复输出，而用指向早先那个字符串（称为匹配字符串）的指针（指示匹配字符串的位置）来代替。 LZ77算法原理为：所找到的最长的匹配字符串，用指针(x, y)来表示，并用它代替当前待编字符串。其中：x表示匹配字符串出现在当前待编字符串之前的位置（按字符个数计算)，y表示匹配字符串的长度。C表示当前待编字符串的下一个待编字符。因为当前匹配字符串再接上这个字符后，就成为前面找不到的字符串了。,4.5.2 LZ78与LZW编码,LZ78与LZW编码都属于字典编码。 LZ78采用了一种完全不同的字典建立方案，取消了文本窗口，保留以前建立的字典，只有当新字符串出现时才将字符串加入字典中。 LZ78的编码方法是从空的字典开始，字典给每一个短语编号。读入字符，并在字典中搜索。输出搜索中发现的最长字符串的编号，然后紧接着输出未匹配的第一个字符，同时将发现的最长匹配字符和未匹配的第一个字符组成一个新短语并编入字典中，赋以新的编号，为下一个字符串编码做准备。,4.5.3 常用压缩文件格式,