第四章：无失真信源编码.pptx

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

1、无失真信源编码无失真编码概述定长信源编码变长信源编码实用的无失真信源编码方法举例第1页/共113页4.1无失真编码概述1离散、无失真、无记忆信源编码的一般模型模型：总组合数：总码组合数：入出信源编码 取值于同一个符号集，符号集大小为n 取值于同一个符号集，符号集大小为m第2页/共113页4.1无失真编码概述2问问题题：能能否否进进行行无无失失真真编编码码?怎怎样样进进行行无无失失真真编编码码?(前提：不考虑信源统计特性前提：不考虑信源统计特性)应满足条件应满足条件：无失真条件变换无失真条件变换 相互矛盾！相互矛盾！o 结论：结论：当当 n=m 时，时，KL 不有效。不有效。当当K=L 时，时，

2、mn，亦不满足有效性，亦不满足有效性o 解决办法：解决办法：引入信源统计特性。引入信源统计特性。无失真：无失真：有效：有效：第3页/共113页4.1无失真编码概述3考察无失真条件：等概条件下的消息符号熵等概条件下的码字符号熵考虑信源的实际统计特性（非等概），实际消息熵为：考虑信源的实际统计特性（非等概），实际消息熵为：代入无失真条件得：代入无失真条件得：结论：即使m=n,只要 就有可能实现K0,0，只要满足：只要满足：则：当则：当L足够大时，可使译码差错小于足够大时，可使译码差错小于，反反之之，当当时，译码一定出错。时，译码一定出错。解释：解释：定长编码定理给出了信源进行定长编码定理给出了信源

3、进行等长编码等长编码所需码长的所需码长的理论极限值理论极限值。第5页/共113页o结论：对信源进行二元等长编码时，每个信源符号所需码长的极限值为 o结论：对于唯一可译码，每个信源符号至少需要用 个码符号来变换。4.2定长编码定理2-进一步理解若要求所得的等长码是唯一可译的，则必须：o若L1，则：o当采用二元码编码时，m2，则：第6页/共113页4.2定长编码定理2-进一步理解每个码字（码序列）所能携带的平均信息量每个源序列所包含的平均不确定性。即：信源序列携带的信息量o 等长有效性的无失真编码的条件：等长有效性的无失真编码的条件：码长下限：码长下限：o 为实现有效：为实现有效：误码率任意小的方

4、向：误码率任意小的方向：?o结论：只要码字能够携带的信息量大于信源序列携带的信息 量，总可以实现几乎无失真编码 考虑信源统计特性考虑信源统计特性第7页/共113页讨论讨论：第三章：在考虑符号出现的概率和符号间相关性前提下第三章：在考虑符号出现的概率和符号间相关性前提下,每个每个 英文符号平均携带的信息量是英文符号平均携带的信息量是1.4bit/1.4bit/符号符号5bit/5bit/码符号。码符号。4.2 定长编码定理3-举例例1：英文电报有32个符号（266），即n=32，若m=2，L1（即对信源的逐个符号进行二元编码），则：bit解释解释：每个英文电报符号至少需要用每个英文电报符号至少需

5、要用5 5位二元符号编码位二元符号编码 （每位二元符号可以携带（每位二元符号可以携带1bit1bit信息，即每个英文电报符号用了可以携带信息，即每个英文电报符号用了可以携带 5bit5bit信息的码符号即信息的码符号即5 5位二元码表示）位二元码表示）问题：问题：如何提高效率？如何体现有效性如何提高效率？如何体现有效性？结论：结论：若不考虑信源统计特性等长编码效率极低若不考虑信源统计特性等长编码效率极低!第8页/共113页4.2定长编码定理4-进一步理解解决方法：字母个数为字母个数为n n，字母之间相关长度为，字母之间相关长度为L L的英文信源，其可能的字母序列的英文信源，其可能的字母序列总数

6、为总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着；但其中大部分字母序列是无意义的字母组合，而且随着L L的增加，这种无意义序列的总数越来越大。的增加，这种无意义序列的总数越来越大。进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数码，即需编码的字母序列的总数 ,则平均每个信源符号所需则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。的码符号个数可以大大减少，从而提高了传输效率。考察考察：方法方法：问题问题：会引入一定的误差！但当会引入一定的误差！但当L足够长后，误差可

