无失真信源编码及其定理ppt课件.ppt

《无失真信源编码及其定理ppt课件.ppt》由会员分享，可在线阅读，更多相关《无失真信源编码及其定理ppt课件.ppt（96页珍藏版）》请在三一办公上搜索。

1、第四章 无失真信源编码,4.1 编码器及码的分类,4.2 等长码,4.4 等长信源编码定理,4.5变长码,4.6变长信源编码定理,4.7霍夫曼码和其它编码方法4.8几种实用的无失真信源编码小结,第四章 无失真信源编码,本章的重、难点内容1、理解等长码和等长信源编码定理2、理解和掌握变长码及变长码编码定理3、理解Huffman编码、费诺码、香农码4、了解几种实用的无失真信源编码方法，包括（MH编码、算术编码、LZ码）,第四章 无失真信源编码,编码的意义：通信的基本问题：如何高速、高质地传送信息。高速和高质鱼和熊掌。编码讨论的问题：（1）质量一定，如何提高信息传输速度（提高编码效率或压缩比）-信源

2、编码（本章讨论问题）（2）信道传输速度一定，如何提高信息传输质量（抗干扰能力）-信道编码（下一章讨论）,引言,信源编码：以提高通信有效性为目的的编码。通常通过压缩信源的冗余度来实现。采用的一般方法是压缩每个信源符号的平均比特数或信源的码率。即同样多的信息用较少的码率传送，使单位时间内传送的平均信息量增加，从而提高通信的有效性。,引言,信道编码：是以提高信息传输的可靠性为目的的编码。通常通过增加信源的冗余度来实现。采用的一般方法是增大码率/带宽。与信源编码正好相反。密码：是以提高通信系统的安全性为目的的编码。通常通过加密和解密来实现。从信息论的观点出发，“加密”可视为增熵的过程，“解密”可视为减

3、熵的过程。,引言,信源编码理论是信息论的一个重要分支，其理论基础是信源编码的两个定理。无失真信源编码定理：是离散信源/数字信号编码的基础；限失真信源编码定理：是连续信源/模拟信号编码的基础。,引言,信源编码的分类：离散信源编码、连续信源编码和相关信源编码三类。离散信源编码：独立信源编码，可做到无失真编码；连续信源编码：独立信源编码，只能做到限失真信源编码；相关信源编码：非独立信源编码。,4.1 编码器及码的分类,编码：信息的组织方式编码的实质：对信源的原始符号按一定的数学规则进行变换。编码的目的：信源编码：提高信息传输的有效性信道编码：提高信息传输的可靠性 本章不考虑干扰问题,4.1 编码器及

4、码的分类,无失真编码器结构框图几个术语：信源符号：信源输入码符号(码元)：,4.1 编码器及码的分类,码字Wi：由xj(j=1,2,r)组成的长度为 li 的序列，Wi与si一一对应。码字长度(码长)：Wi的长度li编码器：将信源符号si变换成Wi的设备信源编码信源编码：把信源符号si映射为码字Wi的过程。无失真编码：映射是一一对应、可逆的。信源编码基本思想：尽可能缩短出现概率大的信源符号的码字,4.1 编码器及码的分类,码的分类二元码：若码符号集X0，1，所得码字为一些二元序列，则称二元码。在二元信道中传输等长码（固定长度码）：若一组码中所有码字的长度都相同(即li=l,i=1,q)，则称为

5、等长码。变长码：不满足等长码条件的码组称为变长码。,4.1 编码器及码的分类,非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：反之，若码组中含有相同的码字则为奇异码。同价码：若码符号集X：x1,x2,xr中每个码符号所占的传输时间都相同，则所得的码为同价码。,4.1 编码器及码的分类,码的N次扩展码：,4.1 编码器及码的分类,惟一可译码：若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（单义可译码）。否则就称为非惟一可译码或非单义可译码。表1中码1是惟一可译码，而码2是非惟一可

6、译码。因为对于码2，其有限长的码符号序列能译成不同的信源符号序列。如码符号序列0010，可译成s1s2s1或s3s1，就不惟一了。问题：怎样才能做到无失真编码即惟一可译码？,4.2 等长码,若要实现无失真编码，不但要求信源符号si与码字Wi是一一对应的，而且要求码符号序列的反变换也是惟一的。即所编的码必须是惟一可译码。对于等长码来说，若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。等长非奇异码一定是惟一可译码。,非奇异码唯一可译码,奇异码非惟一可译码,4.2 等长码,等长编码惟一可译的必要条件：其中：q为信源符号数,r为符号集中的码元数,l为码长。例如：若信源符号数 q4，进行

