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

1、第4章 无失真信源编码前面的章节中，我们对信息问题从实际的角度进展了一些度量和分析。从本章开场，我们将讨论在信息论的根底上进展各种编码。 本章主要引见编码的根本概念，信源编码的根本思绪与主要方法，以无失真、统计编码为主，期望经过本章学习能建立起信源紧缩编码的根本概念。 学习得来终觉浅，绝知此事要自悟第4章 编码类型 1在不失真或允许一定失真条件下，如何提高信息传输速度，这种编码称为信源编码。根据能否允许失真，信源编码又可以分为无失真信源编码当失真可以逼近于0时，在信息论中也当做无失真编码讨论和限失真信源编码。 2在信道遭到干扰的情况下，如何添加信号的抗干扰才干，同时又使得信息的有效传输率最大，

2、到达这种目的的编码称为信道编码。它是为了对抗信道中的噪音和衰减，经过添加冗余，如校验码等，来提高抗干扰才干以及纠错才干。第4章 编码类型 3在可以监听的信道上如何进展平安的通讯，使得在信道上监听的人也无法获取音讯，需求进展加密。对应的加密转换方法称为加密编码。4.1 编码器和相关概念为了分析方便和突出问题的重点，当研讨信源编码时，我们把信道编码和译码看成是信道的一部分，从而突出信源编码。同样，在研讨信道编码时，可以将信源编码和译码看成是信源和信宿的一部分，从而突出信道编码。对于加密编码也是如此。简单地说，通讯系统模型中的各种编码都是可选的，我们可以忽略其他编码，而专门讨论我们研讨的那种编码。4

3、.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 codes4.1.1 常用码的定义 4. 非奇特码，假设一组码中一切码

4、字都不一样，那么称为非奇特码nonsingular code，nonsigular code 5. 奇特码，假设一组码中有一样的码字，那么称为奇特码。该码能够具有什么用途，又有什么缺陷？ 6. 独一可译码 7. 非即时码和即时码 8.分组码与非分组码4.1.2 码树对于给定码字的全体集合 C=W1,W2,Wq，可以用码树来描画。码树有助于研讨独一可译码的判别。图4-3 码树图4.1.3 Kraft不等式利用码树可以判别给定的码能否为独一可译码，但需求画出码树。在实践中，我们可以利用克拉夫特又译克劳夫特，Kraft不等式，直接根据各码字的长度来判别独一可译码能否存在，即各码字的长度应符合克拉夫特

5、不等式：11qilir4.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足够大时，必可使译码过失小于；反之，当 时，译码过失一定是有限