7、以任意小。足够长后，误差可以任意小。第9页/共113页4.2定长编码定理5证明考察离散、随机序列信源的统计特性渐进等分割性（AEP）AEP描述：渐进等分割定理：（熵定理，遍历性定理）设是离散无记忆信源输出的一个特定序列，则任给和，总可以找到一个整数，使当时，有：引入：渐进等分割性（引入：渐进等分割性（AEP:Asymptotic Equipartition Property）特定序列的平均符号自信息随机矢量的平均符号熵第10页/共113页任任何何一一个个离离散散随随机机序序列列信信源源当当序序列列长长度度L时时,信信源源序序列列会会产产生生两两极极分分化化.小小概概率率事事件件集集合合与与大大

8、概概率率事事件件集集合合,即即nL=对于对于有性质有性质:对于对于有性质有性质:由此可见，信源编码只需对信源中由此可见，信源编码只需对信源中少数少数落入典型大概率事件的集合的符落入典型大概率事件的集合的符号进行编码即可。而对号进行编码即可。而对大多数大多数属于非典型小概率事件集合中的信源符号属于非典型小概率事件集合中的信源符号无需编码无需编码.4.2定长编码定理6AEP物理意义信源序列集合信源熵信源熵大概率事件熵大概率事件熵第11页/共113页4.2定长编码定理7AEP证明集合和中的序列分别称为典型序列和非典型序列表示 中所有 典型序列的集合表示 集合中序列的个数可以证明：对于任意小的正数可以

9、证明：对于任意小的正数 ，当，当L足够大时，足够大时，第12页/共113页4.2定长编码定理7AEP证明还可以证明：对于任意小的正数，当L足够大时，表示序列 出现的概率 由切比雪夫不等式可得：表示S中每个符号携带的信息量的方差第13页/共113页第14页/共113页例2p(1)=p,p(0)=q,统计独立L长的序列:当L8时，序列11000101和序列011100101的概率为和显然，这两个序列不等概,当L时，有一些序列时，有一些序列1出现的出现的次数接近次数接近Lp，这些序列的概率为，这些序列的概率为且这些序列近似等概分布。且这些序列近似等概分布。4.2定长编码定理8AEP举例L长的序列长的

10、序列 ，对于任意小的正数，对于任意小的正数 满足式满足式 的序列称为的序列称为 典型序列典型序列 即：即：典型序列集是哪些平均自信息任意小地接近信源熵的典型序列集是哪些平均自信息任意小地接近信源熵的N长序列长序列的集的集合合第15页/共113页4.2定长编码定理9-AEP应用AEP结论：当L足够大时，所有典型序列出现的概率近似相等，即典型序列为渐进等概序列可粗略认为典型序列出现的概率为所有典型序列的概率和接近为1，即典型序列总数占信源序列的总数第16页/共113页4.2定长编码定理9-AEP应用o AEP应用：应用：n提出、证明都是基于离散无记忆序列信源提出、证明都是基于离散无记忆序列信源 n

11、平稳遍历信源有类似结果平稳遍历信源有类似结果n体现信源统计特性体现信源统计特性n用以证明定长编码定理用以证明定长编码定理第17页/共113页4.2定长编码定理10证明定长编码定理证明思路：将取自S，长为L的信源符号序列分为集合和o 几个概念：几个概念：n 编码信息率：编码信息率：编码后对应于每个信源符号平均能载荷的最大信息量n 编码效率：编码效率：编码前后平均每个信源符号能载荷的最大信息量之比只对集合 中的序列进行一一对应的等长编码此时的误差为 ，计算误差证明当证明当 ，且，且(K/L)log mH(S)+时，时，第18页/共113页4.2定长编码定理11（物理意义）结论：可推广至离散、非平稳

12、无记忆信源和有记忆信源（即H(S)=H(S)）情况只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码二元码时，二元码时，m2：l最佳等长码时：最佳等长码时：第19页/共113页4.2定长编码定理12（实际应用问题）编译码同步问题问题：如何使译码端知道码字起点问题：如何使译码端知道码字起点解决办法：解决办法：1 1、每个码字加短同步前缀、每个码字加短同步前缀 2 2、每若干码字加较长同步前缀、每若干码字加较长同步前缀o 分组长度与编译码复杂性、编译码延时等的关系分组长度与编译码复杂性、编译码延时等的关系n问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加问题：要实现

