无失真信源编码资料.pptx

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

1、会计学1无失真信源编码资料无失真信源编码资料2 2/100/100一、一、一、一、概概概概述述述述二、定长码二、定长码二、定长码二、定长码三、变长码三、变长码三、变长码三、变长码四、哈夫曼编码四、哈夫曼编码四、哈夫曼编码四、哈夫曼编码主要内容主要内容主要内容主要内容 本章主要介绍无失真信源编码本章主要介绍无失真信源编码本章主要介绍无失真信源编码本章主要介绍无失真信源编码定理定理定理定理与一些重要的无失真信源编码与一些重要的无失真信源编码与一些重要的无失真信源编码与一些重要的无失真信源编码方法方法方法方法五、几种实用的信源编码方法五、几种实用的信源编码方法五、几种实用的信源编码方法五、几种实用的

2、信源编码方法第1页/共99页3 3/100/100信源编码：信源编码：信源编码：信源编码：将将将将信源符号信源符号信源符号信源符号序列按一定的数学规律映射成由序列按一定的数学规律映射成由序列按一定的数学规律映射成由序列按一定的数学规律映射成由码符号码符号码符号码符号组成的码序列的过程。组成的码序列的过程。组成的码序列的过程。组成的码序列的过程。信源译码：信源译码：信源译码：信源译码：根据码序列恢复信源序列的过程。根据码序列恢复信源序列的过程。根据码序列恢复信源序列的过程。根据码序列恢复信源序列的过程。无失真信源编码：无失真信源编码：无失真信源编码：无失真信源编码：即信源符号可以通过编码序列无差

3、错地恢复。即信源符号可以通过编码序列无差错地恢复。即信源符号可以通过编码序列无差错地恢复。即信源符号可以通过编码序列无差错地恢复。（适用于离散信源的编码）（适用于离散信源的编码）限失真信源编码：限失真信源编码：限失真信源编码：限失真信源编码：信源符号不能通过编码序列无差错地恢复。信源符号不能通过编码序列无差错地恢复。信源符号不能通过编码序列无差错地恢复。信源符号不能通过编码序列无差错地恢复。（可以把差错限制在某一个限度内）（可以把差错限制在某一个限度内）第2页/共99页4 4/100/100信源编码的目的：信源编码的目的：信源编码的目的：信源编码的目的：提高传输有效性提高传输有效性提高传输有效

4、性提高传输有效性，即用尽可能短的码符，即用尽可能短的码符，即用尽可能短的码符，即用尽可能短的码符号序列来代表信源符号。号序列来代表信源符号。号序列来代表信源符号。号序列来代表信源符号。无失真信源编码定理证明了：无失真信源编码定理证明了：无失真信源编码定理证明了：无失真信源编码定理证明了：如果对信源序列进行编码，如果对信源序列进行编码，如果对信源序列进行编码，如果对信源序列进行编码，当序列长度足够长时当序列长度足够长时当序列长度足够长时当序列长度足够长时 ，存在无失真编码使得传送每信源符，存在无失真编码使得传送每信源符，存在无失真编码使得传送每信源符，存在无失真编码使得传送每信源符号所需的码元数

5、接近信源的熵。号所需的码元数接近信源的熵。号所需的码元数接近信源的熵。号所需的码元数接近信源的熵。因此，采用有效的信源编因此，采用有效的信源编因此，采用有效的信源编因此，采用有效的信源编码会使信息传输效率得到提高。码会使信息传输效率得到提高。码会使信息传输效率得到提高。码会使信息传输效率得到提高。第3页/共99页5 5/100/1005.1 5.1 概述概述概述概述本节主要内容本节主要内容本节主要内容本节主要内容一、一、一、一、信源信源信源信源编码编码器器器器二、二、二、二、信源信源信源信源编码编码的分的分的分的分类类三、分组码三、分组码三、分组码三、分组码第4页/共99页6 6/100/10

6、05.1.1 5.1.1 信源编码器信源编码器信源编码器信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器编码器编码器信源序列信源序列信源序列信源序列码符号集码符号集码符号集码符号集码字集合码字集合码字集合码字集合符号集符号集符号集符号集A A第5页/共99页7 7/100/100信源译码器信源译码器信源译码器信源译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器译码器译码器信源序列信源序列信源序列信源序列码符号集码符号集码符号集码符号集码字集合码字集合码字集合码字集合第6页/共99页8 8/100/100摩尔斯信源编