7、二元等长编码，则码符号个数为 r 2。信源S存在惟一可译等长码的条件是码长 l2。若q8，r 2，l3。,4.2 等长码,对 两边取对数得平均每个信源符号所需的码符号个数上式表明：对于等长惟一可译码而言，平均每个信源符号至少需要用 logqlogr个码符号来表示。即：每个信源符号所需最短码长为 logqlogr个。,4.2 等长码,当r=2(二元码)时logr=1,上式变成上式表明：对于二元等长惟一可译码，平均每个信源符号至少需要用logq个码符号来变换。或：对信源进行二元等长不失真编码时，每个信源符号所需的极限值为logq个。,4.2 等长码,当考虑到符号之间的依赖关系或关联性时，可以从N次

8、扩展信源中去掉一些符号，使得总符号数小于，这样使编码所需码字个数大大减少，因此平均每个信源符号所需的码符号个数就可以大大减少，从而提高传输效率。当N足够长后，这种误差概率可以任意小，做到几乎无失真编码。等长编码定理给出了信源进行等长编码所需码长的理论极限值。,4.4 等长信源编码定理,定理4.3(等长信源编码定理):一个熵为H(S)的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取l个码元组成。对于任意0，只要满足：则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。反之，若 当N足够大时，译码错误概率近 似为1,不可能实现无失真编码。,4.

9、4 等长信源编码定理,说明：定理4.3是在平稳无记忆离散信源的条件下得出，但它同样适合于平稳有记忆信源。当进行二元编码时，r2，则：一般情况下，信源符号并非等概率分布，且符号之间有很强的关联性，故信源的熵H(S)logq。,等长编码时平均每个信源符号所需的二元码符号的理论极限,信源等概分布时,4.4 等长信源编码定理,从定理4.3可知，在等长编码中每个信源符号平均所需的二元码符号可大大减少，从而使编码效率提高。定理4.3中的条件式可改写成：,长为l的码符号序列所能载荷的最大信息量,长为N的信源序列平均携带的信息量,4.4 等长信源编码定理,所以等长编码定理告诉我们：只要码字传输的信息量大于信源

10、序列携带的信息量，总可实现几乎无失真编码。令 它是编码后平均每个信源符号能载荷的最大信息量，称为编码信息率。可见，当编码信息率大于信源的熵时，才能实现几乎无失真编码。为衡量编码效果，引入编码效率。,4.4 等长信源编码定理,称 为编码效率。由定理4.3可得最佳等长编码的效率为：如果自信息的方差 和均为定值时，只要N足够大，编码错误就可以小于任一正数。也即要求误差小于时，,4.4 等长信源编码定理,信源序列长度N必须满足：该式给出了在已知方差和信源熵的条件下，信源序列长度N与最佳编码效率和允许错误概率的关系。允许错误概率越小，编码效率要求越高，则信源序列长度N就必须越长。实际情况下，要实现几乎无

11、失真的等长编码，N需要非常大。,4.4 等长信源编码定理,例 设离散无记忆信源信源熵自信息方差若对信源S采用等长二元编码，要求编码效率=0.96，允许错误概率,4.4 等长信源编码定理,则得即序列长度达4130万以上，这在实际中很难实现。因此，一般来说，当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。下面介绍变长码，及其编码定理。,4.5 变长码,4.5.1 惟一可译变长码与即时码等长码仅当N很大才会有较高的编码效率；变长码往往在N不很大时就可编出效率很高而且无失真的码。等长码：非奇异 惟一可译变长码：任意有限长N次扩展码是非奇异 惟一可译,4.

12、5 变长码,即时码：在译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号的惟一可译码码4以“1”作为结束符号，起到逗号的作用，又称为逗点码。逗点码是一种即时码。,非惟一可译奇异码,非惟一可译非奇异码,惟一可译非奇异码,惟一可译非奇异码,4.5 变长码,定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字都不是另一个码字的前缀，则称为即时码也称非延长码或前缀条件码。,所有码,非奇异码,惟一可译码,即时码,4.5 变长码,4.5.2 即时码的树图构造法构造即时码的一种简单方法是树图法。,根：树的最上端树枝的个数为r，r=2为二元码树,中间节点（空心）,节点：树枝