13、有效，源序列分组很长，使得编译码复杂性和延时增加n解决办法：目前没有理想的解决办法解决办法：目前没有理想的解决办法o 定长信源编码的定长信源编码的理论意义理论意义远大于其远大于其实用价值实用价值第20页/共113页4.2定长编码定理13（举例)例例3：设有一简单离散信源：设有一简单离散信源：L=1,n=2 对其进行近似于无失真的等长编码，若要求其编码效率为对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低，差错率低 于于10-5，试求符号联合编码长度，试求符号联合编码长度L=？解：解：由编码效率：由编码效率：而：而：则：则：且：则：则：结论：可见结论：可见,需要需要4100万个

14、信源符号联合编码万个信源符号联合编码,才能达到上述要求才能达到上述要求,这显然是不现实的这显然是不现实的.一般来说：当一般来说：当L L有限时，高传输效率的等长码往有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码码那样可以实现真正的无失真编码第21页/共113页改变信源改变信源定长编码定长编码无失真信源编码实现方法一无失真信源编码实现方法一无失真信源编码实现方法二无失真信源编码实现方法二适应信源适应信源变长编码变长编码大概率大概率短码；小概率短码；小概率长码长码第22页/共113页4.3变长信源编码-1几

15、个码类的概念非奇异码（单义码）唯一可译码前缀码（即时码、非延长码、异前置码）最佳码（紧致码）Kraft定理即时码码长必须满足的条件唯一可译码存在定理变长编码定理（香农第一定理）第23页/共113页4.3变长信源编码-2(几个码类的概念)非奇异码（单义码）：每一个码字仅对应信源中的一个信源符号（序列）。编码是单义的。反之为奇异码或非单义码。第24页/共113页4.3变长信源编码-3(几个码类的概念)唯一可译码编码单义、译码单义对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。非奇异码=唯一可译码？第25页/共113页4.3变长信源编码-4(

16、几个码类的概念)前缀码是唯一可译码中的一类在一个变长码中，没有任何一个码字是其他码字的前缀。译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。又称即时码、非延时码例如逗点码：1，01，001，0001第26页/共113页4.3变长信源编码-5(几个码类的概念)最佳码唯一可译码的一类其平均码长小于其他唯一可译码的平均长度所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码前缀码前缀码最佳码最佳码第27页/共113页4.3变长信源编码-6（几种类型的信源编码举例几种类型的信源编码举例）例4：信源信源概概 率率pi 编编 码码编编 码码编编 码码编编 码码编编 码码U11/2000000U

17、21/401010110U31/810100011110U41/81110110111111定长唯一可译奇异奇异非奇非奇异异前缀前缀唯一唯一可译可译第28页/共113页4.3变长信源编码-7(Kraft定理)引出码树构造即时码方法Kraft定理描述即时码码长须满足的条件Kraft定理证明略第29页/共113页实时唯一可译、可分离A0B10C110D1110E11110ABA BBBBBAACDDED要求：须严格同步第30页/共113页4.3变长信源编码-8(Kraft定理引出)问题问题：寻求实时唯一可译码实时唯一可译码方法：研究实时唯一可译码的码字可分离条件方法：研究实时唯一可译码的码字可分离

18、条件简单信源：简单信源：“码树码树”概念（直观）概念（直观）一般信源：通过一般信源：通过KraftKraft定理给出定理给出实时唯一可译码（实时唯一可译码（前缀码）存前缀码）存在在 的条件的条件第31页/共113页码树变长码的树图表示将变长码与码树建立将变长码与码树建立“一一对应一一对应”关系：关系：树根树根码字起点码字起点树枝数树枝数码的进制数码的进制数节点节点码字或码字的一部分码字或码字的一部分终止节点终止节点码字码字节数节数码长码长非满树非满树变长码变长码满树满树等长码等长码第32页/共113页利用码树构造前缀码利用码树构造前缀码源符号源符号概率概率前前缀码s1s2s3s40111000