7、码器摩尔斯信源编码器摩尔斯信源编码器摩尔斯信源编码器信源编码器信源编码器（1 1）信源符号信源符号信源符号信源符号 英文字母英文字母英文字母英文字母 码符号集码符号集码符号集码符号集点、划、字母间隔、单词间隔点、划、字母间隔、单词间隔点、划、字母间隔、单词间隔点、划、字母间隔、单词间隔信道基本符号信道基本符号信道基本符号信道基本符号 0 0，11 简单信源编码器简单信源编码器简单信源编码器简单信源编码器信源编码器信源编码器（2 2）二进信道二进信道二进信道二进信道将英文字母变成摩尔斯电码将英文字母变成摩尔斯电码将英文字母变成摩尔斯电码将英文字母变成摩尔斯电码将摩尔斯电码变成二进码将摩尔斯电码变

8、成二进码将摩尔斯电码变成二进码将摩尔斯电码变成二进码 符号 点 划 字母间隔 单词间隔 电平+-+-二进代码 1 0111000000000第7页/共99页9 9/100/100原信源的原信源的原信源的原信源的NN次扩展码次扩展码次扩展码次扩展码将将将将NN个信源符号编成一个码字。相当于对原信源的个信源符号编成一个码字。相当于对原信源的个信源符号编成一个码字。相当于对原信源的个信源符号编成一个码字。相当于对原信源的NN次扩展源的信源符号进行编码。次扩展源的信源符号进行编码。次扩展源的信源符号进行编码。次扩展源的信源符号进行编码。例例例例信源信源信源信源X=0,1X=0,1的二次扩展源的二次扩展

9、源的二次扩展源的二次扩展源X X22的符号集为：的符号集为：的符号集为：的符号集为：00,01,10,1100,01,10,11。对。对。对。对X X2 2编码，即为原信源编码，即为原信源编码，即为原信源编码，即为原信源X X的二次扩展码。的二次扩展码。的二次扩展码。的二次扩展码。第8页/共99页1010/100/1005.1.2 5.1.2 信源编码的分类信源编码的分类信源编码的分类信源编码的分类概率匹配编码概率匹配编码概率匹配编码概率匹配编码：信源符号的概率已知。：信源符号的概率已知。：信源符号的概率已知。：信源符号的概率已知。通用编码通用编码通用编码通用编码：信源符号的概率未知。：信源符

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

11、信源序列和编码器输出的关系按信源序列和编码器输出的关系按信源序列和编码器输出的关系先分组再编码先分组再编码先分组再编码先分组再编码定长码定长码变长码变长码每一个码字每一个码字每一个码字每一个码字仅与仅与仅与仅与当前输当前输当前输当前输入的信源符号组有关入的信源符号组有关入的信源符号组有关入的信源符号组有关编码器编码器信源序列信源序列信源序列信源序列编码序列编码序列编码序列编码序列例如算术编码就是非分组码例如算术编码就是非分组码例如算术编码就是非分组码例如算术编码就是非分组码无确定的对应关系无确定的对应关系无确定的对应关系无确定的对应关系第10页/共99页1212/100/1005.1.35.1

12、.3 分组码分组码分组码分组码与非分组码的显著区别：分组码中包含与非分组码的显著区别：分组码中包含与非分组码的显著区别：分组码中包含与非分组码的显著区别：分组码中包含码字码字码字码字各码字各码字各码字各码字都不相同？都不相同？都不相同？都不相同？Y YN N非奇异码非奇异码奇异码奇异码唯一可译唯一可译不同的消息序不同的消息序不同的消息序不同的消息序列不会生成相列不会生成相列不会生成相列不会生成相同的码序列同的码序列同的码序列同的码序列无失真编码无失真编码无失真编码无失真编码必要条件必要条件第11页/共99页1313/100/100即时码与非即时码即时码与非即时码即时码与非即时码即时码与非即时码

