第4章 无失真信源编码-第14讲.ppt

第第4 4章章 无失真信源编码无失真信源编码第一节第一节 编码的定义编码的定义第二节第二节 定长编码定理定长编码定理第三节第三节 变长编码定理变长编码定理第四节第四节 最佳编码最佳编码引言引言引言 编码分为编码分为信源编码信源编码和和信道编码信道编码，其中信源，其中信源编码又分为编码又分为无失真信源编码无失真信源编码和和限失真信源限失真信源编码编码。无失真信源编码无失真信源编码：适用于离散信源或数字：适用于离散信源或数字 信号。信号。限失真信源编码限失真信源编码：主要用于连续信源或模：主要用于连续信源或模拟信号，如语音、图像等信号的数字处理。拟信号，如语音、图像等信号的数字处理。香农信息论三大定理香农信息论三大定理:1.第一极限定理第一极限定理:无失真信源编码定理无失真信源编码定理.2.第二极限定理第二极限定理:信道编码定理（包括离信道编码定理（包括离散和连续信道）散和连续信道）.3.第三极限定理第三极限定理:限失真信源编码定理限失真信源编码定理.信源编码的主要任务是什么信源编码的主要任务是什么?由于信源符号之间存在分布由于信源符号之间存在分布不均匀不均匀和和相关性相关性，使得信源存在冗余度，信源编码的使得信源存在冗余度，信源编码的主要任务主要任务就就是减少冗余，提高编码效率。是减少冗余，提高编码效率。具体说，就是针对信源输出符号序列的统具体说，就是针对信源输出符号序列的统计特性，寻找一定的方法把信源输出符号序列计特性，寻找一定的方法把信源输出符号序列变换为最短的码字序列。变换为最短的码字序列。信源编码的基本途径信源编码的基本途径是什么是什么?信源编码的信源编码的基本途径基本途径有两个有两个:一是一是使序列中的各个符号尽可能地互相独立，即解使序列中的各个符号尽可能地互相独立，即解除相关性；除相关性；二是二是使编码中各个符号出现的概率尽可能地相等，使编码中各个符号出现的概率尽可能地相等，即概率均匀化。即概率均匀化。信源编码的基础是什么信源编码的基础是什么?信源编码的信源编码的基础基础是：两个编码定理。是：两个编码定理。即无失真编码定理和限失真编码定理。即无失真编码定理和限失真编码定理。编码定理证明编码定理证明：（1）必存在一种编码方法，使代码的平均长度必存在一种编码方法，使代码的平均长度可任意接近但不能低于符号熵可任意接近但不能低于符号熵（2）达到这目标的途径，就是使概率与码长匹达到这目标的途径，就是使概率与码长匹配。配。说明说明：（1）无失真编码或可逆编码只适用于离散信源。无失真编码或可逆编码只适用于离散信源。（2 2）对于连续信源，编成代码后就无法无失真）对于连续信源，编成代码后就无法无失真地恢复原来的连续值，因为后者的取值可有无地恢复原来的连续值，因为后者的取值可有无限多个。此时只能根据限失真编码定理进行限限多个。此时只能根据限失真编码定理进行限失真编码失真编码 。什么是分组码？什么是分组码？设设:源消息为符号序列源消息为符号序列Xi，序列中的每个符号取自于符号集序列中的每个符号取自于符号集A，。而而每每个个符符号号序序列列Xi依依照照固固定定的的码码表表映映射射成成一一个个码码字字Yi，这这样样的的码码称称为为分分组组码码，有有时时也也叫叫块块码码。只只有有分分组码才有对应的码表，而非分组码中则不存在码表。组码才有对应的码表，而非分组码中则不存在码表。第一节 编码的定义信源编码器L长序列长序列K长码字长码字图图4-1-1信源编码器信源编码器设设:信源输出的序列长度为信源输出的序列长度为1，即信源符号集，即信源符号集信源概率空间为：信源概率空间为：二元信道的信道基本符号集为二元信道的信道基本符号集为0，1。若将信源若将信源X通过一个二元信道传输，就必须通过一个二元信道传输，就必须把信源符号把信源符号xi变换成由变换成由0，1符号组成的码符号符号组成的码符号序列，即编码。可用不同的码符号序列，如所序列，即编码。可用不同的码符号序列，如所示。示。分组码的一些直观属性分组码的一些直观属性码码非分组码非分组码分组码分组码奇异码奇异码非奇异码非奇异码非唯一可译码非唯一可译码唯一可译码唯一可译码非即时码非即时码即时码（非延长码）即时码（非延长码）码树图A0100000000000001111111011111二进制码树二进制码树2000001111122222三进制码树三进制码树唯一可译码存在的充分和必要条件唯一可译码存在的充分和必要条件用用树树的的概概念念可可导导出出唯唯一一可可译译码码存存在在的的充充分分和和必必要要条条件件，即即各各码码字字的的长长度度Ki应应符符合合克克劳劳夫夫特特不等式：不等式：(4-1-1)式中，式中，m是进制数，是进制数，n是信源符号数。是信源符号数。无失真信源编码定理要研究的内容无失真信源编码定理要研究的内容 若信源输出符号序列的长度若信源输出符号序列的长度 ，即，即 变换成由变换成由K KL L个符号组成的码序列（码字个符号组成的码序列（码字)变换的要求变换的要求:(1)(1)能够无失真或无差错地从能够无失真或无差错地从Y恢复恢复X，也就是能正确地进行反变，也就是能正确地进行反变换或译码换或译码(2)传送传送Y时所需要的信息率最小时所需要的信息率最小 由由于于Y Yk k可可取取m m种种可可能能值值，即即平平均均每每个个符符号号输输出出的的最最大大信信息息量量为为logmlogm，K KL L长长码码字字的的最最大大信信息息量量为为K KL Llogmlogm。用用该该码码字字表表示示L L长长的的信信源源序序列列,则则送送出出一一个个信信源源符符号号所所需需要的信息率平均为要的信息率平均为:其中其中 是是Y Y所能编成的码字的个数。所能编成的码字的个数。信息率最小信息率最小，就是找到一种编码方式使，就是找到一种编码方式使 最小。最小。无失真信源编码定理要研究的内容无失真信源编码定理要研究的内容:(1)(1)最小信息率为多少时，才能得到无失真的译码？最小信息率为多少时，才能得到无失真的译码？(2)(2)若小于这个信息率是否还能无失真地译码？若小于这个信息率是否还能无失真地译码？定长编码定理定长编码定理由由L个符号组成的、每个符号的熵为个符号组成的、每个符号的熵为HL（X）的无记忆）的无记忆平稳信源符号序列平稳信源符号序列，可用，可用KL个符号个符号（每个符号有（每个符号有m种可能值）进行定长种可能值）进行定长编码。对任意编码。对任意，只要，只要则当则当L足够大时，必可使译码差错小于足够大时，必可使译码差错小于；反之，当；反之，当 时，译码差错一定是有限值，而当时，译码差错一定是有限值，而当L足够大时，译码几足够大时，译码几乎必定出错。乎必定出错。第二节 定长编码定理 说明说明（1）当编码器容许的输出信息率，也就是当每）当编码器容许的输出信息率，也就是当每个信源符号所必须输出的码长是个信源符号所必须输出的码长是时，只要时，只要，这种编码器一定可以做到几，这种编码器一定可以做到几乎乎无无失失真真，也也就就是是收收端端的的译译码码差差错错概概率率接接近近零零，条件是所取的符号数条件是所取的符号数L足够大。足够大。（2）将定理的条件改写成）将定理的条件改写成其中：其中：左边：左边：KL长码字所能携带的最大信息量，长码字所能携带的最大信息量，右边：右边：L长信源序列携带的信息量。长信源序列携带的信息量。上述定理表明上述定理表明，只要码字所能携带的信息量，只要码字所能携带的信息量大于信源序列输出的信息量，则可以使传输几大于信源序列输出的信息量，则可以使传输几乎无失真，当然条件是乎无失真，当然条件是L足够大。足够大。反之，当反之，当 时，不可能构成无时，不可能构成无失真的编码，也就是不可能做一种编码器，能失真的编码，也就是不可能做一种编码器，能使收端译码时差错概率趋于零。使收端译码时差错概率趋于零。时，则为临界状态，可能无时，则为临界状态，可能无失真，也可能有失真。失真，也可能有失真。2023/1/2117单个符号变长编码定理单个符号变长编码定理：若若一一离离散散无无记记忆忆信信源源的的符符号号熵熵为为H（X），每每个个信信源源符符号号用用m进进制制码码元元进进行行变变长长编编码码，一一定定存存在在一一种种无无失失真真编编码码方方法法，其其码码字字平平均均长长度度满满足下列不等式足下列不等式 第三节 变长编码定理2023/1/2118离散平稳无记忆序列变长编码定理离散平稳无记忆序列变长编码定理 对于平均符号熵为对于平均符号熵为HL（X）的离散平稳）的离散平稳无记忆信源，必存在一种无失真编码方无记忆信源，必存在一种无失真编码方法，使平均信息率法，使平均信息率满足不等式满足不等式 其中其中为任意小正数为任意小正数。2023/1/2119证明证明:设用设用m进制码元作变长编码，序列进制码元作变长编码，序列长度为长度为L个信源符号，则由（个信源符号，则由（431）式可以得到平均码字长度式可以得到平均码字长度满足下列不满足下列不等式等式 当当L足够大时，可使足够大时，可使，这就得到了这就得到了所需结论所需结论2023/1/2120说明说明:(1)用变长编码来达到相当高的编码效率，用变长编码来达到相当高的编码效率，一般所要求的符号长度一般所要求的符号长度L可以比定长编码可以比定长编码小得多。可得编码效率的下界：小得多。可得编码效率的下界：2023/1/2121(2)例例用二进制，用二进制，m2，log2m=l，H（X）2.55比特符号，若要求比特符号，若要求，则，则 2023/1/2122(3)码的剩余度码的剩余度为为 码的剩余度码的剩余度用来衡量各种编码方法与用来衡量各种编码方法与最佳码的差距最佳码的差距.2023/1/2123例例431 设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为解解:其信源熵为其信源熵为 比特/符号 求求:编码效率编码效率?2023/1/2124(1)定长编码定长编码若用二元定长编码（若用二元定长编码（0，1）来构造一个）来构造一个即时码：即时码：这时平均码长为这时平均码长为=1二元码符号二元码符号/信源符号信源符号编码效率为编码效率为(对于无记忆信源而言对于无记忆信源而言,有有HL(X)=H(X)输出的信息率为输出的信息率为R0811比特二元码符号比特二元码符号2023/1/2125(2)变长编码变长编码假定信源序列的长度为假定信源序列的长度为L=2,其即时码如表其即时码如表4-3所示。所示。序列序列概率即时码 x1x1 9/16 0 x1x2 x2x1 x2x2 1/16 3/16 3/16 111 110 102023/1/2126这个码的码字平均长度这个码的码字平均长度单个符号的平均码长单个符号的平均码长编码效率编码效率输出的信息率为输出的信息率为R20961比特二元码符号比特二元码符号比较（比较（1）、（）、（2）可见，经过二重扩展后，）可见，经过二重扩展后，效率由效率由81.1%上升到上升到96.1%。2023/1/2127(1)最佳码定义是什么最佳码定义是什么?凡是能载荷一定的信息量，且码字的平均长度最凡是能载荷一定的信息量，且码字的平均长度最短，可分离的变长码的码字集合都可称为最佳码。短，可分离的变长码的码字集合都可称为最佳码。(2)最佳编码思想是什么最佳编码思想是什么?将概率大的信息符号编以短的码字，概率小的符将概率大的信息符号编以短的码字，概率小的符号编以长的码字，使得平均码字长度最短。号编以长的码字，使得平均码字长度最短。(3)最佳码的编码主要方法有哪些最佳码的编码主要方法有哪些?香农（香农（Shannon）、费诺（）、费诺（Fano）、哈夫曼）、哈夫曼（Huffman）编码等。）编码等。第四节 最佳编码2023/1/21284.4.1香农编码方法香农编码方法 编码方法如下：编码方法如下：(1)将将信信源源消消息息符符号号按按其其出出现现的的概概率率大大小小依依次次排列排列(2)确定满足下列不等式的整数码长确定满足下列不等式的整数码长Ki：2023/1/2129 (3)为了编成唯一可译码，计算第为了编成唯一可译码，计算第i个消息个消息的累加概率的累加概率(4)将累加概率将累加概率Pi变换成二进制数。变换成二进制数。(5)取取Pi二进数的小数点后二进数的小数点后Ki位即为该消位即为该消息符号的二进制码字。息符号的二进制码字。2023/1/2130例例4-4-1 设信源共有设信源共有7个消息符号，按照概率大小个消息符号，按照概率大小排列后的概率分布和累加概率如表排列后的概率分布和累加概率如表4-4-1所示。根据自信息量定义计算每个信源所示。根据自信息量定义计算每个信源符号的信息量符号的信息量I(xi)=-logp(xi)，然后根据，然后根据信息量确定码长信息量确定码长Ki，如表，如表4-4-1中第中第4、5两列以两列以i=4为例，为例，2023/1/2131累加概率累加概率P4=0.57，变换成二进制为，变换成二进制为0.1001，由于，由于3，所以第，所以第4个消息的编个消息的编码码字为码码字为100。其他消息的码字可用同样。其他消息的码字可用同样方法求得，如表方法求得，如表4-4-1所示。所示。2023/1/2132xiP(xi)Pi-logp(xi)Ki码字x1x2x3x4x5x6x70.200.190.180.170.150.100.0100.20.390.570.740.890.992.342.412.482.562.743.346.663333347000001011100101111011111102023/1/2133说明说明:(1)该信源共有该信源共有5个三位的码字，各码字个三位的码字，各码字之间至少有一位数字不相同，故是唯一之间至少有一位数字不相同，故是唯一可译码。同时可以看出，这可译码。同时可以看出，这7个码字都不个码字都不是延长码，它们都属于即时码。这里是延长码，它们都属于即时码。这里L=1，m=2.(2)信源符号的平均码长信源符号的平均码长码元码元/符号符号 2023/1/2134(3)平均信息传输率平均信息传输率4.4.2费诺编码方法费诺编码方法费诺从概率匹配角度出发，构造了一种编码算法，费诺从概率匹配角度出发，构造了一种编码算法，称为费诺码。称为费诺码。其基本思想是：按照累加概率尽可能相等的原则对其基本思想是：按照累加概率尽可能相等的原则对信源符号进行分组，对于二元码，每次分为两组，对信源符号进行分组，对于二元码，每次分为两组，对于于d元码，则每次分为元码，则每次分为d个组，并且给不同的组分配一个组，并且给不同的组分配一个不同的码元符号；对其中的每组按照累计概率尽可个不同的码元符号；对其中的每组按照累计概率尽可能相等的原则再次进行分组，并指定码元符号，直到能相等的原则再次进行分组，并指定码元符号，直到不能再分类为止不能再分类为止;然后将每个符号指定的码元符号排列然后将每个符号指定的码元符号排列起来即可得到相应的码字。起来即可得到相应的码字。如果采用二元码，如果采用二元码，编码步骤：编码步骤：2023/1/2136编码步骤：编码步骤：（1）将将信信源源消消息息符符号号按按其其出出现现的的概概率率大大小小依依次次排列：排列：p(x1)p(x2)p(xn)。（2）将将依依次次排排列列的的信信源源符符号号按按概概率率值值分分为为两两大大组组，使使两两个个组组的的概概率率之之和和近近于于相相同同，并并对对各各组组赋予一个二进制码元赋予一个二进制码元“0”和和“1”。2023/1/2137（3）将每一大组的信源符号进一步再分成将每一大组的信源符号进一步再分成两组，使划分后的两个组的概率之和近两组，使划分后的两个组的概率之和近于相同，并又赋予两个组一个二进制符于相同，并又赋予两个组一个二进制符号号“0和和“1”。（4）如如此此重重复复，直直至至每每个个组组只只剩剩下下一一个个信信源符号为止。源符号为止。（5）信源符号所对应的码字即为费诺码。信源符号所对应的码字即为费诺码。2023/1/2138对例对例4-4-1的信源进行费诺编码，具体编的信源进行费诺编码，具体编码过程参见下表。码过程参见下表。2023/1/2139费诺码的平均码长费诺码的平均码长信息传输速率信息传输速率4.4.3哈夫曼编码方法哈夫曼编码方法 哈夫曼提出了一种编码效率较高的构造最佳码哈夫曼提出了一种编码效率较高的构造最佳码的方法，的方法，其基本思想是：概率大的符号分配短码其基本思想是：概率大的符号分配短码字，而概率小的信源符号分配长码字，为此首先字，而概率小的信源符号分配长码字，为此首先给小概率符号分配码元，分配码元后的符号进行给小概率符号分配码元，分配码元后的符号进行概率合并，然后按照大小顺序重排概率，并对概概率合并，然后按照大小顺序重排概率，并对概率小的符号或者符号集合分配码元，直到概率合率小的符号或者符号集合分配码元，直到概率合并结束为止，最后逆向搜索参与概率合并时分配并结束为止，最后逆向搜索参与概率合并时分配的码元符号，形成对应的码字。对于二元码，其的码元符号，形成对应的码字。对于二元码，其编码步骤如下：编码步骤如下：2023/1/2141哈夫曼编码哈夫曼编码步骤：步骤：（1）将将n个个信信源源消消息息符符号号按按其其出出现现的的概概率率大大小小依依次排列，次排列，p（x1）p（x2）p（xn）（2）取两个概率最小的字母分别配以取两个概率最小的字母分别配以0和和1两码两码元，并将这两个概率相加作为一个新字母的概元，并将这两个概率相加作为一个新字母的概率，与未分配的二进符号的字母重新排队。率，与未分配的二进符号的字母重新排队。2023/1/2142（3）对对重重排排后后的的两两个个概概率率最最小小符符号号重重复复步步骤（骤（2）的过程。）的过程。（4）不不断断继继续续上上述述过过程程，直直到到最最后后两两个个符符号配以号配以0和和1为止。为止。（5）从最后一级开始，向前返回得到各个从最后一级开始，向前返回得到各个信源符号所对应的码元序列，即相应的信源符号所对应的码元序列，即相应的码字。码字。2023/1/2144问题问题:为何哈夫曼编码方法得到的码并非是唯一的为何哈夫曼编码方法得到的码并非是唯一的?(1)每每次次对对信信源源缩缩减减时时，赋赋予予信信源源最最后后两两个个概概率率最最小小的的符符号号，用用0和和1是是可可以以任任意意的的，所所以以可可以以得得到到不不同同的的哈哈夫夫曼曼码码，但但不会影响码字的长度。不会影响码字的长度。2023/1/2145(2)对对信信源源进进行行缩缩减减时时，两两个个概概率率最最小小的的符符号号合合并并后后的的概概率率与与其其它它信信源源符符号号的的概概率率相相同同时时，这这两两者者在在缩缩减减信信源源中中进进行行概概率率排排序序，其其位位置置放放置置次次序序是是可可以以任任意意的的，故故会会得得到到不不同同的的哈哈夫夫曼曼码码。此此时时将将影影响响码码字字的的长长度度，一一般般将将合合并并的的概概率率放放在在上上面面，这这样样可可获获得得较较小小的的码码方方差差。码码方方差小的编码方法要比码方差大的编码方法好。差小的编码方法要比码方差大的编码方法好。例例设有离散无记忆信源的概率空间为设有离散无记忆信源的概率空间为采用二元码进行编码，由于符号合并后的概率与信采用二元码进行编码，由于符号合并后的概率与信源其他符号的概率相等，合并概率放置的位置不同，源其他符号的概率相等，合并概率放置的位置不同，因此可以得到不同的编码结果，即有两种哈夫曼编码因此可以得到不同的编码结果，即有两种哈夫曼编码方法。如果将合并概率放在下面，编码过程、方法。如果将合并概率放在下面，编码过程、产生码产生码字和编码长度如表字和编码长度如表5.4所示；如果将合并概率放在上面，所示；如果将合并概率放在上面，则编码过程及结果如表则编码过程及结果如表5.5所示。所示。根据两种方法的编码结果，计算两种哈夫曼码的平根据两种方法的编码结果，计算两种哈夫曼码的平均码长，结果是两种编码方法的平均码长相等，即均码长，结果是两种编码方法的平均码长相等，即比特/符号编码效率也相等，都为编码效率也相等，都为将两种编码方法得到的码长分别代入上式，得到各自码方差为将两种编码方法得到的码长分别代入上式，得到各自码方差为0l1=1.362l2=0.16码方差小的编码方法要比码方差大的编码方法好。由于方法码方差小的编码方法要比码方差大的编码方法好。由于方法2的的码方差比方法码方差比方法1的码方差小许多，因此方法的码方差小许多，因此方法2的编码质量好。的编码质量好。