19、10110111s10.04s4s30.160.64s20.16第33页/共113页4.3变长信源编码-9(Kraft定理)问题：问题：比较简单信源，码树方法可直接且直观构造前缀码比较简单信源，码树方法可直接且直观构造前缀码较复杂信源，直接画码树复杂且困难较复杂信源，直接画码树复杂且困难解决方法：解决方法：为便于分析，特别对含有很多符号种类的复杂信源，寻为便于分析，特别对含有很多符号种类的复杂信源，寻找一种与上述找一种与上述“树图树图”等效的解析式表达式等效的解析式表达式-Kraft不不等式。等式。结论：结论：KraftKraft定理给出定理给出码字可分离码字可分离或或前缀码存在前缀码存在的的

20、充要条件充要条件第34页/共113页4.3变长信源编码-10(Kraft定理)kraft定定理理：长长度度为为Ki（i=1,2,n）的的m（码码字字母母表表长长度度）进制前缀码存在的充要条件为：进制前缀码存在的充要条件为：证明：略证明：略物理意义：物理意义：给给定定信信源源个个数数N和和码码字字母母数数m，只只要要允允许许码码字字长长度度可可以以足足够够长，就总可以满足长，就总可以满足Kraft不等式，从而得到前缀码。不等式，从而得到前缀码。只要适当选取码长，码字一定可以即时分离。只要适当选取码长，码字一定可以即时分离。第35页/共113页(a)10(0.8)(0.2)(b)10(0.2)(0

21、.64)(0.16)10(c)10(0.2)(0.512)(0.16)10(0.128)10例例5：32104 个叶子个叶子:代表序列代表序列 1,01,001 和和 000是前缀码消息符号概率码字序号编码a0.201b0.16101c0.1282001d0.5123000第36页/共113页4.3变长信源编码-11(唯一可译码定理)KraftKraft不等式给出的限制也是所有唯一可译码都必须满足的。不等式给出的限制也是所有唯一可译码都必须满足的。定理描述：定理描述：任何唯一可译码均满足任何唯一可译码均满足KraftKraft不等式。不等式。结论：结论：唯一可译码一定满足唯一可译码一定满足kr

22、aftkraft不等式不等式满足满足kraftkraft不等式的码不一定是唯一可译码，但一定存不等式的码不一定是唯一可译码，但一定存在至少一种唯一可译码在至少一种唯一可译码对任何唯一可译码均可在不改变码字长度的条件下得到对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码相应的前缀码第37页/共113页4.3变长编码定理12问题：问题：对于已知信源对于已知信源S可用码符号集可用码符号集X进行变长编码，而且对同一信进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢哪一种最好呢?从高速度传输信息的观

23、点来考虑，当然希望从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择选择由短的码符号组成的码字，就是用码长作为选择准则。准则。引入：码的引入：码的平均长度平均长度。离散无记忆平稳信源离散无记忆平稳信源信源熵率为信源熵率为 ，码字个数为，码字个数为M，信源符号对应码长分别，信源符号对应码长分别为：为：ki,i=1,2,.n则前缀码平均码长：则前缀码平均码长：第38页/共113页4.3变长编码定理13定理：定理：离散无记忆平稳信源离散无记忆平稳信源S，其熵为，其熵为 ，并有码符号集，并有码符号集C=c1,cm。对信源。对信源S进行编码进行编码,总可以找到一种编码方

24、法，总可以找到一种编码方法，构成惟一可译码，使信源构成惟一可译码，使信源S中中每个信源符号每个信源符号所需的平均码所需的平均码长满足长满足:另一方面另一方面,必可以找到前缀码，使其平均码长满足必可以找到前缀码，使其平均码长满足 l对于给定的信源和码符号集，若有一个唯一可译码，其对于给定的信源和码符号集，若有一个唯一可译码，其平均长度小于所有其他唯一可译码，则称这种码为平均长度小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码。或最佳码。唯一可译唯一可译码存在性码存在性紧致码的紧致码的存在性存在性第39页/共113页证明：证明：第40页/共113页Jensen不等式第41页/共113页平均

25、码长=下限值第42页/共113页第43页/共113页由右边不等式第44页/共113页l香农第一定理（变长无失真信源编码定理）：香农第一定理（变长无失真信源编码定理）：设离散无记忆信源的熵为设离散无记忆信源的熵为 H H(S S)，它的，它的N N次扩展信源次扩展信源为为 ，对扩展信源，对扩展信源 进行编码。总可以找到一种编进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：码方法，构成唯一可译码，使平均码长满足：其中l当时，有第45页/共113页l当时，有代表平均到每个信源符号所需的码长l当时，每个码符号能够携带的信息量为：第46页/共113页4.3变长编码定理14物理意义：又称