13、的终端，从节点生出树枝，每个节点伸出r个枝,终端节点（实心）,码字：从根到终端节点对应的码符号，又称树叶,4.5 变长码,按树图法构成的码一定满足即时码的充要条件，因为从根到叶所走的路径各不相同，而且中间节点不安排为码字，所以一定满足对前缀的限制。该树的5个终端节点W1,W2,W3,W4,W5分别表示5个二进制码字0，100，111，1010，1011,4.5 变长码,码树的性质：任一即时码都可用树图表示。当码字长度给定，即时码不是惟一的。整树：每个节点上都有r个分枝。非整树：至少有一个节点上没有r个分枝的树。,4.5.4 惟一可译变长码的判断法,结论：不能用Kraft不等式，只能根据定义判断

14、码C是否是惟一可译码。依据：非惟一可译变长码 有限长的码符号序列能译成两种不同的码字序列。惟一可译变长码判别：将码C中所有可能的尾随后缀组成一个集合F，当且仅当集合F中没有包含任一码字时，码C为惟一可译变长码。,4.5.4 惟一可译变长码的判断法,构成集合F的方法：首先，观察码C中最短的码字是否是其他码字的前缀。若是，将其所有可能的尾随后缀排列出。而这些尾随后缀又可能是某些码字的前缀，再将由这些尾随后缀产生的新的尾随后缀列出。依此下去，直至没有一个尾随后缀是码字的前缀或没有新的尾随后缀产生为止。接着，按照上述步骤将次短的码字直至所有码字可能产生的尾随后缀全部列出。,4.6 变长信源编码定理,对

15、于已知信源S可用码符号X进行变长编码，而且对同一信源可有多种即时码或惟一可译码。选择哪一种最好呢？从高速度传输信息的角度，希望用短的码符号组成码字，即用码长作为选择准则引进码的平均长度。,4.6 变长信源编码定理,设信源为编码后的码字为其码长分别为对于惟一可译码，有则这个码的平均长度为：单位是码符号/信源符号，是每个信源符号平均需用的码元数。,4.6 变长信源编码定理,编码后信道的信息传输率（编码后平均每个码元携带的信息量）:若传输一个码符号平均需要t秒钟，则编码后信道每秒传输的信息量为可见，码的平均长度越短、越大，信息传输效率就越高。对于编码者来说，感兴趣的是平均码长 短的码。问题：如何找到

16、码长最短的惟一可译码？,4.6 变长信源编码定理,紧致码（最佳码）：对于某一信源和某一码符号集来说，若有一个惟一可译码，其平均长度小于所有其他惟一可译码的平均长度，则该码称为紧致码，或称最佳码。无失真信源编码的基本问题转化为找出紧致码。最佳码也就是紧致码的平均长度不是可以无限制缩小的，在理论上是有它的极限值的（在无失真信源编码的条件下），香农第一定理给出了这一极限值，这一定理有很大的实际意义。,4.6 变长信源编码定理,定理4.8 无失真变长信源编码定理(即香农第一定理)：离散无记忆信源S的N次扩展信源，其熵为，并有码符号X=x1,x2,xr。对信源 进行编码，总可以找到一种编码方法，构成惟一

17、可译码，使信源S中每个信源符号所需的平均码长满足：,4.6 变长信源编码定理,当 时，得其中 表示对N个信源符号的序列 进行编码。,4.6 变长信源编码定理,定理4.8是香农信息论的主要定理之一，它说明要做到无失真的信源编码，编码每个信源符号平均所需最少的r元码元数为信源的熵Hr(S)。即熵Hr(S)是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值Hr(S)，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码，当 时，平均码长,4.6 变长信源编码定理,从信道角度看，信道的信息传输率因为 所以极限情况下，编码后信道的信息传输率为：这时信道的信息传输率等

18、于无噪无损信通的信道容量C，信息传输效率最高。,4.6 变长信源编码定理,香农第一定理的物理意义：无失真信源编码的实质：对离散信源进行适当变换 变换后新信源符号(信道的输入信源)尽可能为等概率分布 新信源符号平均所含的信息量达到最大 使信道的信息传输率R达到信道容量C，实现信源与信道理想的统计匹配。,4.6 变长信源编码定理,无失真信源编码定理通常又称为无噪信道编码定理。表述为：若信道的信息传输率R不大于信道容量C，总能对信源的输出进行适当的编码，使得在无噪无损信道上能无差错地以最大信息传输率C传输信息，但要使信道的信息传输率R大于C而无差错地传输信息则是不可能的。,4.6 变长信源编码定理,

