无失真信源编码.pptx

《无失真信源编码.pptx》由会员分享，可在线阅读，更多相关《无失真信源编码.pptx（99页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 1/100/100一、一、概概概概述述述述二、定长码二、定长码三、变长码三、变长码四、哈夫曼编码四、哈夫曼编码主要内容 本章主要介绍无失真信源编码本章主要介绍无失真信源编码定理定理与一些重要的无失真信源编码与一些重要的无失真信源编码方方法法五、几种实用的信源编码方法五、几种实用的信源编码方法第1页/共99页2 2/100/100信源编码：信源编码：将将信源符号信源符号序列按一定的数学规律映射成由序列按一定的数学规律映射成由码符号码符号组成的码组成的码序列的过程。序列的过程。信源译码：信源译码：根据码序列恢复信源序列的过程。根据码序列恢复信源序列的过程。无失真信源编码：无失真信源编码：即信源

2、符号可以通过编码序列无差错地恢复。即信源符号可以通过编码序列无差错地恢复。（适用于离散信源的编码）（适用于离散信源的编码）限失真信源编码：限失真信源编码：信源符号不能通过编码序列无差错地恢复。信源符号不能通过编码序列无差错地恢复。（可以把差错限制在某一个限度内）（可以把差错限制在某一个限度内）第2页/共99页3 3/100/100信源编码的目的：信源编码的目的：提高传输有效性提高传输有效性，即用尽可能短的码符，即用尽可能短的码符号序列来代表信源符号。号序列来代表信源符号。无失真信源编码定理证明了：无失真信源编码定理证明了：如果对信源序列进行编码，如果对信源序列进行编码，当序列长度足够长时当序列

3、长度足够长时 ，存在无失真编码使得传送每信源符，存在无失真编码使得传送每信源符号所需的码元数接近信源的熵。号所需的码元数接近信源的熵。因此，采用有效的信源编因此，采用有效的信源编码会使信息传输效率得到提高。码会使信息传输效率得到提高。第3页/共99页4 4/100/1005.1 概述本节主要内容本节主要内容本节主要内容本节主要内容一、一、信源信源信源信源编码编码器器器器二、二、信源信源信源信源编码编码的分的分的分的分类类三、分组码三、分组码第4页/共99页5 5/100/100信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器编码器编码器信源序列

4、信源序列码符号集码符号集码字集合码字集合符号集符号集A A第5页/共99页6 6/100/100信源译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器译码器译码器信源序列信源序列码符号集码符号集码字集合码字集合第6页/共99页7 7/100/100摩尔斯信源编码器摩尔斯信源编码器摩尔斯信源编码器摩尔斯信源编码器信源编码器信源编码器（1 1）信源符号信源符号 英文字母英文字母 码符号集码符号集点、划、字母间隔、单词间隔点、划、字母间隔、单词间隔信道基本符号信道基本符号 0 0，11 简单信源编码器信源编码器信源编码器（2 2）二进信道二进信道将英文字母变成摩尔斯电码将

5、英文字母变成摩尔斯电码将摩尔斯电码变成二进码将摩尔斯电码变成二进码 符号 点 划 字母间隔 单词间隔 电平+-+-二进代码 1 0111000000000第7页/共99页8 8/100/100原信源的原信源的N N次扩展码次扩展码将将N N个信源符号编成一个码字。相当于对原信源的个信源符号编成一个码字。相当于对原信源的N N次扩展源的信源符号进次扩展源的信源符号进行编码。行编码。例例信源信源X=0,1X=0,1的二次扩展源的二次扩展源X X2 2的符号集为：的符号集为：00,01,10,1100,01,10,11。对。对X X2 2编码，编码，即为原信源即为原信源X X的二次扩展码。的二次扩展

6、码。第8页/共99页9 9/100/100信源编码的分类概率匹配编码概率匹配编码：信源符号的概率已知。：信源符号的概率已知。通用编码通用编码：信源符号的概率未知。：信源符号的概率未知。n分组码：先分组再编码。在分组码中，每一个码字仅与分组码：先分组再编码。在分组码中，每一个码字仅与当前输入的信源当前输入的信源符号组符号组有关，与其他信源符号无关。有关，与其他信源符号无关。包括：定长码、变长码（包括：定长码、变长码（Huffman编码、费诺编码编码、费诺编码）n非分组码：码序列中的符号与信源序列中的符号无确定非分组码：码序列中的符号与信源序列中的符号无确定的对应关系。例如算术编码。的对应关系。例