26、无噪信道编码定理编码后的码符号信源尽可能为等概分布，使每个码符号平均所含的信息量达到最大要做到无失真编码，变换每个信源符号平均所需最少的m元码元数就是信源的熵率（以m进制信息量单位测度，对应离散无记忆信源）信源的熵率是描述每个信源符号平均所需最少的比特数定理说明：是存在性定理具有理论指导意义是构造性定理设计出多种具体编码方法第47页/共113页构造：构造：1、扩展信源至、扩展信源至2、取、取3、则：、则：k(s)满足满足kraft不等式，存在前缀码不等式，存在前缀码4、用树图法构造前缀码香农编码、用树图法构造前缀码香农编码第48页/共113页4.3变长编码定理15编码效率l变长码编码效率：衡量

27、各种编码方法的优略，判断是否最佳码。编码前平均每个信源符号携带的信息量为：编码后平均每个信源符号携带的最大的信息量为：定义变长码编码效率为：l另一种理解：最佳码（极限时）每个信源符号每个信源符号的平均码长为：某一方法得到的每个信源符号每个信源符号的的平均码长为：定义变长码编码效率为：第49页/共113页4.3变长编码定理16编码效率比较：定长编码的编码效率：变长编码的编码效率：注意到：是指平均到每个信源符号所需的码长，而是指平均到每个信源符号所需的码长，而 也是平均到每也是平均到每 个信源符号的码长，所以它们是一致的，均表示无失真信源个信源符号的码长，所以它们是一致的，均表示无失真信源 编码的

28、效率编码的效率。第50页/共113页例6：一离散无记忆信源其其熵熵为：为：用二元符号（用二元符号（0，1；m=2）构造一个）构造一个前缀码前缀码：此时此时每个信源符号每个信源符号平均码长平均码长为：为：编码效率编码效率为：为：为提高编码效率，对为提高编码效率，对S的的2次扩展信源进行次扩展信源进行2维联合编码：维联合编码：第51页/共113页构造一个扩展信源构造一个扩展信源S2的前缀码：的前缀码：前缀码前缀码 s1s1 9/16 0 s1s23/16 10 s2s1 3/16110 s2s2 1/16111此时此时平均码长平均码长为：为：此时信源此时信源S中中每个符号每个符号对应的对应的平均码

29、长平均码长为：为：编码效率编码效率为：为：同样可得：同样可得：第52页/共113页定长编码与变长编码效率比较：例6与例3相比：同一个信源，当要求编码效率达到96时，等长码需要4100万个信源符号联合编码；变长码只需2个符号（二次扩展信源）联合编码；结论结论：采用变长编码，：采用变长编码，L不需要很大就可以达到相当高的编码效率，不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着而且可以实现无失真编码。且随着L的增大，编码效率越来越接近于的增大，编码效率越来越接近于1。第53页/共113页无失真信源编码无失真信源编码等长编码等长编码变长编码变长编码完全无失真完全无失真效率差效率差

30、较好的效率、较好的效率、一定的误差一定的误差可实现、有实用可实现、有实用难实现、无实难实现、无实用用无失真、较好无失真、较好的效率的效率可实现、有实用可实现、有实用总结：总结：第54页/共113页定长编码定理定长编码定理近似无失真等长编码的条件近似无失真等长编码的条件有效性、无失真性无法兼得有效性、无失真性无法兼得考察信源统计特性考察信源统计特性利用信源序列的利用信源序列的AEP特性特性定长编码定理研究思路定长编码定理研究思路变长编码定理研究思路变长编码定理研究思路无失真唯一可译码无失真唯一可译码工程可实现前缀码工程可实现前缀码码树构造简单前缀码码树构造简单前缀码KRAFT不等式前缀不等式前缀

