85信源编码-北邮信息论课件

信源编码信源编码贺志强贺志强信源编码：信源编码：将信源符号序列按一定的数学规律映射将信源符号序列按一定的数学规律映射成由码符号组成的码序列的过程成由码符号组成的码序列的过程成由码符号组成的码序列的过程。成由码符号组成的码序列的过程。信源译码信源译码根据码序列恢复信源序列的过程根据码序列恢复信源序列的过程信源译码：信源译码：根据码序列恢复信源序列的过程。根据码序列恢复信源序列的过程。无失真信源编码：无失真信源编码：即信源符号可以通过编码序列即信源符号可以通过编码序列无差错地恢复无差错地恢复无差错地恢复。无差错地恢复。（适用于离散信源的编码）（适用于离散信源的编码）限失真信源编码：限失真信源编码：信源符号不能通过编码序列无信源符号不能通过编码序列无差错地恢复差错地恢复差错地恢复。差错地恢复。（可以把差错限制在某一个限度内）（可以把差错限制在某一个限度内）信源编码的目的：提高传输有效性，即用尽可能短的码符信源编码的目的：提高传输有效性，即用尽可能短的码符号序列来代表信源符号号序列来代表信源符号号序列来代表信源符号。号序列来代表信源符号。无失真信源编码定理证明，如果对信源序列进行编码，当无失真信源编码定理证明，如果对信源序列进行编码，当序列长度足够长时序列长度足够长时存在无失真编码使得传送每信源符号存在无失真编码使得传送每信源符号序列长度足够长时序列长度足够长时，存在无失真编码使得传送每信源符号，存在无失真编码使得传送每信源符号所需的比特数接近信源的熵。因此，采用有效的信源编码所需的比特数接近信源的熵。因此，采用有效的信源编码会使信息传输效率得到提高会使信息传输效率得到提高会使信息传输效率得到提高。会使信息传输效率得到提高。概述概述一、信源编码器一、信源编码器二、信源编码的分类二、信源编码的分类三分组码三分组码三、分组码三、分组码信源编码器信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器分组码单符号信源编码器符号集符号集AA编为符号集符号集AA1{,,}qaaiica编为1{,,}qcc编码器编码器码字集合码字集合信源序列信源序列{}bb码符号集码符号集1{,}rbb信源译码器信源译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器分组码单符号译码器1{,,}qcc译码器译码器信源序列信源序列码字集合码字集合1{,,}qaa译码器译码器码符号集码符号集1{,}rbb码符号集码符号集简单信源编码器简单信源编码器摩尔斯信源编码器摩尔斯信源编码器将英文字母变成摩尔斯电码将英文字母变成摩尔斯电码将摩尔斯电码变成二进码将摩尔斯电码变成二进码信源编码器信源编码器（（11））信源编码器信源编码器（（22））（（11））信源符号信源符号{{英文字母英文字母}}（（22））二进信道二进信道码符号集码符号集点、划、字母间隔、单词间隔点、划、字母间隔、单词间隔信道基本符号信道基本符号{{00，，1}1}符号点划字母间隔单词间隔电平+-+++---------二进代码10111000000000摩尔斯信源编码器摩尔斯信源编码器原信源的原信源的NN次扩展码次扩展码原信源的原信源的次扩展码次扩展码将将NN个信源符号编成一个码字。相当于对原信源个信源符号编成一个码字。相当于对原信源的的NN次扩展源的信源符号进行编码。次扩展源的信源符号进行编码。例例信源信源X={0,1}X={0,1}的二次扩展源的二次扩展源XX22的符号集为：的符号集为：{00011011}{00011011}对对XX编码即为原信源编码即为原信源XX的二的二{00,01,10,11}{00,01,10,11}。对。对XX22编码，即为原信源编码，即为原信源XX的二的二次扩展码。次扩展码。信源编码的分类信源编码的分类概率匹配编码概率匹配编码：信源符号的概率已知。：信源符号的概率已知。概率匹配编码概率匹配编码：信源符号的概率已知。：信源符号的概率已知。分组码：先分组再编码。在分组码中，每一个码字仅与当前输入的信源符号组有关，与其他信源符号无关。包括定长码变长码（编码费诺编码）包括：定长码、变长码（Huffman编码、费诺编码）非分组码：码序列中的符号与信源序列中的符号无确定通用编通用编信符号的概率未知信符号的概率未知非分码码序列中的符号与信源序列中的符号无确定的对应关系。例如算术编码。通用编码通用编码：信源符号的概率未知。：信源符号的概率未知。信源编码信源编码信源编码信源编码按信源序列和编码器输出的关系按信源序列和编码器输出的关系分组码分组码非分组码非分组码按信源序列和编码器输出的关系按信源序列和编码器输出的关系先分组再编码先分组再编码先分组再编码先分组再编码无确定的对应关系无确定的对应关系定定长长变变长长编码器编码器信源序列信源序列编码序列编码序列长长码码长长码码每个码字每个码字仅与仅与当前输当前输编码器编码器每一个码字每一个码字仅与仅与当前输当前输入的信源符号组有关入的信源符号组有关例如算术编码就是非分组码例如算术编码就是非分组码分组码分组码与非分组码的显著区别：分组码中包含与非分组码的显著区别：分组码中包含码字码字与非分码的著别分码中含与非分码的著别分码中含码字码字Y必要条件各码字各码字都不相同？都不相同？Y非奇异码非奇异码唯一可译唯一可译N不同的消息序不同的消息序列不会生成相列不会生成相奇异码奇异码列不会生成相列不会生成相同的码序列同的码序列无失真编码无失真编码无失真编码无失真编码即时码与非即时码即时码与非即时码即时码与非即时码即时码与非即时码只要接收到只要接收到只要接收到只要接收到每个码字的每个码字的昀后一个符昀后一个符非即时码非即时码昀后个符昀后个符号可立即将号可立即将该码字译出？该码字译出？N即码即码Y即时码即时码优点译码延迟小优点译码延迟小即时码即时码优点：译码延迟小优点：译码延迟小异前置码异前置码异前码异前码设设为长度为为长度为的码字，即的码字，即，，称称为为的前置的前置kxk1,,kkxxxx)1(kjxxx称称为为的前置。的前置。一个码中无任何码字是其他码字的前置一个码中无任何码字是其他码字的前置异前置码是唯一可译码异前置码是唯一可译码kx)1(21kjxxxj异前置码是唯可译码异前置码是唯可译码异前置码与即时码是等价的异前置码与即时码是等价的逗号码逗号码用一个特定的码符号表示所有码字的结尾用一个特定的码符号表示所有码字的结尾逗号码是唯一可译码逗号码是唯一可译码逗号码是唯一可译码逗号码是唯一可译码例例设信源符号集为设信源符号集为{a,b,c,d},{a,b,c,d},采用采用66种分组种分组编码如下表分析每个码的唯可译性编码如下表分析每个码的唯可译性编码如下表，分析每一个码的唯一可译性编码如下表，分析每一个码的唯一可译性符号码A码B码C码D码E码F符号码A码B码C码D码E码Fa0000010b0101100101即时码即时码b0101100101c11010110001011d101111111000101111010cc等长等长异前置码异前置码逗号码逗号码00表示开头表示开头非奇异非奇异1010baba等长等长异前置码异前置码逗号码逗号码00表示开头表示开头唯一可译唯一可译一些结论一些结论变长码变长码定长码定长码只要非奇异，就唯一可译只要非奇异，就唯一可译非奇异且异前置就唯一可译非奇异且异前置就唯一可译速率变化速率变化设置缓冲器设置缓冲器速率恒定速率恒定不需缓冲器不需缓冲器受误码影响大受误码影响大,,逗号码除外逗号码除外码长已知码长已知容易同步容易同步容易产生差错传播容易产生差错传播无差错传播无差错传播码树码树码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的重要工具之一码树是表示信源编码码字的要具码树是表示信源编码码字的要具根节点根节点叶子叶子例例一个码一个码CC包含包含44个码字：个码字：{1,01,000,001},{1,01,000,001},试用码树来表示试用码树来表示试用码树来表示试用码树来表示采用二进制码树采用二进制码树解：解：采用二进制码树采用二进制码树解：解：00（（000000））000011RR001111（（0101））（（001001））RR1111（（11））（（0101））一些结论一些结论在码树中，在码树中，nn阶节点的个数昀多为阶节点的个数昀多为nr例：例：22进码树中，进码树中，rr阶节点数目昀多为阶节点数目昀多为r2非奇异码字总能与码树建立一一对应的关系非奇异码字总能与码树建立一一对应的关系非奇异码字能与码树建对应的关系非奇异码字能与码树建对应的关系定长码定长码本节主要内容本节主要内容本节主要内容本节主要内容无失真编码条件无失真编码条件一、无失真编码条件一、无失真编码条件二、信源序列分组定理二、信源序列分组定理定定三、定长码信源编码定理三、定长码信源编码定理无失真编码条件无失真编码条件对于定长码对于定长码,,只要非奇异就唯一可译。这就要只要非奇异就唯一可译。这就要求求码字的数目不少于被编码的信源序列的个数码字的数目不少于被编码的信源序列的个数单信源符号编码单信源符号编码设信源设信源XX包含包含qq个符号，码符号集包含的符号数为个符号，码符号集包含的符号数为rr单信源符号编码：单信源符号编码：lrq码长码长qNN长信源符号序列编码（长信源符号序列编码（NN次扩展码）次扩展码）平均每个信平均每个信源符号所需源符号所需qNlrqlNllog或符号所需符号所需码符号数码符号数rNqlog例例英文字母英文字母2626个加个加11个空格可看成共个空格可看成共2727个符号的信个符号的信源。源。如对单符号进行编码：如对单符号进行编码：l5755427lll取l2275755.427logl，l取但是，如果采用适当的信源编码，理论上但是，如果采用适当的信源编码，理论上每信源符号所需二进码符号数可以远小于上面每信源符号所需二进码符号数可以远小于上面的值，的值，在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵的值，的值，在理想情况下可以压缩到接近信源的熵在理想情况下可以压缩到接近信源的熵1.41.4左右。本节就是从理论上证明这种压缩是可左右。本节就是从理论上证明这种压缩是可以实现的以实现的以实现的。以实现的。信源序列分组定理信源序列分组定理N总可以找到离散无记忆信源离散无记忆信源的信源序列长度为0NN0N总可以找到00，任意给定都可以分成两组0使得使得①②所有符号序序列出现的概率满足：)(xp所有符号序列出现概率之和小于序列出现的概率满足：x)(xp)()(log1XHxp之和小于)()(logXHxpN(523)(5.2.3)证：设信源符号集证：设信源符号集为，各符号出现的概率分别为，为长度为的序列为中符号12{,,}qAaaaip12NxxxxNNxa为长度为的序列，为中符号出现的次数。将信源序列按下列原则分成两：、，其中，12NxxxxNiNxia1G2G，其中，：2G1G{:x,1,,}iiNpiqN：其它}根据大数定律，当序列足够长时，信源符号2G{:xia根据大数定律，当序列足够长时，信源符号出现的次数接近。因此，中的序列的符号出现的次数符合大数定律，称典型序列。iiNp1G现的次数符合大数定律，称典型序列。可以看出随的不同而改变G可以看出，随的不同而改变。设，则对于中的信源符号，有1G1xGxiaN或其中,1,iiNpiqNiiiNp1或，其中由于信源是无记忆的，所以的概率为的自信息负值为iipN1ix)(xpNN＝，的自信息负值为：qNqNpp11xqiiipNxp1log)(log1()logqiiiiNpp()logqiiNHXNp1i所以log()()logqpxHXp所以1()logiiiHXpN