7、如算术编码。第9页/共99页1010/100/100信源编码信源编码分组码分组码非分组码非分组码按信源序列和编码器输出的关系按信源序列和编码器输出的关系先分组再编码先分组再编码定长定长码码变长变长码码每一个码字每一个码字仅与仅与当前输当前输入的信源符号组有关入的信源符号组有关编码器编码器信源序列信源序列编码序列编码序列例如算术编码就是非分组码例如算术编码就是非分组码无确定的对应关系无确定的对应关系第10页/共99页1111/100/100 分组码与非分组码的显著区别：分组码中包含与非分组码的显著区别：分组码中包含码字码字各码字各码字都不相同？都不相同？Y YN N非奇异码非奇异码奇异码奇异码唯

8、一可译唯一可译不同的消息序不同的消息序列不会生成相列不会生成相同的码序列同的码序列无失真编码无失真编码无失真编码无失真编码必要条件必要条件第11页/共99页1212/100/100即时码与非即时码即时码与非即时码只要接收到只要接收到每个码字的每个码字的最后一个符最后一个符号可立即将号可立即将该码字译出？该码字译出？Y Y即时码即时码N N非即时码非即时码优点：译码延迟小优点：译码延迟小第12页/共99页1313/100/100异前置码异前置码vv设设 为长度为为长度为 的码字，即的码字，即 ，称称 为为 的前置。的前置。vv一个码中无任何码字是其他码字的前置一个码中无任何码字是其他码字的前置v

9、v 异前置码是唯一可译码异前置码是唯一可译码vv 异前置码异前置码与与即时码即时码是等价的是等价的逗号码逗号码vv 用一个特定的码符号表示所有码字的结尾用一个特定的码符号表示所有码字的结尾vv 逗号码是唯一可译码逗号码是唯一可译码第13页/共99页1414/100/100例例设信源符号集为设信源符号集为a,b,c,d,a,b,c,d,采用采用6 6种分组编码如下表，分析每一个码种分组编码如下表，分析每一个码的唯一可译性的唯一可译性5.15.15.15.1符号 码A码B码C码D码E码Fa 0 0 00 0 1 0b 0 1 01 10 01 01c 1 10 10 110 001 011d 10

10、 11 11 111 0001 0111非奇异非奇异唯一可译唯一可译1010babac c等长等长等长等长异前置码异前置码异前置码异前置码 逗号码逗号码逗号码逗号码 0 0 0 0表示开头表示开头表示开头表示开头即时码即时码第14页/共99页1515/100/100一些结论一些结论一些结论一些结论变长码变长码变长码变长码定长码定长码定长码定长码只要非奇异，就唯一可译只要非奇异，就唯一可译非奇异且异前置就唯一可译非奇异且异前置就唯一可译速率变化速率变化设置缓冲器设置缓冲器速率恒定速率恒定不需缓冲器不需缓冲器受误码影响大受误码影响大,逗号码除外逗号码除外码长已知码长已知容易同步容易同步容易产生差错

11、传播容易产生差错传播无差错传播无差错传播第15页/共99页1616/100/100码树码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的重要工具之一叶子叶子叶子叶子根节点根节点根节点根节点 第16页/共99页1717/100/100例例一个码一个码C C包含包含4 4个码字：个码字：1,01,000,001,1,01,000,001,试用码树来表示试用码树来表示5.25.25.25.2采用二进制码树采用二进制码树解：解：解：解：R R R R1 1 1 10 0 0 00 0 0 00 0 0 01 1 1 11 1 1 1（1 1 1 1）（01010101）（0010010010

12、01）（000000000000）第17页/共99页1818/100/100一些结论一些结论一些结论一些结论非奇异码字总能与码树建立一一对应的关系非奇异码字总能与码树建立一一对应的关系在码树中，在码树中，n n阶节点的个数最多为阶节点的个数最多为vv例：例：2 2进码树中，进码树中，n n阶节点数目最多为阶节点数目最多为第18页/共99页1919/100/1005.2 定长码本节主要内容本节主要内容本节主要内容本节主要内容一、无失真编码条件一、无失真编码条件 二、二、信源序列分信源序列分信源序列分信源序列分组组定理定理定理定理三、三、定定定定长码长码信源信源信源信源编码编码定理定理定理定理第1