31、码存在条件码存在条件香农定理最佳码存在条件香农定理最佳码存在条件第55页/共113页定长编码定理定长编码定理变长编码定理变长编码定理1、存在码长为、存在码长为K的定长编码方法的定长编码方法2、L足够大时，几乎无失真足够大时，几乎无失真条件条件1、存在无失真的变长编码方法、存在无失真的变长编码方法2、最佳码的码长上界：、最佳码的码长上界：条件条件结论结论结论结论第56页/共113页4.4 最优编码定理1:对每一给定的离散无记忆信源,存在一个最优的二元前缀码.这个码中最少发生的两个码字必具有相同的长度,且码中相同长度的码字有两个或两个以上时,其中必有两个码字的差别只在最后一位.第57页/共113页

32、4.4 最优编码定理说明没给出编码全过程最优二元前缀码，两个最小概率信源字母对应的码字等长，且差别在最后一位。两个最小概率信源字母对应的码字相同部分的最后一位可以通过缩减信源的方法得到。缩减方法：原信源缩减信源第58页/共113页4.4 最优编码定理2:设C是某信源经缩减后所得的缩减信源的最优前缀码，将C中由原信源中的最小概率的两个字母缩减得到的字母所对应的码字后各加0和1,作为原信源的最小概率的两个码字,而其余码字不变,则这样得到的码C对原信源也是最优的.第59页/共113页4.5实用的无失真信源编码方法举例香农（Shannon)码费诺（Fano）码霍夫曼（Huffman）编码编码方法特点应

33、用问题第60页/共113页思路：平均码长与信源特性相匹配适用数据源：离散无记忆信源香农编码、费诺编码、霍夫曼编码4.5实用的无失真信源编码方法举例第61页/共113页香农编码步骤以二进制香农码为例：排序将信源符号按概率从大到小的顺序排列，为方便起见，令 p(x1)p(x2)p(xn)概率累加 令p(x0)=0，设i=0,1,n-1,用pa(xj)，j=i+1表示前i个码字的累加概率，则：确定码长 求满足下列不等式的整数ki，并令ki为第i个码字的长度log2 p(xi)ki1 log2 p(xi)编码 将pa(xj)用二进制表示，并取小数点后ki 位作为符号xi的编码。4.5实用的无失真信源编

34、码方法举例第62页/共113页例7有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。香农编码举例1第63页/共113页二进制香农编码二进制香农编码xi p(xi)pa(xj)pa(xj)2 ki 码字x10.25x20.25x30.20 x40.15x50.10 x60.050.250.000.500.700.850.95(0.000)2(0.010)2(0.100)2(0.101)2(0.1101)2(0.11110)22233450001100101110111110第64页/共113页编码效率离散无记忆信源的熵：平均码长：采用香农编码后的信息率：编码效率：结论：1、香

35、农编码对信源进行了压缩。若对该信源采用等长编码，要做到无失真译码，每个符号至少要用3个比特表示。2、编码效率并不是很高。香农编码举例2第65页/共113页 以二进制费诺编码为例，编码步骤如下：排序：将概率按从大到小的顺序排列，令p(x1)p(x2)p(xn)分组：按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二 进制码就分成两组，编m进制码就分成m组。编码：给每一组分配一位码元。重复：将每一分组再按同样原则划分，重复步骤2和3，直至概率不再可分 为止。费诺编码步骤4.5实用的无失真信源编码方法举例第66页/共113页例8 设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表所示

36、。费诺编码举例1010101010100011011011101111222344第67页/共113页编码效率该信源的熵:平均码长:编码效率:结论：费诺码比较适合于每次分组概率都很接近的信源。特别是对每次分组概率都相等的信源进行编码时，可达到理想的编码效率。费诺编码举例3第68页/共113页4.5实用的无失真信源编码方法举例霍夫曼编码编码规则：编码规则：1)排序：排序：将信源消息将信源消息U按概率大小排序（由大至小）按概率大小排序（由大至小）p(x1)p(x2)p(xn)2)定规则并编码：定规则并编码：从从最最小小概概率率的的两两个个符符号号开开始始编编码码，并并赋赋予予一一定定规规则则，如如

37、下下支支路路小小概概率率为为“1”，上上支支路路大大概概率率为为“0”。若若两两支支路路概概率率相相等等，仍仍为下支为为下支为“1”上支为上支为“0”。3)概率合并：将已编码两支路概率合并，重新排队，编码。概率合并：将已编码两支路概率合并，重新排队，编码。4)重复：重复步骤重复：重复步骤3）直至合并概率归一时为止。）直至合并概率归一时为止。5)确定最终码子：从概率归一端沿树图路线逆行至对应消息编码。确定最终码子：从概率归一端沿树图路线逆行至对应消息编码。第69页/共113页霍夫曼编码举例1例9：0101011001010110第70页/共113页霍夫曼编码举例1例9：0101011001010