13、只要接收到只要接收到只要接收到只要接收到每个码字的每个码字的每个码字的每个码字的最后一个符最后一个符最后一个符最后一个符号可立即将号可立即将号可立即将号可立即将该码字译出？该码字译出？该码字译出？该码字译出？Y Y即时码即时码N N非即时码非即时码优点：译码延迟小优点：译码延迟小优点：译码延迟小优点：译码延迟小第12页/共99页1414/100/100异前置码异前置码异前置码异前置码vv设设设设 为长度为为长度为为长度为为长度为 的码字，即的码字，即的码字，即的码字，即 ，称称称称 为为为为 的前置。的前置。的前置。的前置。vv一个码中无任何码字是其他码字的前置一个码中无任何码字是其他码字的前

14、置一个码中无任何码字是其他码字的前置一个码中无任何码字是其他码字的前置vv 异前置码是唯一可译码异前置码是唯一可译码异前置码是唯一可译码异前置码是唯一可译码vv 异前置码异前置码异前置码异前置码与与与与即时码即时码即时码即时码是等价的是等价的是等价的是等价的逗号码逗号码逗号码逗号码vv 用一个特定的码符号表示所有码字的结尾用一个特定的码符号表示所有码字的结尾用一个特定的码符号表示所有码字的结尾用一个特定的码符号表示所有码字的结尾vv 逗号码是唯一可译码逗号码是唯一可译码逗号码是唯一可译码逗号码是唯一可译码第13页/共99页1515/100/100例例例例设信源符号集为设信源符号集为设信源符号集

15、为设信源符号集为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 11 11 111 0001 0111非奇异非奇异非奇异非奇异唯一可译唯一可译唯一可译唯一可译1010babac c等长等长等长等长异前置码异前置码异前置码异前置码 逗号码逗号码

16、逗号码逗号码 0 0 0 0表示开头表示开头表示开头表示开头即时码即时码即时码即时码第14页/共99页1616/100/100一些结论一些结论一些结论一些结论变长码变长码变长码变长码定长码定长码定长码定长码只要非奇异，就唯一可译只要非奇异，就唯一可译只要非奇异，就唯一可译只要非奇异，就唯一可译非奇异且异前置就唯一可译非奇异且异前置就唯一可译非奇异且异前置就唯一可译非奇异且异前置就唯一可译速率变化速率变化速率变化速率变化设置缓冲器设置缓冲器设置缓冲器设置缓冲器速率恒定速率恒定速率恒定速率恒定不需缓冲器不需缓冲器不需缓冲器不需缓冲器受误码影响大受误码影响大受误码影响大受误码影响大,逗号码除外逗号码

17、除外逗号码除外逗号码除外码长已知码长已知码长已知码长已知容易同步容易同步容易同步容易同步容易产生差错传播容易产生差错传播容易产生差错传播容易产生差错传播无差错传播无差错传播无差错传播无差错传播第15页/共99页1717/100/100码树码树码树码树码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的重要工具之一叶子叶子叶子叶子根节点根节点根节点根节点 第16页/共99页1818/100/100例例例例一个码一个码一个码一个码CC包含包含包含包含4 4个码字：个码字：个码字：个码字：1,01,000,001,1,0

18、1,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）（001001001001）（000000000000）第17页/共99页1919/100/100一些结论一些结论一些结论一些结论非奇异码字总能与码树建立一一对应的关系非奇异码字总能与码树建立一一对应的关系非奇异码字总能与码树建立一一对应的关系非奇异码字总能与码树建立一一对应的关系在码树中，

19、在码树中，在码树中，在码树中，n n阶节点的个数最多为阶节点的个数最多为阶节点的个数最多为阶节点的个数最多为vv例：例：例：例：2 2进码树中，进码树中，进码树中，进码树中，n n阶节点数目最多为阶节点数目最多为阶节点数目最多为阶节点数目最多为第18页/共99页2020/100/1005.2 5.2 定长码定长码定长码定长码本节主要内容本节主要内容本节主要内容本节主要内容一、无失真编码条件一、无失真编码条件一、无失真编码条件一、无失真编码条件 二、二、二、二、信源序列分信源序列分信源序列分信源序列分组组定理定理定理定理三、三、三、三、定定定定长码长码信源信源信源信源编码编码定理定理定理定理第1