6、值，当L足够大时，译码几乎必定出错。2)(logXHmLKLL4.2 定长编码 4.2 定长编码 例4-3设离散无记忆信源概率空间为 信源熵为04. 005. 006. 007. 01 . 01 . 018. 04 . 087654321xxxxxxxxPX符号/55. 2log)(812bitppXHiii4.2 定长编码 自信息方差为82. 7)()(log)(log)(2)(log)(log)(2)(log)(log)()()(812228181812222812222812222iiiiiiiiiiiiiiiiiiiXHpppXHppXHppXHpXHppXHppXHxIEX4.2 定

7、长编码 对信源符号采用定长二元编码，要求编码效率，无记忆信源有 因此 可以得到 假设要求译码错误概率， 那么 由此可见，在对编码效率和译码错误概率的要求不是非常苛刻的情况下，就需求个信源符号一同进展编码，这对存储和处置技术的要求太高，目前还无法实现。)()(XHXHL%90)()(XHXH28. 0610872210108 . 9(）XL4.3 变长编码 定理4-4 香农单符号变长编码定理：假设离散无记忆信源的符号熵为H(S)，每个信源符号用r进制码元进展变长编码，一定存在一种无失真编码独一可译编码方法，其码字的平均长度满足：rH(S)LrH(S)log1log4.3 变长编码 定理4-5 香

8、农离散平稳无记忆序列变长编码定理，即： 假设对信源离散无记忆信源S的N次扩展信源SN进展编码，那么总可以找到一种编码方法，构成独一可译码，使信源S中每个信源符号所需的平均码长满足：( )1( )loglogNLH SH SrNNr4.3.1 编码空间 在信源编码的时候，我们可以如何使得编码最短，但是越短的编码，也容易呵斥独一不可译。以异前缀编码为例，假设编的过短，会使得大量的码字不可用，假设较长，那么影响不大。为了便于了解，我们这里提出一种新概念-编码空间。4.3.1 编码空间 实践上它是一个相对量，是指一个编码占用的可以运用的编码的比例，思索异前缀编码，显然一个二进制的编码，假设将0作为码字

9、，一切以0开头的编码都不能再用，那么有一半的编码将不能继续作为码字，假设是两位，那么有四分之一的码字不能运用，对于十进制，一个一位的十进制占用的比例为非常之一，依此，一个n位的k进制占用的编码空间为1/kn，当占用的编码空间小于等于1的时候，异前缀码是能够存在的，假设大于1，那么不能够存在。4.3.2 香农码 香农第一定理指出，选择每个码字的长度Ki满足下式的整数：logmpiKi1logmpi 例4-4设无记忆信源的概率空间为：81814121)(4321uuuuupU4.3.2 香农码以二进制编码为例，香农编码方法如下： 将信源音讯符号按其出现的概率大小依次陈列 p(u1)p(u2) p(

10、un) 确定码长Ki (整数) ： Mi= 取整；Ki =Mi+1,假设 Mi是小数； Ki =Mi, 假设Mi是整数 为了编成独一可译码，计算第i个音讯的累加概率 ip1log11)(ikkiupp4.3.2 香农码 将累加概率Pi变换成二进制数。 取pi二进制数的小数点后Ki位即为该音讯符号的二进制数。 例4-5 对信源进展香农编码。05. 005. 02 . 03 . 04 . 0)(54321uuuuuupU4.3.2 香农码4.3.2 香农码 以i=3为例，计算各符号的码字长度： K3=log0.2=3 累加概率P4=0.7 0.10110 1014.3.2 香农码4.3.2 香农码

11、 香农编码给予他什么启示？ 香农编码中如何保证编码是异前缀的？ 香农编码何时可以到达无损紧缩的实际极限？ 思索有记忆和无记忆信源序列概率概率和条件概率分布具有平稳性，对单个符号进展本编码和对序列进展编码，编码的效率相比较如何？4.3.3 费诺码 费诺码属于概率匹配编码，又称为香农-费诺码Shannon-Fano编码，但它普通也不是最正确的编码方法。编码过程如下：(1)信源符号以概率递减的次序陈列起来;(2)将陈列好的信源符号按概率值划分成两大组，使每组的概率之和接近于相等，并对每组各赋予一个二元码符号0和1;(3)将每一大组的信源符号再分成两组，使划分后的两个组的概率之和接近于相等，再分别赋予

12、一个二元码符号;(4)依次下去，直至每个小组只剩一个信源符号为止;(5)信源符号所对应的码字即为费诺码。4.3.3 费诺码 例4-6 对信源进展费诺编码 表4-2是忽略了排序过程的编码，4-3排序。05. 005. 02 . 03 . 04 . 0)(54321uuuuuupU4.3.3 费诺码费诺码具有如下的性质：费诺码的编码方法实践上是一种构造码树的方法，所以费诺码是即时码。费诺码思索了信源的统计特性，使概率大的信源符号能对应码长较短的码字，从而有效地提高了编码效率。费诺码不一定是最正确码。4.3.4 哈夫曼码哈夫曼编码的步骤如下： 统计信源音讯符号的概率，将信源音讯符号按其出现的概率大小

13、依次陈列p(u1)p(u2)p(un) 取两个概率最小的字母分别配以0和1两码元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队，合并后的信源称为缩减信源。 对重排后的两个概率最小符号反复步骤的过程。 不断继续上述过程，直到最后两个符号配以0和1为止。 从最后一级开场，逆向向前前往得到各个信源符号所对应的码元序列，即相应的码字。 例4-7 给定离散信源如下：01. 010. 015. 017. 018. 019. 020. 0)(7654321uuuuuuuupU 例4-7 给定离散信源如下：01. 010. 015. 017. 018. 019. 020. 0)(7

14、654321uuuuuuuupU4.4 其他适用基于统计的信源编码方法 在编码实际的指点下，先后出现了许多性能优良的编码方法，本节引见一些适用的统计编码方法。前面所讨论的无失真编码，都是建立在信源符号与码字一一对应的根底上的，这种编码方法我们通常称为块码或分组码，此时信源符号普通应是多元的，而且不思索信源符号之间的相关性。假设要对最常见的二元序列进展编码，那么需采用游程编码或合并信源符号等方法，把二元序列转换成多值符号，转换后这些多值符号之间的相关性也是不予思索的。这就使信源编码的匹配原那么不能充分满足，编码效率普通就不高。为了抑制这种局限性，就需求跳出分组码的范畴，研讨非分组码的编码方法。下

15、面要引见的游程编码和算术编码即为非分组码。4.4.1 游程编码游程是指符号序列中各个符号延续反复出现而构成符号串的长度，又称游程长度或游长。游程编码(Run-Length Coding，简记RLC)就是将这种符号序列映射成游程长度和对应符号序列的位置的标志序列。假设知道了游程长度和对应符号序列的位置的标志序列，就可以完全恢复出原来的符号序列。4.4.2 算术编码 在算术编码中，信源符号和码字间的一一对应关系并不存在，它是一种从整个符号序列出发，采用递推方式进展编码的方法。算术编码Arithmetic Coding跳出了分组编码的范畴，从全序列出发，采用递推方式的延续编码。4.4.2 算术编码算

16、术编码的根本原理是将编码的音讯表示成实数0和1之间的一个间隔Interval，音讯越长，编码表示它的间隔就越小，表示这一间隔所需的二进制位就越多。 1、算术码的主要概念 2、累积概率4.4.2 算术编码图4-9信源符号序列的累积分布函数F(s)及其对应的区间4.4.2 算术编码4.5 通用编码哈夫曼编码与算术编码都要预先知道信源符号的概率分布。实践问题中往往无法知道或没有必要去统计信源各个符号的概率，希望有一种通用的非概率的编码方法。我们把这种不依托概率知识就能进展紧缩编码的方法叫做通用编码Universal Coding。由于通用，因此具有普遍适用性。它曾经成为一种运用广泛的文件紧缩技术。现

17、已找到多种通用编码方法，如目前在计算机上常用的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 常用紧缩文件格式 ZIP：ZIP文件格式是一种流行的数据紧缩和文档储存