信息论与编码课件(第四章)

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、编码：提高信息传输的有效性信道编码：提高信息传输的可靠性 本章不考虑干扰问题电气信息工程学院4.1 编码器及码的分类无失真编码器结构框图几个术语：信源符号：信源输入码符号 (码元)：电气信息工程学院12 ,.,qSS SS12 ,.,rXx xx编码器编码器12:,.,qCWWW信源码字符号集12 ,.,qSS SS12 ,.,rXx xx4.1 编码器及码的分类码字Wi： 由xj (j=1,2,r)组成的长度为 li 的序列，Wi与si一一对应。码字长度 (码长)： Wi的长度li编码器：将信源符号si变换成Wi的设备信源编码信源编码：把信源符号si映射为码字Wi的过程。 无失真编码：映射是

5、一一对应、可逆的。 信源编码基本思想：尽可能缩短出现概率大的信源符号的码字电气信息工程学院4.1 编码器及码的分类码的分类二元码：若码符号集X0，1，所得码字为一些二元序列，则称二元码。在二元信道中传输等长码（固定长度码）：若一组码中所有码字的长度都相同(即li=l,i=1,q)，则称为等长码。变长码：不满足等长码条件的码组称为变长码。电气信息工程学院4.1 编码器及码的分类非奇异码：若一组码中所有码字都不相同(即所有信源符号映射到不同的码符号序列，不同信源符号可分辨)，则称为非奇异码。奇异码：反之，若码组中含有相同的码字则为奇异码。同价码：若码符号集X：x1,x2,xr中每个码符号所占的传输

6、时间都相同，则所得的码为同价码。电气信息工程学院4.1 编码器及码的分类码的N次扩展码：电气信息工程学院信源符号出现概率码1码2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111信源码 字信源码 字信源码 字a100W1W1=B1a5.010W2W1=B1.a16.111111=W4W4=B16a2001W1W2=B2a30001W1W3=B3a40111W1W4=B44.1 编码器及码的分类惟一可译码：若码的任意一串有限长的码符号序列只能被惟一地译成所对应的信源符号序列，则此码称为惟一可译码（单义可译码）。否则就称为非惟一可译码或非单义可译码。表1中码

7、1是惟一可译码，而码2是非惟一可译码。因为对于码2，其有限长的码符号序列能译成不同的信源符号序列。如码符号序列0010，可译成s1s2s1或s3s1，就不惟一了。问题：怎样才能做到无失真编码即惟一可译码？电气信息工程学院4.2 等长码若要实现无失真编码，不但要求信源符号si与码字Wi是一一对应的，而且要求码符号序列的反变换也是惟一的。即所编的码必须是惟一可译码。对于等长码来说，若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码。等长非奇异码一定是惟一可译码。电气信息工程学院信源符号码1码2s10000s20111s31010s41111非奇异码唯一可译码奇异码非惟一可译码4.2 等

8、长码等长编码惟一可译的必要条件：其中： q为信源符号数,r为符号集中的码元数,l为码长。 例如：若信源符号数 q4，进行二元等长编码，则码符号个数为 r 2。信源S存在惟一可译等长码的条件是码长 l2。若q8，r 2，l3。电气信息工程学院lNrq4.2 等长码对 两边取对数得平均每个信源符号所需的码符号个数上式表明：对于等长惟一可译码而言，平均每个信源符号至少需要用 logqlogr个码符号来表示。即：每个信源符号所需最短码长为 logqlogr个。电气信息工程学院rlqNloglogrqNllogloglNrq4.2 等长码当r=2(二元码)时logr=1, 上式变成上式表明：对于二元等长

9、惟一可译码，平均每个信源符号至少需要用logq个码符号来变换。或：对信源进行二元等长不失真编码时，每个信源符号所需的极限值为logq个。电气信息工程学院qNllog4.2 等长码当考虑到符号之间的依赖关系或关联性时，可以从N次扩展信源中去掉一些符号，使得总符号数小于 ，这样使编码所需码字个数大大减少，因此平均每个信源符号所需的码符号个数就可以大大减少，从而提高传输效率。当N足够长后，这种误差概率可以任意小，做到几乎无失真编码。等长编码定理给出了信源进行等长编码所需码长的理论极限值。电气信息工程学院Nq4.4 等长信源编码定理定理4.3 (等长信源编码定理): 一个熵为H(S)的离散无记忆信源，

