《信息论基础续5》由会员分享，可在线阅读，更多相关《信息论基础续5（50页珍藏版）》请在金锄头文库上搜索。
1、Source Coding定定定长长长无无无失失失真真真信信信源源源编编编码码码定定定理理理定长无失真信源编码定理 I对于信源来说有两个基本问题：如何计算信源输出的信息量；如何有效地表示信源输出，即在不失真或允许一定失真地条件下，如何用尽可能少地符号来表示信源，以便提高信息传输率。编码实质上是对信源地原始符号按照一定地数学规则进行地一种变换。将信源符号集合中的 si（或者长为 N 的信源符号序列）变换成由 xj组成的长度为 li的一一对应的码符号序列 Wi。编码的一些基本概念这种码符号序列 Wi称为码码码字字字；长度 li称为码码码字字字长长长度度度，简称码码码长长长；全体码字的集合 C 称为
2、码码码。若码符号集合为 X = 0,1，则所得的码字都是二元序列，称为二二二元元元码码码。8Source Coding定定定长长长无无无失失失真真真信信信源源源编编编码码码定定定理理理定长无失真信源编码定理 II若一个码中所有码字的码长都相等，则称为等等等长长长码码码；否则为变变变长长长码码码。若一个码中无重复码字，则称为非非非奇奇奇异异异码码码；否则为奇奇奇异异异码码码。若码符号集合中每个码符号所占的传输时间都相同，则所得的码称为同同同价价价码码码。若任意一串有限长的码符号序列只能被唯一地译为对应的信源符号序列，则称此码为唯唯唯一一一可可可译译译码码码。若某个唯一可译码在译码时无需参考后续的
3、码符号就能立即作出判断，将码符号序列译成相应的信源符号序列。则称此码为即即即时时时码码码，即时码又称为逗逗逗点点点码码码、非非非延延延长长长码码码。9Source Coding定定定长长长无无无失失失真真真信信信源源源编编编码码码定定定理理理定长无失真信源编码定理 III定理设熵率为 H(S) 的离散无记忆信源产生的信源符号序列被分为长为 N 的源符号组，并用长为 M 的码字组进行编码，码符号表的大小为 r，则 0 和 0，当 N 足够大，并且 M 满足： M logr/N H(S) + ，则源符号组没有自己特定码字组的概率可以小于 。对于恒稳遍历信源可以得到类似的结果。改写上述定理的条件：M
4、 logr N H(S)，即只要 M 个码字所能传输的最大信息量大于 N 长信源符号序列所携带的信息量，就可以实现几乎无失真编码。10Source Coding定定定长长长无无无失失失真真真信信信源源源编编编码码码定定定理理理定长无失真信源编码定理 IV定义R = M logr/N 为编编编码码码速速速率率率； = H(S)/R 为编编编码码码效效效率率率。根据上述定理，最佳编码效率为：= H(S)/(H(S) + )。 为允许的编码错误概率上限。因此在已知自信息方差和信源熵的条件下，信源符号序列长度 N 与最佳编码效率和允许编码错误概率之间的关系为：N DI(si) 2/H2(S) (1 )
5、2 定长编码在实际应用中存在两个问题：编译码同步的问题；如何均衡分组长度、编译码复杂性、编译码延时和差错概率之间的关系。11Source Coding无无无失失失真真真变变变长长长编编编码码码无失真变长编码 I当使用等概的码符号序列对信源符号序列进行定长编码时，为了使编码有效，信源符号序列的长度必须很大才行。这在实际应用中很难实现。为了解决这一难题，可以采用可变长度的码符号序列去适应不同概率的信源符号（序列）。最典型的变长编码的例子就是电报中使用的 Morse 码：AJ SBK TC L U D MVENW F O X G P Y HQ Z IR 12Source Coding无无无失失失真真
6、真变变变长长长编编编码码码无失真变长编码 II上表给出了 Morse 码的一部分。Morse 码实际上是一个三元码，具有点、划和间隔三种符号。划所对应的时间长度是点所对应的时间长度的三倍。在一个字母中点和划之间的时间间隔是一个时间单位，在字母之间是三个时间单位，而在单词之间是七个时间单位。13Source Coding无无无失失失真真真变变变长长长编编编码码码Kraft 不不不等等等式式式Kraft 不等式 I在唯一可译码中，即时码显然要比非即时码要好。下面的Kraft 定理给出了即时码存在的充要条件。定理 (Kraft 定理)设含有 q 个信源符号的信源要用 r 个符号的码符号表进行变长编码
7、，则当且仅当各码字的长度 l1,l2,.,lq满足 Kraft 不等式qXi=1rli6 1(5)时才存在即时码。14Source Coding无无无失失失真真真变变变长长长编编编码码码Kraft 不不不等等等式式式Kraft 不等式 IIKraft 给出的限制也是所有唯一可译码都必须满足的：定理唯一可译码存在的充要条件为：qXi=1rli6 1(6)上述两个定理都是存存存在在在性性性定理。即时码的一种简单的构造方法是树树树图图图法法法，既用一棵码码码树树树来表示一个码。15Source Coding无无无失失失真真真变变变长长长编编编码码码Kraft 不不不等等等式式式Kraft 不等式 I
8、II码树最上面的节点称为根根根节节节点点点，每个节点伸出来的树枝的数目不大于码符号的个数。树枝的另一头为子节点。没有子节点的节点称为 叶叶叶子子子节节节点点点，其它的节点称为中中中间间间节节节点点点。每个中间节点（包括根节点）都有 r 个子节点的树称为整整整树树树，某个节点到根节点所经过的树枝数称为此节点的深深深度度度，所有叶子节点的深度都相同的整树称为完完完全全全树树树。若将一棵完全树的叶子节点都安排为码字，那么就会得到一个等长码。若所有的码字都安排在叶子节点上，则相应的变长码为即时码。16Source Coding无无无失失失真真真变变变长长长编编编码码码唯唯唯一一一可可可译译译码码码判判
9、判决决决准准准则则则唯一可译码判决准则 I非奇异的等长码一定是唯一可译码。如果一个变长码不满足 Kraft 不等式，则它一定不是唯一可译码。但是满足 Kraft 不等式的变长码不一定是唯一可译码。为此，A.A. Sardinas 和 G.W.Patterson 于1957年提出下述算法用于判断码 C 的唯一可译性。此算法的原理如下图所示：A1A2A3.Am1AmB1B2B3.Bn1Bn17Source Coding无无无失失失真真真变变变长长长编编编码码码唯唯唯一一一可可可译译译码码码判判判决决决准准准则则则唯一可译码判决准则 II其中 Ai,Bi都是码字。由上图可知，当且仅当某个有限长的码符
10、号序列能译成两种不同的码字序列时，此码不是唯一可译码，此时 B1一定是 A1的前缀，而 A1的尾随后缀一定是另一码字 B2的前缀；而 B2的尾随后缀又是其它码字的前缀。最后，码符号序列的尾部一定是一个码字。设 C 为码字集合，按以下步骤构造此码的尾随后缀集合 F：1考查 C 中所有的码字，若 Wi是 Wj的前缀，则将相应的后缀作为一个尾随后缀码放入集合 F0中；2考查 C 和 Fi两个集合，若 Wi C 是 Wj Fi的前缀或Wi Fi是 Wj C 的前缀，则将相应的后缀作为尾随后缀码放入集合 Fi+1中；3F =SiFi即为码 C 的尾随后缀集合；18Source Coding无无无失失失真
11、真真变变变长长长编编编码码码唯唯唯一一一可可可译译译码码码判判判决决决准准准则则则唯一可译码判决准则 III4若 F 中出现了 C 中的元素，则算法终止，返回假（C 不是唯一可译码）；否则若 F 中没有出现新的元素（即最后一个 Fi为空），则返回真。19Source Coding变变变长长长信信信源源源编编编码码码定定定理理理变长信源编码定理 I由上一节讨论可知，对于已知信源 S 可以用码符号 X 进行变长编码，而且对同一信源可以得到多种即时码。究竟哪一种最好呢？定义码的平平平均均均码码码长长长定义为码长的数学期望：LM=qXi=1p(si)li(7)L 的单位为码码码符符符号号号/信信信源源
12、源符符符号号号。20Source Coding变变变长长长信信信源源源编编编码码码定定定理理理变长信源编码定理 II定义编码后平均每个码符号所携带的信息量称为编码后信道的信信信息息息传传传输输输率率率：RM= H(X) =H(S)L(8)定义对于某一信源来说，若存在一个唯一可译码，其平均码长 L小于所有其他唯一可译码的平均码长，则该码称为紧紧紧致致致码码码，或最最最佳佳佳码码码。21Source Coding变变变长长长信信信源源源编编编码码码定定定理理理变长信源编码定理 III定理离散信源 S 的熵为 H(S)，用 r 个码符号对其进行编码，则总可以找到一种编码方法构成唯一可译码，使其平均码
13、长满足：H(S)logr+ 1 L H(S)logr(9)根据 Kraft 定理我们知道只要满足 Kraft 不等式，就一定能够通过树图法构造一个即时码。现在的问题是找到具有最小平均码长的即时码。上述问题可等效为在满足Prli6 1 的条件下寻找一组最佳的 l1,l2,.,lq，使得 L =Ppili达到极小值。22Source Coding变变变长长长信信信源源源编编编码码码定定定理理理变长信源编码定理 IV应用 Lagrange 乘数法可求出：li= logrpi。又因为所有的码长都应该是整数，所以有：logrpi6 liLNNH(S)logr(10)23Source Coding无无无失
14、失失真真真信信信源源源编编编码码码技技技术术术无失真信源编码技术Huffman 编码Shannon 编码Shannon-Fano-Elias 编码Fano 编码算数编码游程编码通用编码24Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码算算算法法法Huffman 编码算法Huffman 编码可以得到最佳码。其具体的算法如下：procedure Huffman:input: 符号 s0,.,sq1，概率 p0,.,pq1output: 从 s0,s1,.,sq1到码字的映射if q = 2;返回编码：s07 0, s17 1else重新
15、排序 s0,.,sq1和 p0,.,pq1创建一个符号 s0，其概率为 p0= pq2+ pq1递归调用 Huffman 以得到 s0,.,sq3,s0的编码w0,.,wq3,w0，相的概率分布为 p0,.,pq3,p0返回编码：s07 w0,.,sq37 wq3, sq27 w00,sq17 w0125Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Shannon 编编编码码码算算算法法法Shannon 编码算法1将信源符号按其概率降序排序2计算 dlogrpie 得到相应的码长 li3计算第 i 个信源符号的累加概率：Pi=i1Pk=1pk4将累加概率变为
16、r 进制小数5取小数点后 li位作为码字输出26Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Shannon-Fano-Elias 编编编码码码算算算法法法Shannon-Fano-Elias 编码算法1计算 dlogrpie + 1 得到相应的码长 li2计算第 i 个信源符号的修正累加概率：Pi=i1Pk=1pk+12pi3将累加概率变为 r 进制小数4取小数点后 li位作为码字输出27Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Fano 编编编码码码算算算法法法Fano 编码算法1将信源符号按其概率降序排序2求取 k，
17、使得?kPi=1piqPi=k+1pi?取得最小值，即在位置 k 将信源符号分为两个子集，其概率和最为接近3为两个子集分别分配码符号 0 和 14对两个子集递归28Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 I加权码字的 Huffman 编码：Huffman 算法可以用于任意的pi 0 的集合，而不要求Pipi= 1。在这种情况下，Huffman 编码可以得到最小的加权码长和Piwili而不是平均码长。信源编码和“20问游戏”：假设我们需要设计一个最有效的问题序列用以在
18、一组对象中找到某个特定的对象。我们应该如何去设计这个问题序列？假定对任何问题的回答都只可能是Yes/No。首先，一个问题序列和一个对对象的编码是等效的。每个问题仅仅依赖于前一个问题的答案，而答案的序列唯一地确定一个对象，并且每个对象都对应一个不同的答案序列。如果29Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 II我们将 Yes/No 分别对应0和1，则相应的解答过程就构成了一棵二叉树，每个码字对应一个对象，平均码长对应问题的平均数目。通过对对象进行二进制 Huffman
19、 编码，我们可以解决上述问题。Huffman 编码和“分片”问题：在“20问游戏”中 Huffman 编码相当于下列形式的任意问题：X A 吗？其中A 1,2,.,q现在我们进一步限制：对象集合已经排好序，并且问题只能是“ X a 吗？” 这种形式。则 Huffman 编码无法解决这种问题。而上述的 Fano 编码算法正好是一个“分片”算法。30Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 IIIHuffman 编码和 Shannon 编码：针对某些特定的分布，采用llo
20、g1pim作为码长将比 Huffman 编码方案差很多。Example考虑拥有两个信源符号的信源，其概率分布为：(0.9999,0.0001)。采用 Shannon 编码算法将为第二个信源符号选择 14 作为码长，而 Huffman 编码算法对两个信源符号都使用 1bit 进行编码。31Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 IV对一个最佳码来说，是否每个信源符号对应的码长都小于llog1pim？答案是否定的。Example考虑这样一个信源：(13,13,14,11
21、2)，对其进行 Huffman 编码可得到这样的码长分布：(2,2,2,2) 或(1,2,3,3)。这两种码长分布得到相同的平均码长，但是在第二个编码方案中第三个码长为3 dlog4e。32Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 Vr 元 Huffman 编码：为了最有效地利用较短码长的码字，在编码前应该通过添加概率为零的信源符号来调整信源符号的个数 q，使其满足：r = q k(r 1)，其中 k 为任意整数。Lemma对于任意的信源分布，必然存在一个最佳的即时码
22、具有以下性质：1如果 pj pk，则有 lj6 lk；2最长的两个码字具有相同的码长；3最长的两个码字分布对应概率最小的两个信源符号且它们之间只有最后的那个比特不同。33Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术Huffman 编编编码码码的的的几几几个个个问问问题题题Huffman 编码的几个问题 VILemma如果某个缩减信源的紧致码为 C0，将 C0中由原信源中的概率最小的两个信源符号缩减得到的新信源符号所对应的码字后各加0和1，作为原信源的最小概率的两个码字，而其余码字不变，则这样得到的码 C 对原信源也是紧致码。定理Huffman 编码是紧致码。
23、34Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术算算算数数数编编编码码码算数编码 I对于符号表很小的信源来说，只有当我们采用较长的分组长度时才能得到较高的编码效率。因此我们需要一个有效的算法来处理较长的信源符号序列，Huffman 编码在这方面作的不够好，因为它必须预先计算所有可能的信源符号序列的概率，然后才能进行编码。从 Shannon-Fano-Elias 编码算法直接扩展而得到的算数编码算法能够解决这个问题。算数编码算法的中心思想是高效地计算 n 长信源符号序列 x的分布概率 p(x) 和累积概率 F(x) 。然后用区间(F(x) p(x),F(x)
24、中的一个值来作为 x 的码字。35Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术算算算数数数编编编码码码算数编码 II假定信源是二进制的，并且分组的长度 n 已知。定义两个 n 长信源符号序列 x 和 y ，定义 x 大大大于于于 y ，当第一个使得xi6= yi的 i 有 xi= 1,yi= 0。我们可将上述信源符号序列安排为一棵深度为 n 的树上的叶子节点。并使得 x y 对应着 x 在 y 的右边。根据累积概率的定义，我们需要计算 x 节点左侧所有叶子节点的概率。所有这些概率的和等于 x 节点左侧所有子树的概率和。36Source Coding无无无失失
25、失真真真信信信源源源编编编码码码技技技术术术游游游程程程编编编码码码游程编码 I我们从一个例子着手。这里有一幅 10 50 的图片。如果我们分别用0和1给白色和黑色的点编码，那么这幅图片总共需要500个比特才能无失真地编码。通过观察，我们发现白点的数目比黑点多，并且无论是黑点还是白点都经常连续地出现。我们将一个连续的同色点序列称为一个游游游程程程。37Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术游游游程程程编编编码码码游程编码 II也许我们可以通过将整个游程用一个字节进行编码来提高效率。即用每个字节的第一个比特表示点的颜色，剩下的7个比特表示游程的长度（0到
26、127）。在这种方案下，一个127点长的白色游程只需8个比特来表示，压缩率为127/8 = 15.9 。对本例而言，总共有55个白游程以及54个黑游程，每个游程的长度都不超过127，所以总共需要 8 (55 + 54) = 872 个比特。不仅没有达到压缩的效果，数据量反而增加了。幸运的是，上述方案还有许多值得改进的地方。首先，黑游程和白游程一定是交替出现的，所以我们只需给第一个游程的颜色进行编码，而不必为每一个后续游程的颜色都进行编码。此时共需要 1 + 7 (55 + 54) = 764 比特。38Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术游游游程程程
27、编编编码码码游程编码 III其次，尽管上述方案对长度较大的游程有很高的压缩比，但是对长度很小的游程就显得不那么好了。解决的方法之一是减少用于表示游程长度的比特数。经过计算，当用3个比特表示游程长度(07)时，最后需要459个比特，压缩率大约为8%。第三，我们注意到在本例中白游程普遍要比黑游程长，因此可以考虑用不同的比特数分别编码。第四，码字序列 011000010 实际上表示的是5个连续的白点，而5 个连续的白点将由码字 101 来表示，因此编码器永远不会产生上述序列，所以我们浪费了很多码字。39Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编
28、码码码通用编码 I对于统计特性已知的平稳信源，霍夫曼码和算术码的编码效率已非常高，而且实现也不算太困难，所以已经进入实用。在信源统计特性不知道时就需要用到具有自适应能力的通用编码方法。LZW 码就是一种高效的通用编码。它是由以色列的 J.Ziv 和 A.Lempel 于1977年提出的，并由 T.Welch于1984年进行了改进。现在已成为计算机文件压缩的标准算法，我们常用的 ZIP、ARC 压缩解压程序就是 LZW 码的改进算法。LZW 码也称基于字典的编码方法，它是定长码。LZW 编码算法是一种分段编码。40Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通
29、通通用用用编编编码码码通用编码 II计算机文件是以字节为单位组成的，每个字节的取值从0到255，将每个字节都看成字符，则共256种字符；再把连续的若干个“字符”看成是一个“单词”，全部字符、单词及它们对应的序号（码字）组成字典。编码时，把字符、单词用对应的码字来代替。通常序号（码字）的长度为12比特（即字典的容量为4096），而“单词”的平均长度远大于12比特，从而达到压缩的目的。例如在一个文件中，有一个片段的内容为“ABCD空空空空空20000”共14个字节，长度为112比特，编码是被分割成4个单词，即“ABCD”。“空空空空空”、“ 2”和“0000”，编码长度为48比特，则压缩比为2.3
30、3。41Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 IIILZW 码是一种自适应变码，它的字典是直接由被压缩文件在编码过程中生成的。一边编码，一边生成字典。在译码的过程中，同样是一边译码，一边生成字典。字典的构成字典的容量为4096（04095）。序号用12比特表示。最后一个单词（第4095个单词）为空。42Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 IV为了使字典中长短不一的单词具有同样的结构，便于处理，对单词进行了格式转换。每个单词由前缀字符串和尾字符
31、两部分组成。其中前缀字符串是字典中已经存在的某个单词，用序号表示，尾字符是本单词的最后一个字符。比如，单词ABC可以变换成“100C”假定AB这个单词在字典中已经存在，且序号为 100，这样，任何单词的内容都可以用三个字节表式：其中两个字节表示前缀单词的序号，一个字节为尾字符。单个字符构成的单词的前缀为空。将压缩文件恢复为原始文件（解压缩）时，根据单词的这种格式，使用递归算法来恢复单词的内容。算法43Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 V1字字字典典典初初初始始始化化化：将被压缩文件中所有使用到的单字节字符放入字典中
32、，为了压缩任何类型的文件，可以将字典的前256个位置（0x000 到 0x 0FF）依次分配给 0x00 到 0xFF 的256个单字节字符。2动动动态态态数数数据据据初初初始始始化化化：初始化新单词存放位置指针 P。将它指向字典的第一个空位置。例如 P = 256（即 0x100），读入被压缩文件的第一个字符 c1，作为待处理单词 W。单词的前缀 Q 为空，即 Q = 4095 ，尾字符就是 c1，序号（码字）就是 c1的序号。3如果文件再没有字符了，输出当前单词 W 的序号，编码结束。如果文件中还有字符，把当前单词 W 作为前缀，再从被压缩文件中读入一个字符 c1，把 c1作为尾字符，得到
33、一个单词 W1。44Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 VI4如果字典中已有 W1，则将 W1看作当前单词 W，返回第三步。如果字典中没有 W1（发现一个新单词），先将原单词W 的序号输出，再加新单词 W1，增加到字典中，然后把刚刚读入的字符 c1作为当前单词 W，返回第三步。例例例： 信源符号序列为 ABCABDABCAAAABBBABCABCA步骤读入字符尾字符码字查找对象新单词输出码字0A1BA041AB1000412CB042BC1010423AC043CA1020434BA041AB5DB100ABD103
34、10045Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 VII6AD044DA1040447BA041AB8CB100ABC1051009AC043CA10AA102CAA10610211AA041AA10704112AA041AA13BA107AAB10810714BB042BB10904215BB042BB16AB109BBA10A10517BA041AB18CB100ABC46Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 VIII19AC105ABCA1
35、0B10520BA041AB21CB100ABC22AC105ABCA23A10B10B47Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 IX最后增加一个码字FFF表示编码结束。原始信源符号序列共23个字符，编码后共14个码字，每个码字12比特，压缩率为 23 8/14 12 = 1.095，并不理想。因为在压缩编码初期，由于字典中的单词很少，字典对压缩效果的贡献也很少，主要是进行字典的扩充工作，经过一段时间的积累，字典内容比较丰富后，对压缩效果的贡献就会体现出来。所以 LZW 算法不适合小文件的压缩。另外，由于字典容量有限，
36、当文件很大时，压缩效率也将受到限制。本算法适合内容有明显单词结构的文件（如文本文件、程序文件）。译码48Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 X1字典初始化：将字典的前256个位置（0x000 到 0x0FF）依次分配给 0x00 到 0xFF 这256个单字节字符。2动态数据初始化：初始化新单词存放于位置指针 P，将它指向字典的第一个空位置，例如 P = 256（即 0x100），读入压缩文件的第一个码字，由于第一个码字必定是一个单字符，可以从初始字典中查表得到，译码输出，并记忆它的码字。3如果压缩中已经没有码字，解
37、码结束。否则继续读入下一个码字。4如果读入的码字是无效码字 FFF。则解码结束，否则进入下一步。49Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 XI5如果在字典中已经有该码字对应的单词，则采用递归算法，输出该单词的内容。并将单词的第一个有效字符作为尾字符，将已经记忆的前一个码字作为前缀，组成一个新单词，写入字典中，然后将当前码字记忆下来，返回第三步；否则，首先在字典中生成新的单词，然后再输出这个单词，将新单词的码字记忆下来，返回第三步。这时的新单词一定是首尾相同的单词。50Source Coding无无无失失失真真真信信信源
38、源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 XII步骤读入码字记忆码字解码输出字典位置新单词0041A1042041B100AB2043042C101BC3100043AB102CA4044100D103ABD5100044AB104DA6102100CA105ABC7041102A106CAA8107041AA107AA9042107B108AAB10149042BB109BB11105149ABC10ABBA51Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 XIII1210B105ABCA10BABCA1
39、3FFF52Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术通通通用用用编编编码码码通用编码 XIVLZW编码算法的优化为了进一步提高压缩效果和适应超大型件的压缩需要，LZW 压缩算法不断被改进。字典的大小根据需要可以扩充，码字的长度也可以不断调整。PKZIP、ARJ、ARC、LHA、WINZIP 等压缩软件都是在 LZW 压缩编码的基础上各自采用了不同的技术改进而成的。53Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术几几几种种种编编编码码码方方方案案案的的的性性性能能能对对对比比比几种编码方案的性能对比 I香农码li=?lo
40、gr1pi?(11)L Hr(S) + 1(12)霍夫曼码L=minqPi=1rli61qXi=1pili(13)L Hr(S) + 1(14)54Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术几几几种种种编编编码码码方方方案案案的的的性性性能能能对对对比比比几种编码方案的性能对比 II费诺码L 6 Hr(S) + 2(15)香农-费诺-埃利斯码li=?logr1pi?+ 1(16)Hr(S) + 1 6 L Hr(S) + 2(17)55Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术几几几种种种编编编码码码方方方案案案的的的性性性能能能对对对比比比几种编码方案的性能对比 IIIMH 码hWB6 LWB hWB+pWnw+pBnB(18)其中 hWB为每个像素的熵； pW,pB分别为白像素和黑像素出现的概率； nW,nB分别为白、黑游程的平均长度。算术码l =?logr1p(s)?(19)H(S1S2.Sn)n6LnH(S1S2.Sn)n+1n(20)56Source Coding无无无失失失真真真信信信源源源编编编码码码技技技术术术几几几种种种编编编码码码方方方案案案的的的性性性能能能对对对比比比几种编码方案的性能对比 IVLZW 码L H(21)57