38、11011第71页/共113页霍夫曼编码举例1例9：010101100101011011000第72页/共113页霍夫曼编码举例1例9：010101100101011011000001第73页/共113页霍夫曼编码举例1例9：010101100101011011000001010第74页/共113页霍夫曼编码举例1例9：0101011001010110110000010100110第75页/共113页霍夫曼编码举例1例9：010101100101011011000001010011001110第76页/共113页霍夫曼编码举例1例9：010101100101011011000001010011

39、00111001111第77页/共113页霍夫曼编码举例2特点：编码不是唯一的保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）每次缩减信源的最长两个码字具有相同码长 后三个特点保证了所得到的huffman码一定是最佳码（证明见李亦农信息论基础教程2005年1月第一版p114）第78页/共113页每次对缩减信源两个概率最小的符号分配“0”和“1”码元是任意的，所以可得到不同的码字。只要在各次缩减信源中保持码元分配的一致性，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长ki不变，

40、平均码长 也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，这几个符号的次序可任意排列，编出的码都是正确的，但得到的码字不相同码字不相同。不同的编法得到的码字长度码字长度ki也不尽相同也不尽相同。霍夫曼编码举例3第79页/共113页例10 单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。方法一：合并后的新符号排在其它相同概率符号的后面。霍夫曼编码举例4对应该图画出树图第80页/共113页 霍夫曼编码举例6xiP(xi)码字码长x10.411x20.2012x30.20003x40.100104x50.100114第81页/共113页方法

41、二：合并后的新符号排在其它相同概率符号的前面。霍夫曼编码举例7第82页/共113页霍夫曼编码举例8xiP(xi)码字码长x10.4002x20.2102x30.2112x40.10103x50.101130001011x5x4x3x2x11第83页/共113页单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。编法一的平均码长为编法二的平均码长为可见 ，本例两种编法的平均码长相同，所以编码效率相同。霍夫曼编码举例9思考题：哪种方法更好？思考题：哪种方法更好？第84页/共113页

42、讨论：1)两种方法平均码长相等。2)计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。第85页/共113页4.5实用的无失真信源编码方法举例霍夫曼编码应用考察考察例例6和下例：例和下例：例12：对以下平稳信源进行霍夫曼编码：对以下平稳信源进行霍夫曼编码信源字母信源字母概率概率码字码字编码过程编码过程a1a2a3a41/21/41/81/8010110111010101编码效率：编码效率：第86页/共113页4.5实用的无失真信源编码方法举例霍夫曼编码应用结论：结论：q 各信源字母的概率刚好取各信源字母的概率刚好取 的形式时，霍夫曼编码取得的形式时，霍夫曼编码取得 理想的压缩效

43、果理想的压缩效果q 各信源字母的概率不能取各信源字母的概率不能取 的形式时，霍夫曼编码压缩的形式时，霍夫曼编码压缩 效率不理想效率不理想q 扩展信源，可以提高压缩效率，当扩展信源，可以提高压缩效率，当 时达到理想的压缩时达到理想的压缩 第87页/共113页霍夫曼编码应用应用应用:在不同领域得到广泛应用。在不同领域得到广泛应用。例：例：International digital facsimile coding standard(1980)US International digital facsimile coding standard(1980)US、MPEG1MPEG1、2 2问题：问题：

44、误差扩散误差扩散 速率匹配速率匹配统计匹配（统计匹配（1 1、一般变长编码更适合大的消息集，而不大适合小且概率分布相差很大的集、一般变长编码更适合大的消息集，而不大适合小且概率分布相差很大的集合；小消息集只有在很特殊情况下才能实现统计匹配合；小消息集只有在很特殊情况下才能实现统计匹配 2 2、要求了解信源的统计分布；）、要求了解信源的统计分布；）算法复杂度随着信源符号串长度的增加而迅速增长。算法复杂度随着信源符号串长度的增加而迅速增长。4.5实用的无失真信源编码方法举例第88页/共113页霍夫曼编码应用解决：解决：工工程程上上克克服服误误差差扩扩散散的的方方法法有有两两种种：一一是是限限制制哈