19、为了衡量各种编码是否达到极限情况，定义变长码的编码效率为：一般用码的效率来衡量各种编码的优劣。为了衡量各种编码与理论极限的差距，定义码的剩余度为：,4.6 变长信源编码定理,在二元无损无噪信道中r=2，所以在二元无损无噪信道中信息传输率和R数值相同但单位不同在二元信道中若=1，即信息传输率R=1比特码符号，达到了信道的信道容量，编码效率最高，码剩余度为零。,4.6 变长信源编码定理,例：有一离散无记忆信源其熵为：0.811用二元码符号构造一个即时码平均码长编码效率 编码效率较低，为此对信源S的二次扩展信源S2 进行编码。,4.6 变长信源编码定理,平均码长,4.6 变长信源编码定理,由此可得，

20、编码复杂了一些，但是信息传输率提高了同理，对信源S的三次和四次扩展信源进行编码，其编码效率和信道的信息传输率分别为：,4.6 变长信源编码定理,很明显，用变长码编码时，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。随着扩展信源次数的增加，编码的效率越来越接近于1，编码后信道的信息传输率R也越来越接近于无噪无损二元信道的信道容量C=1bit/symbol，达到信源与信道匹配，使信道得到充分利用。,4.7 霍夫曼码和其他编码方法,本节介绍霍夫曼(Huffman)码、费诺(Fano)码和香农-费诺-埃利斯(Shannon-Fano-Elias)码。香农第一定理指出了平均码长与信源熵

21、之间的关系，同时也指出了通过编码可使平均码长达到极限值。但没有给出具体的编码方法。那么如何编码呢？也就是如何去构造一个紧致码？具体的编码方法如何？下面我们来讨论霍夫曼码的编码方法。,4.7.1 霍夫曼（Huffman）码编码步骤,1.将q个信源符号按概率递减的方式排列起来。2.用“0”,“1”码符号分别表示概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个符号，从而得到只包含 q-1个符号的新信源，称之为S信源的缩减信源S1。3.将缩减信源S1的符号仍按概率大小以递减次序排列，再将其最后两个概率最小的符号合并成一个符号，并分别用“0”，“1”码符号表示，这样又形成了q-2个符号的缩

22、减信源S2。,4.7.1 霍夫曼（Huffman）码编码步骤,4.依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用“0”，“1”码符号表示，然后从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即得出对应的码字。例 设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。编码过程如下图（后页）。,4.7.1 霍夫曼（Huffman）码,霍夫曼码是一种即时码，可用码树形式来表示。将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。,4.7.1 霍夫曼（Huffman）码,信源熵为：平均码长为编码效率为若采用定长编码,码长L=3,则编码效率可见哈夫曼的编

23、码效率提高了12.7%。,注意：霍夫曼编码并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。不同的码元分配，得到的具体码字不同，但码长li不变，平均码长 也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度li也不尽相同。,4.7.1 霍夫曼（Huffman）码,例：单符号离散无记忆信源，用两种不同的方法对其编二进制霍夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。,4.7.1 霍夫曼（Huffman）码

24、,方法二：合并后的新符号排在其它相同概率符号的前面。这两种编码哪一种更好呢？我们来计算一下二者的平均码长。,0,1,0,1,0,1,0,1,4.7.1 霍夫曼（Huffman）码,两种编码的平均码长是一样的，说明两种编码效率一样，哪一种更好呢？我们可以计算一下平均码长的方差。定义码字长度的方差2：,4.7.1 霍夫曼（Huffman）码,可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有2种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。,4.7.1 霍夫曼（Huffm

25、an）码,结论：在霍夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。,4.7.1 霍夫曼（Huffman）码,霍夫曼码的特点：霍夫曼码的编码方法保证了概率大的符号对应于短码，概率小的符号对应于长码,即 而且短码得到充分利用。每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同(二元编码情况)。每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的霍夫曼码一定是最佳码。,4.7.3 霍夫曼（Huffman）码的最佳性,最佳码的一些性质：定理4.9 对于给定分布的任