13、9页/共99页2020/100/100无失真编码条件 对于定长码对于定长码,只要非奇异就唯一可译。这就要求只要非奇异就唯一可译。这就要求码字的数目不少于被编码码字的数目不少于被编码的信源序列的个数的信源序列的个数vv设信源设信源X X包含包含q q个符号，码符号集包含的符号数为个符号，码符号集包含的符号数为r r 单信源符号编码：单信源符号编码：码长码长码长码长N N长信源符号序列编码（长信源符号序列编码（N N次扩展码）次扩展码）平均每个信平均每个信平均每个信平均每个信源符号所需源符号所需源符号所需源符号所需码符号数码符号数码符号数码符号数第20页/共99页2121/100/100例例英文字

14、母英文字母2626个加个加1 1个空格可看成共个空格可看成共2727个符号的信源。个符号的信源。如对单符号进行编码：如对单符号进行编码：但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值，可以远小于上面的值，在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵1.41.4左右左右。本节就是从理论上证明这种压缩是可以实现的。本节就是从理论上证明这种压缩是可以实现的。第21页/共99页2222/100/100信源序列分组定理定理定理离散无记忆信源离散无记忆信源使得使得所有序列出现概率之和小于

15、序列 出现的概率 满足：第22页/共99页2323/100/100证：我们先证明（5.2.3）式。设信源符号集为 ，各符号出现的概率分别为 ，为长度为 的序列，为 中符号出现的次数。将信源序列按下列原则分成两：、，其中，：（5.2.4）：其它 根据大数定律，当序列足够长时，信源符号出现的次数接近 。因此，中的序列的符号出 现的次数符合大数定律，称典型序列。第23页/共99页2424/100/100从（5.2.4）中可以看出，随 的不同而改变。设 ，则对于 中的信源符号 ，有 或 ，其中 由于信源是无记忆的，所以 的概率为 ，的自信息负值为：第24页/共99页2525/100/100所以选择 ，

16、使得 （5.2.5）则式（5.2.3）成立。第25页/共99页2626/100/100下面证明定理的后半部分。设 ，根据（5.2.3）式，有 （5.2.6）因为信源是无记忆的，所以 ，得到 （5.2.7）将（5.2.7）代入（5.2.6），得 （5.2.8）第26页/共99页2727/100/100令 ,可得 ,所以根据Chebyshev不等式：，其中 为随机变量；这样就得到：（5.2.9）其中 ，所以，（5.2.10）第27页/共99页2828/100/100其中，自信息的方差 （5.2.11）取 ，则当 ，第28页/共99页2929/100/100总结总结总结总结对离散无记忆信源，给定对离

17、散无记忆信源，给定 ，令，令取取 ；那么对长度为；那么对长度为N N的信源序列，满足下式的为典型序列，否则为非的信源序列，满足下式的为典型序列，否则为非典型序列。典型序列。定理说明，当定理说明，当N N足够大时，典型序列足够大时，典型序列 的的的值接近信源的熵的值接近信源的熵对于有记忆的马氏源，定理也成立对于有记忆的马氏源，定理也成立第29页/共99页3030/100/100渐进均分特性典型序列的概率估计典型序列的概率估计设取设取2 2为底为底简记为简记为:vv当当 足够小时，每个典型序列的概率足够小时，每个典型序列的概率 接近，接近，其偏差其偏差不大于不大于 ；vv此时序列的长度需要很大此时

18、序列的长度需要很大第30页/共99页3131/100/100典型序列的个数估计典型序列的个数估计设设 为为 中序列的个数中序列的个数先估计上界：先估计上界：利用概率估计的下界利用概率估计的下界再估计下界：再估计下界：利用概率估计的上界利用概率估计的上界第31页/共99页3232/100/100渐近均分特性渐近均分特性当当 取值很小时（取值很小时（N N要求很大），对于典型序列要求很大），对于典型序列 含意：含意：当长度当长度N N足够大时：足够大时：vv典型序列接近等概率典型序列接近等概率 ，数目近似于数目近似于vv非典型序列出现的概率接近为零非典型序列出现的概率接近为零vv （以概率收敛）（

19、以概率收敛）第32页/共99页3333/100/100结论结论结论结论设信源序列数为设信源序列数为 ，编码序列数为，编码序列数为 。如果每个信源序列都至少要有一个码字，。如果每个信源序列都至少要有一个码字，即即需要需要 。但是，随着信源序列长度的增加，基本上是典型序列出现，这样。但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际我们仅考虑对典型序列的编码，所以实际需要需要 个码字。而当信源的熵个码字。而当信源的熵小于小于 时，就会使得码字的长度减小。时，就会使得码字的长度减小。第33页/共99页3434/100/100定长码信源编码定理定理定理5.2.