45、哈夫夫曼曼码码仅仅能能应应用用于于优优质质信信道道（=10Y。把符号序列看成二进制小数把符号序列看成二进制小数0.S和和0.Y，对第一个，对第一个i有有siyi,则则0.S0.Y将二元符号序列排成一棵将二元符号序列排成一棵n阶二元整树。可见所有小于阶二元整树。可见所有小于S的序列都的序列都在同一阶在同一阶S节点的左侧。节点的左侧。111001第102页/共113页S=110101 C0.01111001P(S)=(3/4)3(1/4)C=1000(有尾数时进位）11010.100101000.00011011算术码编码举例1例例14：P(S)=(3/4)3(1/4)第103页/共113页111

46、0算术码编码举例2第104页/共113页算术码编码过程：算术码编码过程：累积概率：累积概率码字码字：区间长度（符号所落区间）：区间长度（符号所落区间）例：例：算术码编码举例3第105页/共113页sF(s)A(s)kC空空0110.010.111110.01110.10011100.01110.001001310010.011110010.0001101141000F(1)=F()+A()F(1)=0+0.01=0.01A(1)=A()p1=1x0.11=0.11A(11)=A(1)p1F(110)=F(11)+A(11)F(0)=0.0111+0.1001x0=0.0111A(110)=A(

47、11)p0A(1101)=A(110)p1算术码编码举例4第106页/共113页算术码译码过程：算术码译码过程：C=1000=0.1sF(s)C-F(s)P(s)P(s)p0输出输出空空00.110.01110.010.010.110.00111110.01110.00010.10010.00100101100.01110.00010.0010010.00001001111104.5实用的无失真信源编码方法举例算术码译码第107页/共113页JPEGJPEG算法适用于灰度和颜色连续变化的静止图像，分成有损压缩和无损压缩两种，具有顺序编码、算法适用于灰度和颜色连续变化的静止图像，分成有损压缩和无

48、损压缩两种，具有顺序编码、累进编码、无失真编码和分层编码四种操作方式。累进编码、无失真编码和分层编码四种操作方式。JPEGJPEG有损压缩方法是以有损压缩方法是以DCT(Discrete Cosine DCT(Discrete Cosine Transform)Transform)为基础的压缩方法。为基础的压缩方法。JPEGJPEG无损压缩方法又称预测压缩方法。但最常用的是基于无损压缩方法又称预测压缩方法。但最常用的是基于DCTDCT变换变换的顺序型模式有损压缩，又称为的顺序型模式有损压缩，又称为JPEGJPEG基本系统基本系统(Baseline)(Baseline)，具有先进、有效、简单、易

49、于交流的，具有先进、有效、简单、易于交流的特点，下图给出了特点，下图给出了JPEGJPEG编码器的流程图。编码器的流程图。算术码的实际应用算术码的实际应用-JPEG200；1、Huffman码2、算术码（此时无码表）第108页/共113页u 算术编码是一种非分组编码，对变长信源符号序列赋于变长码，理论上可以达到更算术编码是一种非分组编码，对变长信源符号序列赋于变长码，理论上可以达到更 好的效果。好的效果。u 信源的每信源的每一个符号一个符号对应对应0，1）的一个子区间，该子区间的长度等于对应符号出）的一个子区间，该子区间的长度等于对应符号出 现的现的概率概率。u 算术编码把信源算术编码把信源X

50、的任一给定的任一给定序列序列和和0，1）的一个子区间联系在一起，该子区间）的一个子区间联系在一起，该子区间 的长度等于这个序列的概率。的长度等于这个序列的概率。u 编码过程从第一个符号开始，逐个处理。随着处理符号数目的增加，同序列联系在编码过程从第一个符号开始，逐个处理。随着处理符号数目的增加，同序列联系在 一起的区间长度越来越小。一起的区间长度越来越小。u 随着区间的缩小，区间首尾二进制代码相同位数越来越多，这些二进制代码唯一随着区间的缩小，区间首尾二进制代码相同位数越来越多，这些二进制代码唯一 确定了输入符号序列，并可唯一译码。确定了输入符号序列，并可唯一译码。u 概率大的符号对应区间大，