26、何信源，存在一个最佳即时码(其平均码长最短)，此码满足以下性质(1)若pjpk，则ljlk。(2)两个最小概率的信源符号所对应的码字具有相同的码长。(3)两个最小概率的信源符号所对应的码字，其除最后一位码元不同外，前面各位码元都相同。,4.7.3 霍夫曼（Huffman）码的最佳性,说明：定理4.9中所述的三个性质正好是霍夫曼编码三个特点。由此可见，霍夫曼码C是信源给定后，所有可能的惟一可译码中平均码长最短的码，即,4.7.3 霍夫曼（Huffman）码的最佳性,定理4.10 二元霍夫曼码一定是最佳即时码。即若C是霍夫曼码，C是任意其他即时码，则有：因为霍夫曼码是在信源给定情况下的最佳码，所以

27、其平均码长的界限为：对信源的N次扩展信源同样可以采取霍夫曼编码方法。因为霍夫曼码是紧致码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值信源的熵。,4.7.4 费诺（Fano）码,费诺编码也是一种常见的信源编码方法。费诺码不是最佳的编码方法，但有时也可得到最佳码的性能。费诺码的编码程序如下：（1）信源符号以概率递减的次序排列起来，将排列好的信源符号划分成两大组，使每组的概率之和接近于相等，并各赋予一个二元码符号“0”和“1”；（2）将每一大组的信源符号再分成两组，使同一组的两个小组的概率之和接近于相等，再分别赋予一个二元码符号。,4.7.4 费诺（Fano）码,（3）依次下去

28、，直至每个小组只剩一个信源符号为止。例 设有一单符号离散信源对该信源编二进制费诺码。,4.7.4 费诺（Fano）码,该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。,4.7.4 费诺（Fano）码,费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码。费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长短的码字。从而有效地提高了编码效率。费诺编码方法不一定使短码得到充分利用。尤其当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法会很多。可

29、能某种分大组的结果，会使后面小组的“概率和”相差较远，使平均码长增加。费诺码不一定是最佳码。,4.7.5香农费诺埃利斯码,香农-费诺-埃利斯(Shannon-Fano-Elias)编码方法，是采用信源符号的累积分布函数来分配码字的。设信源符号集，定义累积分布函数：定义修正的累积分布函数：,4.7.5香农费诺埃利斯码,累积分布函数为每台阶的上界值。而台阶的高度为 的值，的值正处于对应于 台阶的中点当，知道了 就能确定信源符号为,因此可用 的值作为符号 的码字。,4.7.5香农费诺埃利斯码,每个信源符号ak所编码的码字对应的区域都没有重叠，码组满足前缀条件，为即时码。用二进数表示，一般为无限位二进

30、制数。取小数后l(ak)位，即截去后面的位数，得 的近似值，并用这l(ak)位二进数作为ak的码字。其中 表示取l位使小于等于x的数。一般取,4.7.5香农费诺埃利斯码,例 离散无记忆信源，它的香农费诺埃利斯码表如下：平均码长信源熵,4.7.5香农费诺埃利斯码,例 给出另一信源 的香农费诺埃利斯码平均码长,一些结论,霍夫曼码、费诺码、香费埃码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；霍夫曼码和费诺码的编码方法都不惟一；费诺码比较适合于对分组概率相等或接近的信源编码；霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的

31、要求也比较简单，因此综合性能优于费诺码和香费埃码。,4.8几种实用的无失真信源编码方法,在实际编码压缩技术中，常常结合实际信源情况，在压缩技术上给以改进，使便于操作和软硬件实现，本节介绍几种实用的无失真信源编码的方法。4.8.1 MH码MH（Modified Huffman），即修正的霍夫曼编码，MH编码是用于黑白二值文件传真的数据压缩，1997年被CCITT推荐为传真机一维压缩编码的国际标准。,4.8.1 MH码,文件传真是指一般文件、图纸、手写稿、表格、报纸等文件的传真。它们是黑白二值的，也就是信源是二元信源q=2。文件图纸根据清晰度的要求来决定空间扫描分辨率，将文件图纸在空间上离散化。分

32、辨率越高，分的越细，质量越高。国际规定，A4（210mm297mm）幅面文件应该有1188或2376条扫描线，每条扫描线有1728个像素的扫描分辨率（相当于垂直4或8线/mm，水平8点/mm）。,4.8.1 MH码,因此，A4文件纸约有2.05M像素/公文纸或4.1M像素/公文纸，从节省传送时间和存储空间来说，必须进行数据压缩。MH编码是一维编码方案，即对一行一行的数据进行编码。它将游程编码和霍夫曼编码相结合，是一种标准的改进霍夫曼码。从文件来看，每行中会出现连续个“白”像素或连续个“黑”像素，同一符号出现而形成字符串的长度称之为游程长度。,4.8.1 MH码,MH码分别对“白”、“黑”的不同