20、2 5.2.2 离散无记忆信源的熵为离散无记忆信源的熵为H(X)H(X)，码符号集的符号数为，码符号集的符号数为r r，将长度为，将长度为N N的信源序的信源序列编成长度为列编成长度为l l的码序列。只要满足：的码序列。只要满足：则当则当N N足够大时，译码差错可以任意小足够大时，译码差错可以任意小(）；若上述不等式不满足，肯定会）；若上述不等式不满足，肯定会出现译码差错。出现译码差错。第34页/共99页3535/100/100证明思路证明思路 在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的非典型序列无对应的码字

21、。非典型序列无对应的码字。典型序列的个数小于典型序列的个数小于典型序列的个数小于典型序列的个数小于正定理正定理正定理正定理第35页/共99页3636/100/100证明思路证明思路 若不满足上式若不满足上式若不满足上式若不满足上式逆定理逆定理逆定理逆定理=已知编码序列条件下信源序列的不确定性，如果无差错译码已知编码序列条件下信源序列的不确定性，如果无差错译码,该不确定性为该不确定性为零。零。第36页/共99页3737/100/100相关定义定长码编码速率定长码编码速率vv它表示编码后，一个信源符号平均所携带的最大信息量，它表示编码后，一个信源符号平均所携带的最大信息量，也可以理解为传送一个信源

22、符号平均所需的比特数。也可以理解为传送一个信源符号平均所需的比特数。vv压缩码率实际就是减小编码速率。压缩码率实际就是减小编码速率。第37页/共99页3838/100/100编码效率编码效率vvNH(X)NH(X)表示表示N N长信源序列的所包含的信息量长信源序列的所包含的信息量vvl lr r表示码序列所能携带的最大信息量。表示码序列所能携带的最大信息量。vv由定理可知，当由定理可知，当N N足够大时，足够大时，可以接近可以接近1 1vv由渐近均分特性，当由渐近均分特性，当 减小时，减小时，增加。增加。vv压缩码率和提高编码效率是同样的含义。压缩码率和提高编码效率是同样的含义。第38页/共9

23、9页3939/100/100信息传输速率：每个传输符号所含信息量信息传输速率：每个传输符号所含信息量vv对于二进编码，编码效率与信息传输速率数值相同。对于二进编码，编码效率与信息传输速率数值相同。第39页/共99页4040/100/100相关结论无失真信源编码的另一种表述无失真信源编码的另一种表述 如果编码速率如果编码速率 ，则存在无失真编码。，则存在无失真编码。反之，肯定有失真。反之，肯定有失真。第40页/共99页4141/100/100编码效率与熵的关系编码效率与熵的关系vv信源给定后，若要求编码效率越高，信源给定后，若要求编码效率越高，N N 越大，要求越大，要求译码差错越低，译码差错越

24、低，N N值也越大。值也越大。第41页/共99页4242/100/100例例一离散无记忆信源的模型如下，要求用二元定长码编码，已知一离散无记忆信源的模型如下，要求用二元定长码编码，已知 ，试估计信源序列的最小长度，试估计信源序列的最小长度N N。信源的熵信源的熵解：解：解：解：自信息方差自信息方差两种含义不现实：编码时延大，信源要求长第42页/共99页4343/100/100结论结论结论结论 要达到一定误码要求，信源序列长度需很长，所以编码器难于实现。要达到一定误码要求，信源序列长度需很长，所以编码器难于实现。第43页/共99页4444/100/1005.3 变长码本节主要内容本节主要内容本节

25、主要内容本节主要内容一、异前置码的性质一、异前置码的性质二、二、变长码变长码信源信源信源信源编码编码定理定理定理定理第44页/共99页4545/100/100异前置码的性质R R R R1 1 1 10 0 0 00 0 0 00 0 0 01 1 1 11 1 1 1（1 1 1 1）（01010101）（001001001001）（000000000000）变长码可用变长码可用非全码树非全码树来描述。下图就是一个异前置码的码树。来描述。下图就是一个异前置码的码树。只有端点（树叶）对应码字。只有端点（树叶）对应码字。vv对应码字的端点与根之间不对应码字的端点与根之间不能有其它的节点作为码字能

26、有其它的节点作为码字vv端点不能向上延伸再构成新端点不能向上延伸再构成新码字码字全码树图中每个叶子节点都在最底层，从左至右排列第45页/共99页4646/100/100定理定理5.3.1 5.3.1 (Kraft(Kraft定理定理)若信源符号数为若信源符号数为q q，码符号数为，码符号数为r r，对信源符号进行编码，相应码长度为，对信源符号进行编码，相应码长度为 ，则异前置码存在的，则异前置码存在的充要条件充要条件是：是：第46页/共99页4747/100/100证明思路证明思路 充分性：充分性：充分性：充分性：做一个做一个做一个做一个 阶全树，树叶总数阶全树，树叶总数阶全树，树叶总数阶全树

27、，树叶总数取取取取 阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶第47页/共99页4848/100/100证明思路证明思路 必要性：必要性：必要性：必要性：构造一个码全树，最高阶为码字最大长度构造一个码全树，最高阶为码字最大长度构造一个码全树，最高阶为码字最大长度构造一个码全树，最高阶为码字最大长度对于阶为对于阶为对于阶为对于阶为 的节点，占用的树叶数为的节点，占用的树叶数为的节点，占用的树叶数为的节点，占用的树叶数为 v当码满足当码满足当码满足当码满足 Kraft Kraft Kraf

28、t Kraft 不等式时，未必就是异前置码不等式时，未必就是异前置码不等式时，未必就是异前置码不等式时，未必就是异前置码v异前置码并不唯一，例如异前置码并不唯一，例如异前置码并不唯一，例如异前置码并不唯一，例如 0,1 0,1 0,1 0,1 交换。交换。交换。交换。第48页/共99页4949/100/100例例下表列出了下表列出了3 3种变长码的编码，并给出了对应每个码的所有的码长种变长码的编码，并给出了对应每个码的所有的码长 和具有同一码长的码字的个数，其中码符号集为和具有同一码长的码字的个数，其中码符号集为0,1,2,30,1,2,3。试问对。试问对每个码是否存在相应的异前置码？每个码是

29、否存在相应的异前置码？码字 码 个数 码 长 码1码2码3 1 3 2 1 2 3 7 7 3 3 3 3 4 3 3 7 5 4 5 4第49页/共99页5050/100/100解：解：解：解：利用利用 Kraft Kraft 不等式来验证。不等式来验证。对于码对于码1 1：存在相应的异前置码存在相应的异前置码同理：同理：码码2 2不存在相应的异前置码；码不存在相应的异前置码；码3 3存在相应的异前置码。存在相应的异前置码。实际上，可以用码树来验证，方法更简单。实际上，可以用码树来验证，方法更简单。注意：只是存在异前置码！注意：只是存在异前置码！第50页/共99页5151/100/100定理

30、定理5.3.25.3.2证明略证明略证明略证明略 若一个码是唯一可译码且码字长为若一个码是唯一可译码且码字长为 则必满足则必满足KraftKraft不等式，即：不等式，即：q q：信源符号数信源符号数r r：码符号数：码符号数第51页/共99页5252/100/100推论推论5.3.15.3.1 任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。结论结论结论结论 满足满足kraftkraft不等式并不等式并不一定唯一可译不一定唯一可译，因为奇异码可能满足，因为奇异码可能满足kraftkraft不等式。不等式。第52页/共99页5

31、353/100/100变长码信源编码定理单信源符号编码的单信源符号编码的平均码长平均码长：表示平均每个信源符号所需码符号的个数表示平均每个信源符号所需码符号的个数对于对于N N次扩展源编码，原信源符号平均码长为次扩展源编码，原信源符号平均码长为第53页/共99页5454/100/100定理定理5.3.3 5.3.3 单符号信源变长码编码定理单符号信源变长码编码定理 给定熵为给定熵为H(X)H(X)的离散无记忆信源的离散无记忆信源X X，用，用r r元码符号集对单信源符号进行编元码符号集对单信源符号进行编码，码，则存在唯一可译码，其平均码长满足：则存在唯一可译码，其平均码长满足：第54页/共99

32、页5555/100/100(1)证明不等式前半部证明思路证明思路 等式成立条件即即即即第55页/共99页5656/100/100(2)证明不等式后半部证明思路证明思路 第56页/共99页5757/100/100定理定理5.3.4 5.3.4 有限序列信源变长码编码定理有限序列信源变长码编码定理证明略证明略证明略证明略 若对长度为若对长度为N N的离散无记忆信源序列进行编码，则存在唯一可译码，且的离散无记忆信源序列进行编码，则存在唯一可译码，且使每信源符号平均码长满足使每信源符号平均码长满足：且对任何唯一可译码左边不等式都要满足。且对任何唯一可译码左边不等式都要满足。第57页/共99页5858/

33、100/100定理定理5.3.55.3.5证明略证明略证明略证明略 对于离散平稳遍历马氏源，有对于离散平稳遍历马氏源，有：第58页/共99页5959/100/100定理定理5.3.6 5.3.6 仙农第一定理仙农第一定理证明思路：证明思路：证明思路：证明思路：若对任意信源若对任意信源X X的的N N次扩展源次扩展源 进行编码，当进行编码，当N N足够大时，总能找到唯一足够大时，总能找到唯一可译的可译的r r进编码，使得进编码，使得X X的平均码长任意接近信源的熵的平均码长任意接近信源的熵 利用定理的不等式，就可得到定理的结利用定理的不等式，就可得到定理的结利用定理的不等式，就可得到定理的结利用

34、定理的不等式，就可得到定理的结果果果果第59页/共99页6060/100/100相关定义相关定义相关定义相关定义编码速率：编码速率：编码效率：编码效率：信息传输速率：信息传输速率：编码剩余度：编码剩余度：第60页/共99页6161/100/100vv对所有唯一可译码都要满足对所有唯一可译码都要满足vv无需一定满足，但存在这种关系，无需一定满足，但存在这种关系，通常希望越小越好通常希望越小越好一些结论一些结论一些结论一些结论平均码长的上、下界平均码长的上、下界 时，时，此时：，此时：vv各信源符号出现概率为各信源符号出现概率为 l li i为整数为整数vv每码元平均所带信息量为每码元平均所带信息

35、量为 ,码元符号独立且等概码元符号独立且等概第61页/共99页6262/100/100例例进行二元编码，即进行二元编码，即 ，求平均码长和编码效率；，求平均码长和编码效率；ii ii）编成）编成2 2次扩展码，信源序列与码序列的映射关系为：次扩展码，信源序列与码序列的映射关系为：求平均码长和编码效率。求平均码长和编码效率。解：解：解：解：1)1)1)1)第62页/共99页6363/100/100信源序列的概率：信源序列的概率：2)2)2)2)且：且：与例相比，可以看出，与例相比，可以看出，为得到同样编码效率所用的编码符号数比定长码小为得到同样编码效率所用的编码符号数比定长码小得多得多。因此容易