20、9页/共99页2121/100/1005.2.1 5.2.1 无失真编码条件无失真编码条件无失真编码条件无失真编码条件 对于定长码对于定长码对于定长码对于定长码,只要非奇异就唯一可译。这就要求只要非奇异就唯一可译。这就要求只要非奇异就唯一可译。这就要求只要非奇异就唯一可译。这就要求码字的数目不少于被编码的信源序列的个数码字的数目不少于被编码的信源序列的个数码字的数目不少于被编码的信源序列的个数码字的数目不少于被编码的信源序列的个数vv设信源设信源设信源设信源X X包含包含包含包含q q个符号，码符号集包含的符号数为个符号，码符号集包含的符号数为个符号，码符号集包含的符号数为个符号，码符号集包含

21、的符号数为r r 单信源符号编码：单信源符号编码：单信源符号编码：单信源符号编码：码长码长码长码长NN长信源符号序列编码（长信源符号序列编码（长信源符号序列编码（长信源符号序列编码（NN次扩展码）次扩展码）次扩展码）次扩展码）平均每个信平均每个信平均每个信平均每个信源符号所需源符号所需源符号所需源符号所需码符号数码符号数码符号数码符号数第20页/共99页2222/100/100例例例例英文字母英文字母英文字母英文字母2626个加个加个加个加1 1个空格可看成共个空格可看成共个空格可看成共个空格可看成共2727个符号的信源。个符号的信源。个符号的信源。个符号的信源。如对单符号进行编码：如对单符号

22、进行编码：如对单符号进行编码：如对单符号进行编码：但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值，但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值，但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值，但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面的值，在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵1.41.4左右左右左右左右。本节就是从理论上证明这种压缩是可以实现的。本节就是从理论

23、上证明这种压缩是可以实现的。本节就是从理论上证明这种压缩是可以实现的。本节就是从理论上证明这种压缩是可以实现的。第21页/共99页2323/100/1005.2.2 5.2.2 信源序列分组定理信源序列分组定理信源序列分组定理信源序列分组定理定理定理定理定理5.2.1 5.2.1 离散无记忆信源离散无记忆信源离散无记忆信源离散无记忆信源使得使得使得使得所有序列出所有序列出现概率之和现概率之和小于小于序列序列 出现的概率出现的概率 满足：满足：(5.2.3)第22页/共99页2424/100/100证：我们先证明（我们先证明（5.2.35.2.3）式。）式。设信源符号集设信源符号集为为 ，各符号

24、出现的概率分别为各符号出现的概率分别为 ，为长度为为长度为 的序列，的序列，为为 中符号中符号出现的次数。出现的次数。将信源序列按下列原则分成两将信源序列按下列原则分成两 ：、，其中，其中，：（5.2.45.2.4）：其它其它 根据根据大数定律大数定律，当序列足够长时，信源符号，当序列足够长时，信源符号出现的次数接近出现的次数接近 。因此，。因此，中的序列的符号出中的序列的符号出 现的次数符合大数定律，称典型序列。现的次数符合大数定律，称典型序列。第23页/共99页2525/100/100从（从（5.2.45.2.4）中可以看出，）中可以看出，随随 的不同而改变。的不同而改变。设设 ，则对于，

25、则对于 中的信源符号中的信源符号 ，有，有 或或 ，其中，其中 由于信源是无记忆的，所以由于信源是无记忆的，所以 的概率为的概率为 ，的自信息负值为：的自信息负值为：第24页/共99页2626/100/100所以所以选择选择 ，使得，使得 （5.2.55.2.5）则式（则式（5.2.35.2.3）成立。）成立。第25页/共99页2727/100/100下面证明定理的后半部分。设下面证明定理的后半部分。设 ，根据（根据（5.5.2.32.3）式，有）式，有 （5.2.65.2.6）因为信源是无记忆的，所以因为信源是无记忆的，所以 ，得到得到 （5.2.75.2.7）将（将（5.2.75.2.7）

26、代入（）代入（5.2.65.2.6），得），得 （5.2.85.2.8）第26页/共99页2828/100/100令令 ,可得可得 ,所以所以根据根据ChebyshevChebyshev不等式：不等式：，其中，其中 为随机变量；这样就得到：为随机变量；这样就得到：（5.2.95.2.9）其中其中 ，所以，所以，（5.2.105.2.10）第27页/共99页2929/100/100其中，自信息的方差其中，自信息的方差 （5.2.115.2.11）取取 ，则当，则当 ，第28页/共99页3030/100/100总结总结总结总结对离散无记忆信源，给定对离散无记忆信源，给定对离散无记忆信源，给定对离散