33、游程长度进行霍夫曼编码，形成黑、白两张码表。编、译码通过查表进行。每行总是从白色游程开始（如第一像素为黑色，则此长度可设为零）。如游程长度超过63个像素则分成两部分：前面是组合基干码，后为结尾码。修正MH编码一次只压缩一扫描行，各行独立不相关，因此是一种一维编码方案。,4.8.1 MH码,例 设某页传真文件中某一扫描行的像素点为|17白|5黑|55白|10黑|1641白|该行HM码为101011|0011|010110000|0000100|010010101|00101010|EOL数据压缩比：1728/5432，压缩率很高。,4.8.2算术编码,算术编码不同于霍夫曼码，它是非分组码。它从全

34、序列出发，考虑符号之间的依赖关系来进行编码的。霍夫曼码 必须对二元信源的N次扩展信源进行编码时，才能使平均码长很快接近信源的熵，编码效率才高，而MH码的码表非常的庞大。问题，对于很长的信源符号序列是否存在简单有效的编码方法呢？,4.8.2算术编码,由香费埃推广得到的算术编码就可以达到这个目的。下面举例说明算术码是如何具体编码的。例 设二元无记忆信源对二元序列 做算术编码。解：,4.8.2算术编码,信源符号序列s的累积分布函数：从上式得得C0.1101010 得s的码字为1101010,4.8.2算术编码,编码效率为可见这种按全序列进行编码，随着信源序列n的增长，效率还会增高，平均码长接近信源的

35、熵。按算术编码方法编出的码字为即时码。,4.8.3 LZ码,对于统计特性确知的平稳信源，已有霍夫曼码和算术码效率很高的编码方法。但是要知道信源的统计特性相当困难。通用编码就是指在信源统计特性不知时，对信源进行编码，而使编码效率仍很高的码。LZ码就是一种通用编码方法。LZ码是1977年两位以色列研究人员，齐费和兰佩尔提出的，它是一种基于字典的编码方法。1978年齐费和兰佩尔又提出了改进算法叫做LZ78码。,4.8.3 LZ码编码方法,LZ78的编码算法是一种分段编码。设信源符号集为 共q个符号，设输入信源符号序列为，编码就是将此序列分成不同的C段。分段规则是尽可能取最少个连着的信源符号，并保证各

36、段都不同。首先取一个符号作为第一段，然后再继续分段。若出现与前面相同符号时，就再取紧跟后面的一个符号一起组成一个段，以使与前面的段不同。,4.8.3 LZ码,有了许多段后，再分段时就应查看有否与前面段的短语相同，若有重复就添加符号后使与前面的段不同，可直至信源符号序列结束。这样，不同的段内的信源符号可看成一短语，可得不同段所对应的短语字典表。（见后例）码字由段号加后面一个符号组成。段号所需码长，每个符号所需码长为对于单符号的码字，其段号数为0,4.8.3 LZ码,例 设q=4,信源序列为根据分段规则，可分段为编码字典表此序列编码为00000001100001100001100001010011

37、010,4.8.3 LZ码,可见，LZ78码编码方法简单又快捷，码符号序列的译码也很直接，一边译码一边又建成字典表，所以字典表无需传送，能无误地恢复成原信源符号序列。在上例中，这二元序列共有35位，似乎比不编码还差。但当序列n增长时，段内短语的符号数也将增长，尤其是某些符号重复出现的话，编码效率将会提高。,4.8.3 LZ码,LZ78码是一种简单的通用编码，编码方法不依赖信源的概率分布。这种编码方法不需知道有关信源的统计特性，而且编码方法简单，编译速度快，又能达到最佳压缩编码效率。1984年韦尔奇给出了LZ78算法的实用修正形式，称为LZW算法。LZW算法保留了LZ码的自适应能力，它成为计算机文件压缩的标准算法，已成为UNIX操作系统的标准文件压缩程序和arc文件的压缩程序。,本章小结,无失真信源压缩极限（包括等长信源编码和变长信源编码定理）霍夫曼码：,费诺码香农费诺埃利斯码信源符号的累积分布函数截取长度平均码长,MH码：是一种修正了的霍夫曼码，是CCITT制定的一维传真编码的国际标准。算术编码信源符号序列的累积分布函数：截取长度：LZ码：是一种通用编码，无需知道信源分布概率的一种通用编码方法。,