36、达到高的编码效率，是变长码的显著优点。因此容易达到高的编码效率，是变长码的显著优点。第63页/共99页6464/100/1005.4 哈夫曼编码本节主要内容本节主要内容本节主要内容本节主要内容一、二元哈夫曼编码一、二元哈夫曼编码二、二、多元哈夫曼多元哈夫曼多元哈夫曼多元哈夫曼编码编码三、马氏源的编码三、马氏源的编码第64页/共99页6565/100/100定理定理5.4.15.4.1 任意对于一个含任意对于一个含q q个符号的信源，存在最优的二进制码，其中有两个最个符号的信源，存在最优的二进制码，其中有两个最长的码字有相同的长度且仅最后一个码位有别，即其中一个的最末尾是长的码字有相同的长度且仅

37、最后一个码位有别，即其中一个的最末尾是0 0，而另一个的最末尾是，而另一个的最末尾是1 1（或者相反）（或者相反）若一个唯一可译码的平均码长小于所有其它唯一可译码，则称该码为若一个唯一可译码的平均码长小于所有其它唯一可译码，则称该码为最优最优码码(或紧致码或紧致码)。应注意：最优是唯一可译码之间的比较，因此它的平均码长应注意：最优是唯一可译码之间的比较，因此它的平均码长未必达到编码未必达到编码定理的下界定理的下界。二元哈夫曼编码第65页/共99页6666/100/100证明思路：证明思路：首先证明对于最优码，概率小的符号对应长度长的码字。首先证明对于最优码，概率小的符号对应长度长的码字。证明最