10、若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取l个码元组成。对于任意0，只要满足：则当N足够大时，可实现几乎无失真编码，即译码错误概率能为任意小。反之，若 当N足够大时，译码错误概率近 似为1,不可能实现无失真编码。电气信息工程学院rSHNllog)(rSHNllog2)(4.4 等长信源编码定理说明：定理4.3是在平稳无记忆离散信源的条件下得出，但它同样适合于平稳有记忆信源 。当进行二元编码时，r2，则：一般情况下，信源符号并非等概率分布，且符号之间有很强的关联性，故信源的熵H(S)logq。 电气信息工程学院)(SHNl等长编码时平均每个信源符号所需的二元码符号的

11、理论极限qNllog信源等概分布时4.4 等长信源编码定理从定理4.3可知，在等长编码中每个信源符号平均所需的二元码符号可大大减少，从而使编码效率提高。定理4.3中的条件式可改写成： 电气信息工程学院)(loglog)(SNHrlrSHNl长为l的码符号序列所能载荷的最大信息量长为N的信源序列平均携带的信息量4.4 等长信源编码定理所以等长编码定理告诉我们：只要码字传输的信息量大于信源序列携带的信息量，总可实现几乎无失真编码。令 它是编码后平均每个信源符号能载荷的最大信息量，称为编码信息率。可见，当编码信息率大于信源的熵时，才能实现几乎无失真编码。为衡量编码效果，引入编码效率。电气信息工程学院

12、)(logSHrNlrNlRlog4.4 等长信源编码定理称 为编码效率。由定理4.3可得最佳等长编码的效率为： 如果自信息的方差 和均为定值时，只要N足够大，编码错误就可以小于任一正数。也即要求误差小于时，电气信息工程学院rNlSHRSHlog)()(0)(1)()(SHSHSH)(isID4.4 等长信源编码定理信源序列长度N必须满足：该式给出了在已知方差和信源熵的条件下，信源序列长度N与最佳编码效率 和允许错误概率 的关系。允许错误概率越小，编码效率要求越高，则信源序列长度N就必须越长。实际情况下，要实现几乎无失真的等长编码，N需要非常大。电气信息工程学院)1 ()()()(2222SH

13、sIDsIDNii4.4 等长信源编码定理例 设离散无记忆信源信源熵自信息方差若对信源S采用等长二元编码，要求编码效率=0.96，允许错误概率电气信息工程学院41,43,)(21sssPS)(811. 034log434log41)(symbolbitSH4715. 0)811. 0()41(log41)43(log43)()(log)(2222122iiiiSHppsID5104.4 等长信源编码定理则得即序列长度达4130万以上，这在实际中很难实现。因此，一般来说，当N有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能像变长码那样可以实现无失真编码。下面介绍变长码，及其编码定理。

14、电气信息工程学院752221013. 41004. 0)96. 0()811. 0(4715. 0N4.5 变长码4.5.1 惟一可译变长码与即时码等长码仅当N很大才会有较高的编码效率；变长码往往在N不很大时就可编出效率很高而且无失真的码。等长码：非奇异 惟一可译变长码：任意有限长N次扩展码是非奇异 惟一可译电气信息工程学院4.5 变长码即时码：在译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号的惟一可译码码4以“1”作为结束符号，起到逗号的作用，又称为逗点码 。逗点码是一种即时码。电气信息工程学院信源符号出现概率码1码2码3码4s1s2s3s41/21/41/81/801100

15、11010000111010010001010010001非惟一可译奇异码非惟一可译非奇异码惟一可译非奇异码惟一可译非奇异码4.5 变长码定义定义：如果一个码组中的任一个码字都不是另一个码字的续长，或者说，任何一个码字都不是另一个码字的前缀，则称为即时码也称非延长码或前缀条件码。 电气信息工程学院所有码非奇异码惟一可译码即时码4.5 变长码4.5.2 即时码的树图构造法构造即时码的一种简单方法是树图法。电气信息工程学院信源符号码4s1s2s3s41010010001根：树的最上端树枝的个数为r，r=2为二元码树01001111010010001码4的树图ABCD中间节点（空心）节点：树枝的终端

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

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

18、全部列出。电气信息工程学院4.6 变长信源编码定理对于已知信源S可用码符号X进行变长编码，而且对同一信源可有多种即时码或惟一可译码。选择哪一种最好呢？从高速度传输信息的角度，希望用短的码符号组成码字，即用码长作为选择准则引进码的平均长度。电气信息工程学院4.6 变长信源编码定理设信源为编码后的码字为其码长分别为对于惟一可译码，有则这个码的平均长度为：单位是码符号/信源符号，是每个信源符号平均需用的码元数。电气信息工程学院)(,),(),(,)(2121qqsPsPsPssssPSqWWW,21qlll,21),2 , 1()()(qisPWPiiqiiilsPL1)(4.6 变长信源编码定理编

19、码后信道的信息传输率 （编码后平均每个码元携带的信息量）: 若传输一个码符号平均需要t秒钟，则编码后信道每秒传输的信息量为可见，码的平均长度越短、 越大，信息传输效率就越高。对于编码者来说，感兴趣的是平均码长 短的码。问题：如何找到码长最短的惟一可译码？ 电气信息工程学院)/()(sbitLtSHRttRtRL4.6 变长信源编码定理紧致码（最佳码）：对于某一信源和某一码符号集来说，若有一个惟一可译码，其平均长度小于所有其他惟一可译码的平均长度，则该码称为紧致码，或称最佳码 。无失真信源编码的基本问题转化为找出紧致码。最佳码也就是紧致码的平均长度不是可以无限制缩小的，在理论上是有它的极限值的（

20、在无失真信源编码的条件下），香农第一定理给出了这一极限值，这一定理有很大的实际意义。 电气信息工程学院4.6 变长信源编码定理定理4.8 无失真变长信源编码定理(即香农第一定理) ： 离散无记忆信源S的N次扩展信源 ，其熵为 ，并有码符号X=x1,x2,xr 。对信源 进行编码，总可以找到一种编码方法，构成惟一可译码，使信源S中每个信源符号所需的平均码长满足：电气信息工程学院NqNS,21)(NSHNS4.6 变长信源编码定理当 时，得其中 表示对N个信源符号的序列 进行编码。电气信息工程学院)(1)(log)(1log)(SHNLNSHrSHNLNrSHrNrN或N)(limSHNLrNNN

21、qiiiNpL1)(NLNi4.6 变长信源编码定理定理4.8是香农信息论的主要定理之一，它说明要做到无失真的信源编码，编码每个信源符号平均所需最少的r元码元数为信源的熵Hr(S) 。即熵Hr(S) 是无失真信源压缩的极限值。若编码的平均码长小于信源的熵值Hr(S) ，则惟一可译码不存在，在译码或反变换时必然要带来失真或差错。通过对扩展信源进行变长编码，当 时，平均码长 电气信息工程学院N)(SHr4.6 变长信源编码定理从信道角度看，信道的信息传输率因为 所以极限情况下，编码后信道的信息传输率为：这时信道的信息传输率等于无噪无损信通的信道容量C，信息传输效率最高。电气信息工程学院LSHR)(

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

23、6 变长信源编码定理为了衡量各种编码是否达到极限情况，定义变长码的编码效率为：一般用码的效率来衡量各种编码的优劣。为了衡量各种编码与理论极限的差距，定义码的剩余度为：电气信息工程学院LSHr)(LSHr)(114.6 变长信源编码定理在二元无损无噪信道中r=2， 所以在二元无损无噪信道中信息传输率和R数值相同但单位不同在二元信道中若=1，即信息传输率R=1比特码符号，达到了信道的信道容量，编码效率最高，码剩余度为零。电气信息工程学院)()(SHSHrLSH)(LSHR)(4.6 变长信源编码定理例：有一离散无记忆信源其熵为： 0.811用二元码符号构造一个即时码平均码长编码效率 编码效率较低

24、，为此对信源S的二次扩展信源S2 进行编码。电气信息工程学院4143,)(2121ppsssPS)(SH1,021ssL)( 1141143)(1信源符号二元码符号qiiilsP811. 0)(LSH4.6 变长信源编码定理平均码长电气信息工程学院即时码s1s19/160s1s23/1610s2s13/16110s2s21/16111i()iP)(162731613163216311692信源符号二元码符号L844. 0322722LL961. 0)(2LSH961. 0)(22LSHR4.6 变长信源编码定理由此可得，编码复杂了一些，但是信息传输率提高了同理，对信源S的三次和四次扩展信源进行

25、编码，其编码效率和信道的信息传输率分别为：电气信息工程学院985. 03991. 04)(985. 03二元码符号比特R)(991. 04二元码符号比特R4.6 变长信源编码定理很明显，用变长码编码时，N不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。随着扩展信源次数的增加，编码的效率越来越接近于1，编码后信道的信息传输率R也越来越接近于无噪无损二元信道的信道容量C=1bit/symbol，达到信源与信道匹配，使信道得到充分利用。电气信息工程学院4.7 霍夫曼码和其他编码方法本节介绍霍夫曼(Huffman)码、费诺(Fano)码和香农-费诺-埃利斯(Shannon-Fano-El

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

27、并分别用“0”，“1”码符号表示，这样又形成了q-2个符号的缩减信源S2。电气信息工程学院4.7.1 霍夫曼（Huffman）码编码步骤4. 依次继续下去，直到信源最后只剩下两个符号为止，将这最后两个符号分别用“0”，“1” 码符号表示，然后从最后一级缩减信源开始，向前返回，得出各信源符号所对应的码符号序列，即得出对应的码字。例 设单符号离散无记忆信源如下，要求对信源编二进制霍夫曼码。编码过程如下图（后页）。电气信息工程学院12345678,()0.10.070.060.050.04XxxxxxxxxP X电气信息工程学院4.7.1 霍夫曼（Huffman）码霍夫曼码是一种

28、即时码，可用码树形式来表示。将上图左右颠倒过来重画一下，即可得到二进制哈夫曼码的码树。 电气信息工程学院01001111树图X1:1X2:001000011X3:011X4:0000X5:0100X6:0101X7:00010X8:000114.7.1 霍夫曼（Huffman）码信源熵为：平均码长为编码效率为若采用定长编码,码长L=3,则编码效率可见哈夫曼的编码效率提高了12.7%。电气信息工程学院821( )( )log( )2.55(/)iiiH Xp xp x比特 符号)(61. 25)05. 004. 0(4)06. 007. 01 . 0(3) 1 . 018. 0(4 . 0)(8

29、1信源符号码符号iiilxpL%7 .9761. 255. 2)(LXH2.55385%注意：霍夫曼编码并不惟一。每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长li不变，平均码长 也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同。不同的编法得到的码字长度li也不尽相同。电气信息工程学院L4.7.1 霍夫曼（Huffman）码例：单符号离散无

30、记忆信源 ，用两种不同的方法对其编二进制霍夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。电气信息工程学院12345,()0.10.1XxxxxxP XsiliWi概率s1s2s3s4s5123441010000010000.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101014.7.1 霍夫曼（Huffman）码方法二：合并后的新符号排在其它相同概率符号的前面。这两种编码哪一种更好呢？我们来计算一下二者的平均码长。电气信息工程学院siliWi概率s1s2s3s4s522233001011010011

31、0.10.1 0.4 0.2 0.2 0.2 0.4 0.4 0.2 0.6 0.4010101014.7.1 霍夫曼（Huffman）码两种编码的平均码长是一样的，说明两种编码效率一样，哪一种更好呢？我们可以计算一下平均码长的方差。定义码字长度的方差2：电气信息工程学院511( )0.4 1 0.2 20.2 30.1 40.1 42.2iiiLP s l 521( )0.4 20.2 20.2 20.1 30.1 32.2iiiLP s l 2221() ( )()qiiiiE lLP slL522111( )()1.36iiiP slL522221( )()0.16ii

32、iP slL4.7.1 霍夫曼（Huffman）码可见：第二种编码方法的码长方差要小许多。意味着第二种编码方法的码长变化较小，比较接近于平均码长。第一种方法编出的5个码字有4种不同的码长；第二种方法编出的码长只有2种不同的码长；显然，第二种编码方法更简单、更容易实现，所以更好。电气信息工程学院4.7.1 霍夫曼（Huffman）码结论：在霍夫曼编码过程中，对缩减信源符号按概率由大到小的顺序重新排列时，应使合并后的新符号尽可能排在靠前的位置，这样可使合并后的新符号重复编码次数减少，使短码得到充分利用。电气信息工程学院4.7.1 霍夫曼（Huffman）码霍夫曼码的特点： 霍夫曼码的编码方法保证了

33、概率大的符号对应于短码，概率小的符号对应于长码,即 而且短码得到充分利用。每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同(二元编码情况) 。每次缩减信源的最长两个码字有相同的码长。这三个特点保证了所得的霍夫曼码一定是最佳码。电气信息工程学院kjkjllpp4.7.3 霍夫曼（Huffman）码的最佳性最佳码的一些性质：定理4.9 对于给定分布的任何信源，存在一个最佳即时码(其平均码长最短)，此码满足以下性质(1)若pjpk，则ljlk。(2)两个最小概率的信源符号所对应的码字具有相同的码长。(3)两个最小概率的信源符号所对应的码字，其除最后一位码元不同外，前面各位码元都相同。

34、电气信息工程学院4.7.3 霍夫曼（Huffman）码的最佳性说明：定理4.9中所述的三个性质正好是霍夫曼编码三个特点。由此可见，霍夫曼码C是信源给定后，所有可能的惟一可译码中平均码长最短的码，即电气信息工程学院4.7.3 霍夫曼（Huffman）码的最佳性定理4.10 二元霍夫曼码一定是最佳即时码。即若C是霍夫曼码，C是任意其他即时码， 则有：因为霍夫曼码是在信源给定情况下的最佳码，所以其平均码长的界限为：对信源的N次扩展信源同样可以采取霍夫曼编码方法。因为霍夫曼码是紧致码，所以编码后单个信源符号所编得的平均码长随N的增加很快接近于极限值信源的熵。电气信息工程学院)()(CLCL1)()()

35、(SHCLSHrr4.7.4 费诺（Fano）码费诺编码也是一种常见的信源编码方法。费诺码不是最佳的编码方法，但有时也可得到最佳码的性能。费诺码的编码程序如下：（1）信源符号以概率递减的次序排列起来，将排列好的信源符号划分成两大组，使每组的概率之和接近于相等，并各赋予一个二元码符号“0”和“1 ” ；（2）将每一大组的信源符号再分成两组，使同一组的两个小组的概率之和接近于相等，再分别赋予一个二元码符号。电气信息工程学院4.7.4 费诺（Fano）码（3）依次下去，直至每个小组只剩一个信源符号为止。例 设有一单符号离散信源对该信源编二进制费诺码。电气信息工程学院123456,()0.320.22

36、80.04XxxxxxxP X4.7.4 费诺（Fano）码该信源的熵为平均码长为编码效率为本例中费诺编码有较高的编码效率。费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。电气信息工程学院621()( )log( )2.35(/)iiiH Xp xp x 比特 符号)(4 . 2)(61信源符号二元码符号iiilxpL%9 .974 . 235. 2)(LXH4.7.4 费诺（Fano）码费诺码的编码方法实际上是一种构造码树的方法，所以费诺码是即时码 。费诺码考虑了信源的统计特性，使概率大的信源符号能对应码长短

37、的码字。从而有效地提高了编码效率。费诺编码方法不一定使短码得到充分利用。尤其当信源符号较多时，若有一些符号概率分布很接近时，分两大组的组合方法会很多。可能某种分大组的结果，会使后面小组的“概率和”相差较远，使平均码长增加。费诺码不一定是最佳码。 电气信息工程学院4.7.5香农费诺埃利斯码香农-费诺-埃利斯(Shannon-Fano-Elias)编码方法，是采用信源符号的累积分布函数来分配码字的。设信源符号集 ，定义累积分布函数：定义修正的累积分布函数：电气信息工程学院qaaaA,21kiikikAaaaPaF1,)()(11,)(21)()()(kiikkikAaaaPaPaFSF4.7.5香

38、农费诺埃利斯码累积分布函数为每台阶的上界值。而台阶的高度为 的值， 的值正处于对应于 台阶的中点当 ，知道了 就能确定信源符号为 ,因此可用 的值作为符号 的码字。电气信息工程学院1234561.0)(2aF)(3aP)(kaFi)(iaP)(kaFka)()(bFaFba 时)(kaFkaS )(kaFka4.7.5香农费诺埃利斯码每个信源符号ak所编码的码字对应的区域都没有重叠，码组满足前缀条件，为即时码。用二进数表示 ，一般为无限位二进制数。取小数后l(ak)位，即截去后面的位数，得 的近似值 ，并用这l(ak)位二进数作为ak的码字。其中 表示取l位使小于等于x的数。一般取电气信息工程

39、学院)(kaF)(kaF)()(kalkaF lx1)(1log)(kkaPal4.7.5香农费诺埃利斯码例 离散无记忆信源 ，它的香农费诺埃利斯码表如下：平均码长信源熵电气信息工程学院4321,ssssS 信源概率F(S) 的二进数码长码字Ws1s2s3s250.1250.250.750.8751.00.1250.50.81250.93750.0010.100.11010.111132440011011011111)(SF)(SF1)(1log)(sPsl)(75. 2信源符号码符号L)(75. 1)(信源符号比特SH4.7.5香农费诺埃利斯码例 给出另一信源 的香农费

40、诺埃利斯码平均码长电气信息工程学院54321,sssssS 信源概率F(S) 的二进数码长码字Ws1s2s3s4s50.250.250. 51.00.1250.3750.60.7750.9250.0010.01133444001011100111001110)(SF)(SF1)(1log)(sPsl00111 .00011110. 00110111. 0)(5 . 3信源符号码符号L一些结论霍夫曼码、费诺码、香费埃码都考虑了信源的统计特性，使经常出现的信源符号对应较短的码字，使信源的平均码长缩短，从而实现了对信源的压缩；霍夫曼码和费诺码的编码方法都不

41、惟一；费诺码比较适合于对分组概率相等或接近的信源编码；霍夫曼码对信源的统计特性没有特殊要求，编码效率比较高，对编码设备的要求也比较简单，因此综合性能优于费诺码和香费埃码。电气信息工程学院4.8几种实用的无失真信源编码方法在实际编码压缩技术中，常常结合实际信源情况，在压缩技术上给以改进，使便于操作和软硬件实现，本节介绍几种实用的无失真信源编码的方法。4.8.1 MH码MH（Modified Huffman），即修正的霍夫曼编码，MH编码是用于黑白二值文件传真的数据压缩，1997年被CCITT推荐为传真机一维压缩编码的国际标准。电气信息工程学院4.8.1 MH码文件传真是指一般文件、图纸、手写稿、

42、表格、报纸等文件的传真。它们是黑白二值的，也就是信源是二元信源q=2。文件图纸根据清晰度的要求来决定空间扫描分辨率，将文件图纸在空间上离散化。分辨率越高，分的越细，质量越高。国际规定，A4（210mm297mm）幅面文件应该有1188或2376条扫描线，每条扫描线有1728个像素的扫描分辨率（相当于垂直4或8线/mm，水平8点/mm）。电气信息工程学院4.8.1 MH码因此，A4文件纸约有2.05M像素/公文纸或4.1M像素/公文纸，从节省传送时间和存储空间来说，必须进行数据压缩。MH编码是一维编码方案，即对一行一行的数据进行编码。它将游程编码和霍夫曼编码相结合，是一种标准的改进霍夫曼码。从文

43、件来看，每行中会出现连续个“白”像素或连续个“黑”像素，同一符号出现而形成字符串的长度称之为游程长度。电气信息工程学院4.8.1 MH码MH码分别对“白”、“黑”的不同游程长度进行霍夫曼编码，形成黑、白两张码表。编、译码通过查表进行。每行总是从白色游程开始（如第一像素为黑色，则此长度可设为零）。如游程长度超过63个像素则分成两部分：前面是组合基干码，后为结尾码。修正MH编码一次只压缩一扫描行，各行独立不相关，因此是一种一维编码方案。电气信息工程学院4.8.1 MH码例 设某页传真文件中某一扫描行的像素点为|17白|5黑|55白|10黑|1641白|该行HM码为101011|0011|01011

44、0000|0000100|010010101|00101010|EOL数据压缩比：1728/5432，压缩率很高。电气信息工程学院4.8.2算术编码算术编码不同于霍夫曼码，它是非分组码。它从全序列出发，考虑符号之间的依赖关系来进行编码的。霍夫曼码 必须对二元信源的N次扩展信源进行编码时，才能使平均码长很快接近信源的熵，编码效率才高，而MH码的码表非常的庞大。问题，对于很长的信源符号序列是否存在简单有效的编码方法呢？电气信息工程学院4.8.2算术编码由香费埃推广得到的算术编码就可以达到这个目的。下面举例说明算术码是如何具体编码的。例 设二元无记忆信源对二元序列 做算术编码。解：电气信息工程学院4

45、3411,0)(21ppsPS11111100S2662)41 ()43() 1 ()0()(PPsP7)(1logsPl4.8.2算术编码信源符号序列s的累积分布函数：从上式得得C0.1101010 得s的码字为1101010电气信息工程学院syyPsF)()(111101001001. 082202. 0)43(1)111111(1)11111100()11111101()11111110()11111111(1)(1)111110()11110()1110()110()10()0()(6PPPPPyPPPPPPPsFsy4.8.2算术编码编码效率为可见这种按全序列进行编码，随着信源序列n的增长，效率还会增高