27、无记忆信源，给定 ，令，令，令，令取取取取 ；那么对长度为；那么对长度为；那么对长度为；那么对长度为NN的信源序列，满足下式的为典型序列，否则为非典型序列。的信源序列，满足下式的为典型序列，否则为非典型序列。的信源序列，满足下式的为典型序列，否则为非典型序列。的信源序列，满足下式的为典型序列，否则为非典型序列。定理说明，当定理说明，当定理说明，当定理说明，当NN足够大时，典型序列足够大时，典型序列足够大时，典型序列足够大时，典型序列 的的的的的值接近信源的熵的值接近信源的熵的值接近信源的熵的值接近信源的熵对于有记忆的马氏源，定理对于有记忆的马氏源，定理对于有记忆的马氏源，定理对于有记忆的马氏源

28、，定理5.2.15.2.1也成立也成立也成立也成立第29页/共99页3131/100/100渐进均分特性渐进均分特性渐进均分特性渐进均分特性典型序列的概率估计典型序列的概率估计典型序列的概率估计典型序列的概率估计设取设取设取设取2 2为底为底为底为底简记为简记为简记为简记为:vv当当当当 足够小时，每个典型序列的概率足够小时，每个典型序列的概率足够小时，每个典型序列的概率足够小时，每个典型序列的概率 接近，接近，接近，接近，其偏其偏其偏其偏差不大于差不大于差不大于差不大于 ；vv此时序列的长度需要很大此时序列的长度需要很大此时序列的长度需要很大此时序列的长度需要很大第30页/共99页3232/

29、100/100典型序列的个数估计典型序列的个数估计典型序列的个数估计典型序列的个数估计设设设设 为为为为 中序列的个数中序列的个数中序列的个数中序列的个数先估计上界：先估计上界：先估计上界：先估计上界：利用概率估计的下界利用概率估计的下界利用概率估计的下界利用概率估计的下界再估计下界：再估计下界：再估计下界：再估计下界：利用概率估计的上界利用概率估计的上界利用概率估计的上界利用概率估计的上界第31页/共99页3333/100/100渐近均分特性渐近均分特性渐近均分特性渐近均分特性当当当当 取值很小时（取值很小时（取值很小时（取值很小时（N N要求很大），对于典型序列要求很大），对于典型序列要求

30、很大），对于典型序列要求很大），对于典型序列 含意：含意：含意：含意：当长度当长度当长度当长度N N足够大时：足够大时：足够大时：足够大时：vv典型序列接近等概率典型序列接近等概率典型序列接近等概率典型序列接近等概率 ，数目近似于数目近似于数目近似于数目近似于vv非典型序列出现的概率接近为零非典型序列出现的概率接近为零非典型序列出现的概率接近为零非典型序列出现的概率接近为零vv （以概率收敛）（以概率收敛）（以概率收敛）（以概率收敛）第32页/共99页3434/100/100结论结论结论结论设信源序列数为设信源序列数为设信源序列数为设信源序列数为 ，编码序列数为，编码序列数为，编码序列数为，编

31、码序列数为 。如果每个信源序列都至少要有一个码字，即。如果每个信源序列都至少要有一个码字，即。如果每个信源序列都至少要有一个码字，即。如果每个信源序列都至少要有一个码字，即需要需要需要需要 。但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际。但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际。但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际。但是，随着信源序列长度的增加，基本上是典型序列出现，这样我们仅考虑对典型序列的编码，所以实际需要需要需要需要 个码字。而当信源

32、的熵小于个码字。而当信源的熵小于个码字。而当信源的熵小于个码字。而当信源的熵小于 时，就会使得码字的长度减小。时，就会使得码字的长度减小。时，就会使得码字的长度减小。时，就会使得码字的长度减小。第33页/共99页3535/100/1005.2.3 5.2.3 定长码信源编码定理定长码信源编码定理定长码信源编码定理定长码信源编码定理定理定理定理定理5.2.2 5.2.2 离散无记忆信源的熵为离散无记忆信源的熵为离散无记忆信源的熵为离散无记忆信源的熵为H(X)H(X)，码符号集的符号数为，码符号集的符号数为，码符号集的符号数为，码符号集的符号数为r r，将长度为，将长度为，将长度为，将长度为NN的