38、长的码字有两个长度相同，且只有最后一位不同。证明最长的码字有两个长度相同，且只有最后一位不同。一个最优码唯一可译一个最优码唯一可译 满足满足KraftKraft不等式不等式 存在与其同样存在与其同样码长的异前置码码长的异前置码第66页/共99页6767/100/100二元最优异前置码的构造方法二元最优异前置码的构造方法二元最优异前置码的构造方法二元最优异前置码的构造方法设信源设信源S S为为 ，对应的码字为，对应的码字为将概率最小的两个码符号将概率最小的两个码符号 合并，从而产生新的信源合并，从而产生新的信源S S 设设 ，对应的码字为，对应的码字为 。对新信源编码后，按下面的关系就可恢复原。

39、对新信源编码后，按下面的关系就可恢复原来信源的码字：来信源的码字：第67页/共99页6868/100/100证明思路：证明思路：设设若若 对信源对信源 是最优的异前置码，则是最优的异前置码，则 对信源对信源 也是最优的异前置码也是最优的异前置码对对S S，有，有第68页/共99页6969/100/100一些结论一些结论一些结论一些结论我们可以采用合并两个最小概率符号的方法，逐步地按这样的路线去编码：我们可以采用合并两个最小概率符号的方法，逐步地按这样的路线去编码：最后将最后将2 2字母信源分配字母信源分配0 0、1 1符号；然后可符号；然后可逐步反推逐步反推到原信源到原信源S S，从而得到信，

40、从而得到信源的最优编码。这种编码称做源的最优编码。这种编码称做二元二元HuffmanHuffman编码编码第69页/共99页7070/100/100例例一信源一信源S S的符号集的符号集A=A=，概率分别为：概率分别为：0 0.3.3，0.250.25，0.250.25，0.10.1，0.10.1；试对信源符号进行二元；试对信源符号进行二元HuffmanHuffman编码编码解：解：解：解：依次做信源依次做信源依次做信源依次做信源S S S S S S S S S S S S，最后将，最后将，最后将，最后将0 0 0 0、1 1 1 1符号符号符号符号分配分配分配分配给给给给S S S S，如

41、下图：，如下图：，如下图：，如下图：信源符号 码字 00 01 10 110 111第70页/共99页7171/100/100HuffmanHuffman编码方法编码方法编码方法编码方法将信源概率分布按大小依递减次序排列；合并将信源概率分布按大小依递减次序排列；合并两概率最小者，得到信新源；并分配两概率最小者，得到信新源；并分配 0,1 0,1 符号符号新信源若包含两个以上符号返回（新信源若包含两个以上符号返回（1 1），），否则否则到（到（3 3）从最后一级向前按顺序写出每信源符号所对应从最后一级向前按顺序写出每信源符号所对应的码字的码字第71页/共99页7272/100/100例例一信源一

42、信源S S的符号集的符号集A=A=，概率分别为：概率分别为：0 0.4.4，0.20.2，0.20.2，0.10.1，0.10.1；试对信源符号进行二元；试对信源符号进行二元HuffmanHuffman编码，并计算平均码长和编码效率编码，并计算平均码长和编码效率解：解：解：解：000110110111两种计算方法第72页/共99页7373/100/100一些结论一些结论一些结论一些结论HuffmanHuffman编码是最优码（或紧致码），是异前置码编码是最优码（或紧致码），是异前置码编码结果并不唯一，例如编码结果并不唯一，例如0 0、1 1可换，相同概率符号码字可换，但平均码长可换，相同概率符

43、号码字可换，但平均码长不变不变不一定达到编码定理下界，达下界条件为不一定达到编码定理下界，达下界条件为通常适用于通常适用于多元信源多元信源，对于，对于二元信源二元信源，必须采用合并符号的方法，才能得，必须采用合并符号的方法，才能得到较高的编码效率到较高的编码效率第73页/共99页7474/100/100例例例还可以用以下的方法编码：例还可以用以下的方法编码：01011011101111不变不变不变不变但码长的方差改变了但码长的方差改变了但码长的方差改变了但码长的方差改变了000110110111方法1方法2第74页/共99页7575/100/100一些结论一些结论一些结论一些结论 当码长的方差

44、小时，编码器所需缓冲器容量小。当码长的方差小时，编码器所需缓冲器容量小。因此要尽量减小码长的方因此要尽量减小码长的方差差。方法是：在编码方法是：在编码时，时，应使合并后的信源符号位于缩减信源符号尽可能高的应使合并后的信源符号位于缩减信源符号尽可能高的位置上（位置上（减少合并次数减少合并次数）。）。第75页/共99页7676/100/100否则，就利用上式计算出大于否则，就利用上式计算出大于q q的最小正整数的最小正整数s s。然后给信源增补零概率符号，。然后给信源增补零概率符号，使增补后的信源符号总数为使增补后的信源符号总数为s s。编码后，去掉这些零概率符号所对应的码字，。编码后，去掉这些零