33、信源序列编成长度为的信源序列编成长度为的信源序列编成长度为的信源序列编成长度为l l的码序列。只要满足：的码序列。只要满足：的码序列。只要满足：的码序列。只要满足：则当则当则当则当NN足够大时，译码差错可以任意小足够大时，译码差错可以任意小足够大时，译码差错可以任意小足够大时，译码差错可以任意小(）；若上述不等式不满足，肯定会出现译码差错。）；若上述不等式不满足，肯定会出现译码差错。）；若上述不等式不满足，肯定会出现译码差错。）；若上述不等式不满足，肯定会出现译码差错。第34页/共99页3636/100/100证明思路证明思路证明思路证明思路 在编码时，可以使所有典型序列都有对应的码字，而最坏

34、的情况是所有的非典型序列无对应的码字。在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的非典型序列无对应的码字。在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的非典型序列无对应的码字。在编码时，可以使所有典型序列都有对应的码字，而最坏的情况是所有的非典型序列无对应的码字。典型序列的个数小于典型序列的个数小于典型序列的个数小于典型序列的个数小于正定理正定理正定理正定理第35页/共99页3737/100/100证明思路证明思路证明思路证明思路 若不满足上式若不满足上式若不满足上式若不满足上式逆定理逆定理逆定理逆定理=已知编码序列条件下信源序列的不确定性，如果无差错译码

35、已知编码序列条件下信源序列的不确定性，如果无差错译码已知编码序列条件下信源序列的不确定性，如果无差错译码已知编码序列条件下信源序列的不确定性，如果无差错译码,该不确定性为零。该不确定性为零。该不确定性为零。该不确定性为零。第36页/共99页3838/100/100相关定义相关定义相关定义相关定义定长码编码速率定长码编码速率定长码编码速率定长码编码速率vv它表示编码后，一个信源符号平均所携带的最大信息它表示编码后，一个信源符号平均所携带的最大信息它表示编码后，一个信源符号平均所携带的最大信息它表示编码后，一个信源符号平均所携带的最大信息量，也可以理解为传送一个信源符号平均所需的比特量，也可以理解

36、为传送一个信源符号平均所需的比特量，也可以理解为传送一个信源符号平均所需的比特量，也可以理解为传送一个信源符号平均所需的比特数。数。数。数。vv压缩码率实际就是减小编码速率。压缩码率实际就是减小编码速率。压缩码率实际就是减小编码速率。压缩码率实际就是减小编码速率。第37页/共99页3939/100/100编码效率编码效率编码效率编码效率vvNH(X)NH(X)表示表示表示表示N N长信源序列的所包含的信息量长信源序列的所包含的信息量长信源序列的所包含的信息量长信源序列的所包含的信息量vvl lr r表示码序列所能携带的最大信息量。表示码序列所能携带的最大信息量。表示码序列所能携带的最大信息量。

37、表示码序列所能携带的最大信息量。vv由定理由定理由定理由定理5.3.25.3.2可知，当可知，当可知，当可知，当N N足够大时，足够大时，足够大时，足够大时，可以接近可以接近可以接近可以接近1 1vv由渐近均分特性，当由渐近均分特性，当由渐近均分特性，当由渐近均分特性，当 减小时，减小时，减小时，减小时，增加。增加。增加。增加。vv压缩码率和提高编码效率是同样的含义。压缩码率和提高编码效率是同样的含义。压缩码率和提高编码效率是同样的含义。压缩码率和提高编码效率是同样的含义。第38页/共99页4040/100/100信息传输速率：每个传输符号所含信息量信息传输速率：每个传输符号所含信息量信息传输

38、速率：每个传输符号所含信息量信息传输速率：每个传输符号所含信息量vv对于二进编码，编码效率与信息传输速率数值相同。对于二进编码，编码效率与信息传输速率数值相同。对于二进编码，编码效率与信息传输速率数值相同。对于二进编码，编码效率与信息传输速率数值相同。第39页/共99页4141/100/100相关结论相关结论相关结论相关结论无失真信源编码的另一种表述无失真信源编码的另一种表述无失真信源编码的另一种表述无失真信源编码的另一种表述 如果编码速率如果编码速率如果编码速率如果编码速率 ，则存在无失真编码。，则存在无失真编码。，则存在无失真编码。，则存在无失真编码。反之，肯定有失真。反之，肯定有失真。反

39、之，肯定有失真。反之，肯定有失真。第40页/共99页4242/100/100编码效率与熵的关系编码效率与熵的关系编码效率与熵的关系编码效率与熵的关系vv信源给定后，若要求编码效率越高，信源给定后，若要求编码效率越高，信源给定后，若要求编码效率越高，信源给定后，若要求编码效率越高，N N 越大，要求越大，要求越大，要求越大，要求译码差错越低，译码差错越低，译码差错越低，译码差错越低，N N值也越大。值也越大。值也越大。值也越大。第41页/共99页4343/100/100例例例例5.2.15.2.15.2.15.2.1一离散无记忆信源的模型如下，要求用二元定长码编码，已知一离散无记忆信源的模型如下

40、，要求用二元定长码编码，已知一离散无记忆信源的模型如下，要求用二元定长码编码，已知一离散无记忆信源的模型如下，要求用二元定长码编码，已知 ，试估计信源序列的最小长度，试估计信源序列的最小长度，试估计信源序列的最小长度，试估计信源序列的最小长度NN。信源的熵信源的熵信源的熵信源的熵解：解：解：解：自信息方差自信息方差自信息方差自信息方差两种含义不现实：编码时延大，信源要求长第42页/共99页4444/100/100结论结论结论结论 要达到一定误码要求，信源序列长度需很长，所以编码器难于实现。要达到一定误码要求，信源序列长度需很长，所以编码器难于实现。要达到一定误码要求，信源序列长度需很长，所以编

41、码器难于实现。要达到一定误码要求，信源序列长度需很长，所以编码器难于实现。第43页/共99页4545/100/1005.3 5.3 变长码变长码变长码变长码本节主要内容本节主要内容本节主要内容本节主要内容一、异前置码的性质一、异前置码的性质一、异前置码的性质一、异前置码的性质二、二、二、二、变长码变长码信源信源信源信源编码编码定理定理定理定理第44页/共99页4646/100/1005.3.1 5.3.1 异前置码的性质异前置码的性质异前置码的性质异前置码的性质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

42、）（001001001001）（000000000000）变长码可用变长码可用变长码可用变长码可用非全码树非全码树非全码树非全码树来描述。下图就是一个异前置码的码树。来描述。下图就是一个异前置码的码树。来描述。下图就是一个异前置码的码树。来描述。下图就是一个异前置码的码树。只有端点（树叶）对应码字。只有端点（树叶）对应码字。只有端点（树叶）对应码字。只有端点（树叶）对应码字。vv对应码字的端点与根之间不对应码字的端点与根之间不对应码字的端点与根之间不对应码字的端点与根之间不能有其它的节点作为码字能有其它的节点作为码字能有其它的节点作为码字能有其它的节点作为码字vv端点不能向上延伸再构成新端点不

43、能向上延伸再构成新端点不能向上延伸再构成新端点不能向上延伸再构成新码字码字码字码字全码树图中每个叶子节点都在最底层，从左至右排列第45页/共99页4747/100/100定理定理定理定理5.3.1 5.3.1 (Kraft(Kraft定理定理定理定理)若信源符号数为若信源符号数为若信源符号数为若信源符号数为q q，码符号数为，码符号数为，码符号数为，码符号数为r r，对信源符号进行编码，相应码长度为，对信源符号进行编码，相应码长度为，对信源符号进行编码，相应码长度为，对信源符号进行编码，相应码长度为 ，则异前置码存在的，则异前置码存在的，则异前置码存在的，则异前置码存在的充要条件充要条件充要条

44、件充要条件是：是：是：是：第46页/共99页4848/100/100证明思路证明思路证明思路证明思路 充分性：充分性：充分性：充分性：做一个做一个做一个做一个 阶全树，树叶总数阶全树，树叶总数阶全树，树叶总数阶全树，树叶总数取取取取 阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶阶的任一节点作为第一个码字，去掉的树叶第47页/共99页4949/100/100证明思路证明思路证明思路证明思路 必要性：必要性：必要性：必要性：构造一个码全树，最高阶为码字最大长度构造一个码全树，最高阶为码字最大长度构造一个码全树，最高阶为码字最大长

45、度构造一个码全树，最高阶为码字最大长度对于阶为对于阶为对于阶为对于阶为 的节点，占用的树叶数为的节点，占用的树叶数为的节点，占用的树叶数为的节点，占用的树叶数为 vv当码满足当码满足当码满足当码满足 Kraft Kraft Kraft Kraft 不等式时，未必就是异前置码不等式时，未必就是异前置码不等式时，未必就是异前置码不等式时，未必就是异前置码vv异前置码并不唯一，例如异前置码并不唯一，例如异前置码并不唯一，例如异前置码并不唯一，例如 0,1 0,1 0,1 0,1 交换。交换。交换。交换。第48页/共99页5050/100/100例例例例5.4.15.4.15.4.15.4.1下表列出

46、了下表列出了下表列出了下表列出了3 3种变长码的编码，并给出了对应每个码的所有的码长种变长码的编码，并给出了对应每个码的所有的码长种变长码的编码，并给出了对应每个码的所有的码长种变长码的编码，并给出了对应每个码的所有的码长 和具有同一码长的码字的个数，其中码符号集为和具有同一码长的码字的个数，其中码符号集为和具有同一码长的码字的个数，其中码符号集为和具有同一码长的码字的个数，其中码符号集为0,1,2,30,1,2,3。试问对每个码是否存在相应的异前置码？。试问对每个码是否存在相应的异前置码？。试问对每个码是否存在相应的异前置码？。试问对每个码是否存在相应的异前置码？码字 码 个数 码 长 码1

47、码2码3 1 3 2 1 2 3 7 7 3 3 3 3 4 3 3 7 5 4 5 4第49页/共99页5151/100/100解：解：解：解：利用利用利用利用 Kraft Kraft 不等式来验证。不等式来验证。不等式来验证。不等式来验证。对于码对于码对于码对于码1 1：存在相应的异前置码存在相应的异前置码存在相应的异前置码存在相应的异前置码同理：同理：同理：同理：码码码码2 2不存在相应的异前置码；码不存在相应的异前置码；码不存在相应的异前置码；码不存在相应的异前置码；码3 3存在相应的异前置码。存在相应的异前置码。存在相应的异前置码。存在相应的异前置码。实际上，可以用码树来验证，方法更

48、简单。实际上，可以用码树来验证，方法更简单。实际上，可以用码树来验证，方法更简单。实际上，可以用码树来验证，方法更简单。注意：只是存在异前置码！注意：只是存在异前置码！注意：只是存在异前置码！注意：只是存在异前置码！第50页/共99页5252/100/100定理定理定理定理5.3.25.3.2证明略证明略证明略证明略 若一个码是唯一可译码且码字长为若一个码是唯一可译码且码字长为若一个码是唯一可译码且码字长为若一个码是唯一可译码且码字长为 则必满足则必满足则必满足则必满足KraftKraft不等式，即：不等式，即：不等式，即：不等式，即：q q：信源符号数信源符号数信源符号数信源符号数r r：码

49、符号数：码符号数：码符号数：码符号数第51页/共99页5353/100/100推论推论推论推论5.3.15.3.1 任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。任意唯一可译码都可用异前置码代替，而不改变码字的任一长度。结论结论结论结论 满足满足满足满足kraftkraft不等式并不等式并不等式并不等式并不一定唯一可译不一定唯一可译不一定唯一可译不一定唯一可译，因为奇异码可能满足，因为奇异码可能满足，因为奇异码可能满足，因为奇异码可能满足kraftkraft不等式。不

50、等式。不等式。不等式。第52页/共99页5454/100/1005.3.2 5.3.2 变长码信源编码定理变长码信源编码定理变长码信源编码定理变长码信源编码定理单信源符号编码的单信源符号编码的单信源符号编码的单信源符号编码的平均码长平均码长平均码长平均码长：表示平均每个信源符号所需码符号的个数表示平均每个信源符号所需码符号的个数表示平均每个信源符号所需码符号的个数表示平均每个信源符号所需码符号的个数对于对于对于对于NN次扩展源编码，原信源符号平均码长为次扩展源编码，原信源符号平均码长为次扩展源编码，原信源符号平均码长为次扩展源编码，原信源符号平均码长为第53页/共99页5555/100/100