45、概率符号所对应的码字，其余码字为所需码字其余码字为所需码字 通过观察可知，要使编码的通过观察可知，要使编码的平均码长最短平均码长最短，对应的码树要构成，对应的码树要构成满树满树是必要条是必要条件。对于件。对于r r元哈霍夫曼编码，从第元哈霍夫曼编码，从第n n阶的阶的1 1个节点到个节点到n+1n+1阶节点，增加的数目为阶节点，增加的数目为r-1r-1。因此，达到满树时，总的树叶数为：。因此，达到满树时，总的树叶数为：元哈夫曼编码非负整数非负整数码树图中每个中间节点后续的枝数为r时称满树;第76页/共99页7777/100/100例例一信源一信源S S的符号集的符号集A=A=概率分别为：概率分

46、别为：0 0.4,0.2,0.1,0.1,0.05,0.05.4,0.2,0.1,0.1,0.05,0.05,0.050.05,0.050.05；试对信源符号进行；试对信源符号进行3 3元哈夫曼编码，并计算平均码长和元哈夫曼编码，并计算平均码长和编码效率编码效率解：解：解：解：信源要增加信源要增加1 1个零概率符个零概率符号号第77页/共99页7878/100/100第78页/共99页7979/100/100决策树决策树 如果有如果有n n个互斥随机事件，概率分别为个互斥随机事件，概率分别为p pi i,现用某种测试方法分步对所选择现用某种测试方法分步对所选择的目标事件进行识别，要求具有最小的

47、决策平均次数，相当于对这些事件进的目标事件进行识别，要求具有最小的决策平均次数，相当于对这些事件进行行HuffmanHuffman编码。编码。Huffman编码的应用第79页/共99页8080/100/100决策树举例决策树举例例如，甲手中有例如，甲手中有4 4张纸牌，点数分别为张纸牌，点数分别为1 1、2 2、3 3、4 4，要求乙，要求乙猜：乙可以向甲提问题，甲只能用猜：乙可以向甲提问题，甲只能用是或否是或否来回答。求乙平来回答。求乙平均最少问几个问题可以猜到纸牌的点数和相应的策略。均最少问几个问题可以猜到纸牌的点数和相应的策略。(1)1(1)1、2 2、3 3、4 4的概率均为的概率均为

48、1/41/4的决策树；的决策树；(2)1(2)1、2 2、3 3、4 4的概率分别为的概率分别为1/21/2、1/41/4、1/81/8、1/81/8的决策树的决策树.vv首先首先HuffmanHuffman编码；编码；vvHuffmanHuffman编码码树变成决策树。编码码树变成决策树。vv决策的设计：每步决策结果应该与节点分支的概率匹配。决策的设计：每步决策结果应该与节点分支的概率匹配。第80页/共99页8181/100/100第第(1)(1)问问第81页/共99页8282/100/100第第(2)(2)问问第82页/共99页8383/100/100按状态编码按状态编码 根据马氏源的特性

49、，当前发出的符号所含信息量取决于当前的状态。这个根据马氏源的特性，当前发出的符号所含信息量取决于当前的状态。这个信息量可能很大也可能很小。例如，一个马氏源包含信息量可能很大也可能很小。例如，一个马氏源包含3 3个状态个状态aa，b b，cc，每，每个状态代表一个输出符号，状态转移矩阵如下：个状态代表一个输出符号，状态转移矩阵如下：马氏源可以采用按马氏源可以采用按状态编码状态编码和和多个符号合并编码多个符号合并编码下一个字母下一个字母b.cb.c出现出现等概等概包含的信息量包含的信息量最大最大下一个字母下一个字母必然出现必然出现b b包含的信息量包含的信息量为为0 0第83页/共99页8484/

50、100/1001.1.给定一个初始状态给定一个初始状态2.2.对每个状态对每个状态 ,根据转移概率根据转移概率 进行最优编码，例如进行最优编码，例如 HuffmanHuffman编码编码.3.3.设设 为对应的码表为对应的码表,其中规定其中规定信源符号信源符号 和码字和码字 的对应关系，记为的对应关系，记为按状态编码方法按状态编码方法第84页/共99页8585/100/100编码过程编码过程1.1.给定一信源序列给定一信源序列 ，设初始状态，设初始状态 2.2.用用 码表，查出码表，查出 对应的码字对应的码字 作为编码器输出，同时根据作为编码器输出，同时根据 得到下得到下一个状态一个状态 3.