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

第四章：无失真信源编码无失真信源编码无失真编码概述定长信源编码变长信源编码实用的无失真信源编码方法举例4.1无失真编码概述1离散、无失真、无记忆信源编码的一般模型模型：总组合数：总码组合数：入出信源编码 取值于同一个符号集，符号集大小为n 取值于同一个符号集，符号集大小为m4.1无失真编码概述2问问题题：能能否否进进行行无无失失真真编编码码?怎怎样样进进行行无无失失真真编编码码?(前提：不考虑信源统计特性前提：不考虑信源统计特性)应满足条件应满足条件：无失真条件变换无失真条件变换 相互矛盾！相互矛盾！o 结论：结论：当当 n=m 时，时，KL 不有效。不有效。当当K=L 时，时，mn，亦不满足有效性，亦不满足有效性o 解决办法：解决办法：引入信源统计特性。引入信源统计特性。无失真：无失真：有效：有效：4.1无失真编码概述3考察无失真条件考察无失真条件：等概等概条件下的消息符号熵等概等概条件下的码字符号熵考虑信源的实际统计特性（非等概），实际消息熵为：考虑信源的实际统计特性（非等概），实际消息熵为：代入无失真条件得：代入无失真条件得：结论结论：即使m=n,只要 就有可能实现K0,0，只要满足：只要满足：则：当则：当L足够大时，可使译码差错小于足够大时，可使译码差错小于，反反之之，当当时时，译译码码一定出错。一定出错。解释：解释：定长编码定理给出了信源进行定长编码定理给出了信源进行等长编码等长编码所需码长的所需码长的理论极限值理论极限值。o结论结论：对信源进行二元等长编码时，每个信源符号所需码长：对信源进行二元等长编码时，每个信源符号所需码长的极限值为的极限值为 o结论结论：对于唯一可译码，：对于唯一可译码，每个每个信源符号至少需要用信源符号至少需要用 个个码符号来变换。码符号来变换。4.2定长编码定理定长编码定理2-进一步理解进一步理解若要求所得的等长码是唯一可译的，则必须：若要求所得的等长码是唯一可译的，则必须：o若若L1，则：，则：o当采用二元码编码时，当采用二元码编码时，m2，则：，则：4.2定长编码定理2-进一步理解每个码字（码序列）所能携每个码字（码序列）所能携带的平均信息量带的平均信息量每个源序列所包含的平均不确定性。即：信每个源序列所包含的平均不确定性。即：信源序列携带的信息量源序列携带的信息量o 等长有效性的无失真编码的条件：等长有效性的无失真编码的条件：码长下限：码长下限：o 为实现有效：为实现有效：误码率任意小的方向：误码率任意小的方向：?o结论结论：只要码字能够携带的信息量大于信源序列携带的信息：只要码字能够携带的信息量大于信源序列携带的信息 量，总可以实现几乎无失真编码量，总可以实现几乎无失真编码 考虑信源统计特性考虑信源统计特性讨论讨论：第三章：在考虑符号出现的概率和符号间相关性前提下第三章：在考虑符号出现的概率和符号间相关性前提下,每个每个 英文符号平均携带的信息量是英文符号平均携带的信息量是1.4bit/1.4bit/符号符号5bit/5bit/码符号。码符号。4.2 定长编码定理定长编码定理3-举例举例例例1：英文电报有：英文电报有32个符号（个符号（266），即），即n=32，若若m=2，L1（即对信源的逐个符号进行二元编码），（即对信源的逐个符号进行二元编码），则：则：bit解释解释：每个英文电报符号至少需要用每个英文电报符号至少需要用5 5位二元符号编码位二元符号编码 （每位二元符号可以携带（每位二元符号可以携带1bit1bit信息，即每个英文电报符号用了可以携带信息，即每个英文电报符号用了可以携带 5bit5bit信息的码符号即信息的码符号即5 5位二元码表示）位二元码表示）问题：问题：如何提高效率？如何体现有效性如何提高效率？如何体现有效性？结论：结论：若不考虑信源统计特性等长编码效率极低若不考虑信源统计特性等长编码效率极低!4.2定长编码定理定长编码定理4-进一步理解进一步理解解决方法：解决方法：字母个数为字母个数为n n，字母之间相关长度为，字母之间相关长度为L L的英文信源，其可能的字母序列的英文信源，其可能的字母序列总数为总数为 ；但其中大部分字母序列是无意义的字母组合，而且随着；但其中大部分字母序列是无意义的字母组合，而且随着L L的增加，这种无意义序列的总数越来越大。的增加，这种无意义序列的总数越来越大。进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编进行联合编码，即对字母序列编码，且只对哪些有意义的字母序列编码，即需编码的字母序列的总数码，即需编码的字母序列的总数 ,则平均每个信源符号所需则平均每个信源符号所需的码符号个数可以大大减少，从而提高了传输效率。的码符号个数可以大大减少，从而提高了传输效率。考察考察：方法方法：问题问题：会引入一定的误差！但当会引入一定的误差！但当L足够长后，误差可以任意小。足够长后，误差可以任意小。4.2定长编码定理定长编码定理5证明证明考察离散、随机序列信源的统计特性考察离散、随机序列信源的统计特性渐进等分割性（渐进等分割性（AEP）AEP描述：描述：渐进等分割定理：渐进等分割定理：（熵定理，遍历性定理）（熵定理，遍历性定理）设设是是离散无记忆信源离散无记忆信源输出的一个特定序列，则任给输出的一个特定序列，则任给和和，总可以找到一个整数，总可以找到一个整数，使当，使当时，有：时，有：引入：渐进等分割性（引入：渐进等分割性（AEP:Asymptotic Equipartition Property）特定序列的平均符号自信息特定序列的平均符号自信息随机矢量的平均符号熵随机矢量的平均符号熵任何一个离散随机序列信源当序列长度任何一个离散随机序列信源当序列长度L时时,信源序列会产信源序列会产生生两两极极分分化化.小小概概率率事事件件集集合合与与大大概概率率事事件件集集合合,即即nL=对于对于有性质有性质:对于对于有性质有性质:由此可见，信源编码只需对信源中由此可见，信源编码只需对信源中少数少数落入典型大概率事件的集合的符落入典型大概率事件的集合的符号进行编码即可。而对号进行编码即可。而对大多数大多数属于非典型小概率事件集合中的信源符号属于非典型小概率事件集合中的信源符号无需编码无需编码.4.2定长编码定理定长编码定理6AEP物理意义物理意义信源序列集合信源熵信源熵大概率事件熵大概率事件熵4.2定长编码定理定长编码定理7AEPAEP证明证明证明证明集合集合和和中的序列分别称为中的序列分别称为典型序列典型序列和和非典型序列非典型序列表示表示中所有中所有典型序列的集合典型序列的集合表示表示集合中序列的集合中序列的个数个数可以证明：对于任意小的正数可以证明：对于任意小的正数，当，当L足够大时，足够大时，4.2定长编码定理定长编码定理7AEPAEP证明证明证明证明还可以证明：对于任意小的正数还可以证明：对于任意小的正数，当，当L足够大时，足够大时，表示序列表示序列出现的出现的概率概率由切比雪夫不等式可得：由切比雪夫不等式可得：表示表示S中每个符号携带的信息量的方差中每个符号携带的信息量的方差例例2p(1)=p,p(0)=q,统计独立统计独立L长的序列长的序列:当当L8时，序列时，序列11000101和序列和序列011100101的概率为的概率为和和显然，显然，这两个序列不等概这两个序列不等概,当当L时，有一些序列时，有一些序列1出现的次数接近出现的次数接近Lp，这些序列的概率为，这些序列的概率为且这些序且这些序列近似等概分布。列近似等概分布。4.2定长编码定理定长编码定理8AEPAEP举例举例举例举例L长的序列长的序列，对于任意小的正数，对于任意小的正数满足式满足式的序列称为的序列称为典型序列典型序列即：即：典型序列集是哪些平均自信息任意小地接近信源熵的典型序列集是哪些平均自信息任意小地接近信源熵的N长序列长序列的集的集合合4.2定长编码定理定长编码定理9-AEPAEP应用应用应用应用AEP结论：当结论：当L足够大时，足够大时，所有所有典型序列出现的概率近似相等，即典型序列出现的概率近似相等，即典型序列为典型序列为渐渐进等概进等概序列序列可粗略认为可粗略认为典型序列出现的概率为典型序列出现的概率为所有所有典型序列的概率和接近为典型序列的概率和接近为1，即，即典型序列总数占信源序列的总数典型序列总数占信源序列的总数4.2定长编码定理定长编码定理9-AEPAEP应用应用应用应用o AEP应用：应用：n提出、证明都是基于离散无记忆序列信源提出、证明都是基于离散无记忆序列信源 n平稳遍历信源有类似结果平稳遍历信源有类似结果n体现信源统计特性体现信源统计特性n用以证明定长编码定理用以证明定长编码定理4.2定长编码定理定长编码定理10证明证明证明证明定长编码定理证明思路：定长编码定理证明思路：将取自将取自S，长为，长为L的信源符号序列分为集合的信源符号序列分为集合和和o 几个概念：几个概念：n 编码信息率：编码信息率：编码编码后后对应于对应于每个信源符号每个信源符号平均能载平均能载荷的最大信息量荷的最大信息量n 编码效率：编码效率：编码编码前后前后平均平均每个信源符号每个信源符号能载荷的最大信能载荷的最大信息量之比息量之比只对集合只对集合中的序列进行一一对应的等长编码中的序列进行一一对应的等长编码此时的误差为此时的误差为，计算误差，计算误差证明当证明当，且，且(K/L)log mH(S)+时，时，4.2定长编码定理定长编码定理11（物理意义）物理意义）结论：结论：可推广至离散、非平稳无记忆信源和有记忆信源可推广至离散、非平稳无记忆信源和有记忆信源（即（即H(S)=H(S)）情况情况只要码字传输的信息量大于信源序列携带的信息量，只要码字传输的信息量大于信源序列携带的信息量，总可以实现几乎无失真编码总可以实现几乎无失真编码二元码时，二元码时，m2：l最佳等长码时：最佳等长码时：4.2定长编码定理定长编码定理12（实际应用问题）实际应用问题）编译码同步问题编译码同步问题问题：如何使译码端知道码字起点问题：如何使译码端知道码字起点解决办法：解决办法：1 1、每个码字加短同步前缀、每个码字加短同步前缀 2 2、每若干码字加较长同步前缀、每若干码字加较长同步前缀o 分组长度与编译码复杂性、编译码延时等的关系分组长度与编译码复杂性、编译码延时等的关系n问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加问题：要实现有效，源序列分组很长，使得编译码复杂性和延时增加n解决办法：目前没有理想的解决办法解决办法：目前没有理想的解决办法o 定长信源编码的定长信源编码的理论意义理论意义远大于其远大于其实用价值实用价值4.2定长编码定理定长编码定理13（举例举例)例例3：设有一简单离散信源：设有一简单离散信源：L=1,n=2 对其进行近似于无失真的等长编码，若要求其编码效率为对其进行近似于无失真的等长编码，若要求其编码效率为96%，差错率低，差错率低 于于10-5，试求符号联合编码长度，试求符号联合编码长度L=？解：解：由编码效率：由编码效率：而：而：则：则：且：则：则：结论：可见结论：可见,需要需要4100万个信源符号联合编码万个信源符号联合编码,才能达到上述要求才能达到上述要求,这显然是不现实的这显然是不现实的.一般来说：当一般来说：当L L有限时，高传输效率的等长码往有限时，高传输效率的等长码往往要引入一定的失真和错误，它不能象变长编往要引入一定的失真和错误，它不能象变长编码那样可以实现真正的无失真编码码那样可以实现真正的无失真编码改变信源改变信源定长编码定长编码无失真信源编码实现方法一无失真信源编码实现方法一无失真信源编码实现方法二无失真信源编码实现方法二适应信源适应信源变长编码变长编码大概率大概率短码；小概率短码；小概率长码长码4.3变长信源编码变长信源编码-1几个码类的概念几个码类的概念非奇异码（单义码）非奇异码（单义码）唯一可译码唯一可译码前缀码（即时码、非延长码、异前置码）前缀码（即时码、非延长码、异前置码）最佳码（紧致码）最佳码（紧致码）Kraft定理即时码码长必须满足的条件定理即时码码长必须满足的条件唯一可译码存在定理唯一可译码存在定理变长编码定理（香农第一定理）变长编码定理（香农第一定理）4.3变长信源编码变长信源编码-2(几个码类的概念几个码类的概念)非奇异码（单义码）：非奇异码（单义码）：每一个码字仅对应信源中的一个信源符号（序列）。每一个码字仅对应信源中的一个信源符号（序列）。编码是单义的。编码是单义的。反之为奇异码或非单义码。反之为奇异码或非单义码。4.3变长信源编码变长信源编码-3(几个码类的概念几个码类的概念)唯一可译码唯一可译码编码单义、译码单义编码单义、译码单义对任何一个有限长度的信源字母序列，如果编码得到的码字对任何一个有限长度的信源字母序列，如果编码得到的码字母序列不与其他任何信源字母序列所对应的码字母序列相同。母序列不与其他任何信源字母序列所对应的码字母序列相同。非奇异码非奇异码=唯一可译码？唯一可译码？4.3变长信源编码变长信源编码-4(几个码类的概念几个码类的概念)前缀码前缀码是唯一可译码中的一类是唯一可译码中的一类在一个变长码中，在一个变长码中，没有任何一个码字是其他码字的前缀。没有任何一个码字是其他码字的前缀。译码时无需参考后续的码符号就能立即作出判断，进行译码时无需参考后续的码符号就能立即作出判断，进行无延时译码。无延时译码。又称即时码、非延时码又称即时码、非延时码例如逗点码：例如逗点码：1，01，001，00014.3变长信源编码变长信源编码-5(几个码类的概念几个码类的概念)最佳码最佳码唯一可译码的一类唯一可译码的一类其平均码长小于其他唯一可译码的平均长度其平均码长小于其他唯一可译码的平均长度所有的码所有的码非奇异码非奇异码唯一可译码唯一可译码前缀码前缀码最佳码最佳码4.3变长信源编码变长信源编码-6（几种类型的信源编码举例几种类型的信源编码举例几种类型的信源编码举例几种类型的信源编码举例）例例例例4 4：信源信源概概 率率pi 编码编码编编 码码编编 码码编编 码码编编 码码U11/2000000U21/401010110U31/810100011110U41/81110110111111定长唯一可译奇异奇异非奇非奇异异前缀前缀唯一唯一可译可译4.3变长信源编码变长信源编码-7(Kraft定理定理)引出引出码树码树构造即时码方法构造即时码方法Kraft定理描述定理描述即时码码长须满足的条件即时码码长须满足的条件Kraft定理证明略定理证明略实时唯一可译、可分离实时唯一可译、可分离A0B10C110D1110E11110ABA BBBBBAACDDED100010111010111101010111001001101110要求：须严格同步4.3变长信源编码变长信源编码-8(Kraft定理引出定理引出)问题问题：寻求：寻求实时唯一可译码实时唯一可译码方法：研究实时唯一可译码的码字可分离条件方法：研究实时唯一可译码的码字可分离条件简单信源：简单信源：“码树码树”概念（直观）概念（直观）一般信源：通过一般信源：通过KraftKraft定理给出定理给出实时唯一可译码（实时唯一可译码（前缀码）存在前缀码）存在 的条件的条件码树码树变长码的树图表示变长码的树图表示将变长码与码树建立将变长码与码树建立“一一对应一一对应”关系：关系：树根树根码字起点码字起点树枝数树枝数码的进制数码的进制数节点节点码字或码字的一部分码字或码字的一部分终止节点终止节点码字码字节数节数码长码长非满树非满树变长码变长码满树满树等长码等长码利用码树构造前缀码利用码树构造前缀码源符号源符号概率概率前前缀码s1s2s3s4011100010110111s10.04s4s30.160.64s20.164.3变长信源编码变长信源编码-9(Kraft定理定理)问题：问题：比较简单信源，码树方法可直接且直观构造前缀码比较简单信源，码树方法可直接且直观构造前缀码较复杂信源，直接画码树复杂且困难较复杂信源，直接画码树复杂且困难解决方法：解决方法：为便于分析，特别对含有很多符号种类的复杂信源，寻找一为便于分析，特别对含有很多符号种类的复杂信源，寻找一种与上述种与上述“树图树图”等效的解析式表达式等效的解析式表达式-Kraft不等式。不等式。结论：结论：KraftKraft定理给出定理给出码字可分离码字可分离或或前缀码存在前缀码存在的的充要条件充要条件4.3变长信源编码变长信源编码-10(Kraft定理定理)kraft定定理理：长长度度为为Ki（i=1,2,n）的的m（码码字字母母表表长长度度）进制前缀码存在的充要条件为：进制前缀码存在的充要条件为：证明：略证明：略物理意义：物理意义：给给定定信信源源个个数数N和和码码字字母母数数m，只只要要允允许许码码字字长长度度可可以以足足够够长长，就总可以满足就总可以满足Kraft不等式，从而得到前缀码。不等式，从而得到前缀码。只要适当选取码长，码字一定可以即时分离。只要适当选取码长，码字一定可以即时分离。(a)10(0.8)(0.2)(b)10(0.2)(0.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.51230004.3变长信源编码变长信源编码-11(唯一可译码定理唯一可译码定理)KraftKraft不等式给出的限制也是所有唯一可译码都必须满足的。不等式给出的限制也是所有唯一可译码都必须满足的。定理描述：定理描述：任何唯一可译码均满足任何唯一可译码均满足KraftKraft不等式。不等式。结论：结论：唯一可译码一定满足唯一可译码一定满足kraftkraft不等式不等式满足满足kraftkraft不等式的码不一定是唯一可译码，但一定存在至不等式的码不一定是唯一可译码，但一定存在至少一种唯一可译码少一种唯一可译码对任何唯一可译码均可在不改变码字长度的条件下得到相对任何唯一可译码均可在不改变码字长度的条件下得到相应的前缀码应的前缀码4.3变长编码定理变长编码定理12问题：问题：对于已知信源对于已知信源S可用码符号集可用码符号集X进行变长编码，而且对同一信源进行变长编码，而且对同一信源编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一编成同一码符号的前缀码或惟一可译码可有许多种。究竟哪一种最好呢种最好呢?从高速度传输信息的观点来考虑，当然希望选择由短从高速度传输信息的观点来考虑，当然希望选择由短的码符号组成的码字，就是用码长作为选择的码符号组成的码字，就是用码长作为选择准则。准则。引入：码的引入：码的平均长度平均长度。离散无记忆平稳信源离散无记忆平稳信源信源熵率为信源熵率为，码字个数为，码字个数为M，信源符号对应码长分别，信源符号对应码长分别为：为：ki,i=1,2,.n则前缀码平均码长：则前缀码平均码长：4.3变长编码定理变长编码定理13定理：定理：离散无记忆平稳信源离散无记忆平稳信源S，其熵为，其熵为 ，并有码符号集，并有码符号集C=c1,cm。对信源。对信源S进行编码进行编码,总可以找到一种编码方法，总可以找到一种编码方法，构成惟一可译码，使信源构成惟一可译码，使信源S中中每个信源符号每个信源符号所需的平均码长所需的平均码长满足满足:另一方面另一方面,必可以找到前缀码，使其平均码长满足必可以找到前缀码，使其平均码长满足 l对于给定的信源和码符号集，若有一个唯一可译码，其对于给定的信源和码符号集，若有一个唯一可译码，其平均长度小于所有其他唯一可译码，则称这种码为平均长度小于所有其他唯一可译码，则称这种码为紧致码紧致码或最佳码。或最佳码。唯一可译唯一可译码存在性码存在性紧致码的紧致码的存在性存在性证明：证明：Jensen不等式平均码长=下限值由右边不等式l香农第一定理（变长无失真信源编码定理）：香农第一定理（变长无失真信源编码定理）：设离散无记忆信源的熵为设离散无记忆信源的熵为 H H(S S)，它的，它的N N次扩展信源次扩展信源为为 ，对扩展信源，对扩展信源 进行编码。总可以找到一种编进行编码。总可以找到一种编码方法，构成唯一可译码，使平均码长满足：码方法，构成唯一可译码，使平均码长满足：其中l当时，有l当时，有代表平均到每个信源符号所需的码长代表平均到每个信源符号所需的码长l当时，每个码符号能够携带的信息量为：4.3变长编码定理变长编码定理14物理意义：物理意义：又称又称无噪信道编码定理无噪信道编码定理编码后的码符号信源尽可能为等概分布，使每个编码后的码符号信源尽可能为等概分布，使每个码符号码符号平均所含的信平均所含的信息量达到最大息量达到最大要做到无失真编码，变换每个要做到无失真编码，变换每个信源符号信源符号平均所需最少的平均所需最少的m元码元数就元码元数就是信源的熵率（以是信源的熵率（以m进制信息量单位测度，对应离散无记忆信源）进制信息量单位测度，对应离散无记忆信源）信源的熵率是描述每个信源的熵率是描述每个信源符号信源符号平均所需最少的比特数平均所需最少的比特数定理说明：定理说明：是存在性定理具有理论指导意义是存在性定理具有理论指导意义是构造性定理设计出多种具体编码方法是构造性定理设计出多种具体编码方法构造：构造：1、扩展信源至、扩展信源至2、取、取3、则：、则：k(s)满足满足kraft不等式，存在前缀码不等式，存在前缀码4、用树图法构造前缀码香农编码、用树图法构造前缀码香农编码4.3变长编码定理变长编码定理15编码效率编码效率l变长码编码效率：变长码编码效率：衡量各种编码方法的优略，判断是否最佳码。衡量各种编码方法的优略，判断是否最佳码。编码前平均每个信源符号携带的信息量为：编码前平均每个信源符号携带的信息量为：编码后平均每个信源符号携带的最大的信息量为：编码后平均每个信源符号携带的最大的信息量为：定义变长码编码效率为：定义变长码编码效率为：l另一种理解：另一种理解：最佳码（极限时）最佳码（极限时）每个信源符号每个信源符号的平均码长为：的平均码长为：某一方法得到的某一方法得到的每个信源符号每个信源符号的的平均码长为：平均码长为：定义变长码编码效率为：定义变长码编码效率为：4.3变长编码定理变长编码定理16编码效率编码效率比较：比较：定长编码的定长编码的编码效率编码效率：变长编码的编码效率：变长编码的编码效率：注意到：是指平均到每个信源符号所需的码长，而是指平均到每个信源符号所需的码长，而 也是平均到每也是平均到每 个信源符号的码长，所以它们是一致的，均表示无失真信源个信源符号的码长，所以它们是一致的，均表示无失真信源 编码的效率编码的效率。例例6：一离散无记忆信源：一离散无记忆信源其其熵熵为：为：用二元符号（用二元符号（0，1；m=2）构造一个）构造一个前缀码前缀码：此时此时每个信源符号每个信源符号平均码长平均码长为：为：编码效率编码效率为：为：为提高编码效率，对为提高编码效率，对S的的2次扩展信源进行次扩展信源进行2维联合编码：维联合编码：构造一个扩展信源构造一个扩展信源S2的前缀码：的前缀码：前缀码前缀码s1s19/160s1s23/1610s2s13/16110s2s21/16111此时此时平均码长平均码长为：为：此时信源此时信源S中中每个符号每个符号对应的对应的平均码长平均码长为：为：编码效率编码效率为：为：同样可得：同样可得：定长编码与变长编码效率比较：定长编码与变长编码效率比较：例例6与与例例3相比：相比：同一个信源，当要求编码效率达到同一个信源，当要求编码效率达到96时，时，等长码等长码需要需要4100万个信源符号联合编码；万个信源符号联合编码；变长码变长码只需只需2个符号（二次扩展信源）联合编码；个符号（二次扩展信源）联合编码；结论结论：采用变长编码，：采用变长编码，L不需要很大就可以达到相当高的编码效率，不需要很大就可以达到相当高的编码效率，而且可以实现无失真编码。且随着而且可以实现无失真编码。且随着L的增大，编码效率越来越接近于的增大，编码效率越来越接近于1。无失真信源编码无失真信源编码等长编码等长编码变长编码变长编码完全无失真完全无失真效率差效率差较好的效率、较好的效率、一定的误差一定的误差可实现、有实用可实现、有实用难实现、无实难实现、无实用用无失真、较好无失真、较好的效率的效率可实现、有实用可实现、有实用总结：总结：定长编码定理定长编码定理近似无失真等长编码的条件近似无失真等长编码的条件有效性、无失真性无法兼得有效性、无失真性无法兼得考察信源统计特性考察信源统计特性利用信源序列的利用信源序列的AEP特性特性定长编码定理研究思路定长编码定理研究思路变长编码定理研究思路变长编码定理研究思路无失真唯一可译码无失真唯一可译码工程可实现前缀码工程可实现前缀码码树构造简单前缀码码树构造简单前缀码KRAFT不等式前缀不等式前缀码存在条件码存在条件香农定理最佳码存在条件香农定理最佳码存在条件定长编码定理定长编码定理变长编码定理变长编码定理1、存在码长为、存在码长为K的定长编码方法的定长编码方法2、L足够大时，几乎无失真足够大时，几乎无失真条件条件1、存在无失真的变长编码方法、存在无失真的变长编码方法2、最佳码的码长上界：、最佳码的码长上界：条件条件结论结论结论结论4.4 最优编码最优编码定理定理1:对每一给定的离散无记忆信源对每一给定的离散无记忆信源,存在一个存在一个最优的二元前缀码最优的二元前缀码.这个码中这个码中最少发生最少发生的两个码的两个码字字必具有相同必具有相同的长度的长度,且码中相同长度的码字有且码中相同长度的码字有两个或两个以上时两个或两个以上时,其中必有两个码字的差别只其中必有两个码字的差别只在在最后一位最后一位.4.4 最优编码最优编码定理说明定理说明没给出编码全过程没给出编码全过程最优二元前缀码，两个最小概率信源字母对应的码字等长，最优二元前缀码，两个最小概率信源字母对应的码字等长，且差别在最后一位。且差别在最后一位。两个最小概率信源字母对应的码字两个最小概率信源字母对应的码字相同部分相同部分的最后一位可以的最后一位可以通过缩减信源的方法通过缩减信源的方法得到。得到。缩减方法：缩减方法：原信源原信源缩减信源缩减信源4.4 最优编码最优编码定理定理2:设设C是某信源经是某信源经缩减后缩减后所得的所得的缩减信源缩减信源的最优前缀码，将的最优前缀码，将C中由原信源中的最小概率中由原信源中的最小概率的两个字母缩减得到的字母所对应的码字后各的两个字母缩减得到的字母所对应的码字后各加加0和和1,作为作为原信源原信源的最小概率的两个码字的最小概率的两个码字,而而其余码字不变其余码字不变,则这样得到的码则这样得到的码C对原信源也是对原信源也是最优的最优的.4.5实用的无失真信源编码方法举例实用的无失真信源编码方法举例香农（香农（Shannon)码码费诺（费诺（Fano）码）码霍夫曼（霍夫曼（Huffman）编码）编码编码方法编码方法特点特点应用应用问题问题思路：平均码长与信源特性相匹配思路：平均码长与信源特性相匹配适用数据源：离散无记忆信源适用数据源：离散无记忆信源香农编码、费诺编码、霍夫曼编码香农编码、费诺编码、霍夫曼编码4.5实用的无失真信源编码方法举例香农编码步骤以二进制香农码为例：以二进制香农码为例：排序排序将信源符号按概率从大到小的顺序排列，为方便起见，令将信源符号按概率从大到小的顺序排列，为方便起见，令 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实用的无失真信源编码方法举例例例7有一单符号离散无记忆信源有一单符号离散无记忆信源对该信源编二进制香农码。其编码过程如下表所示。对该信源编二进制香农码。其编码过程如下表所示。香农编码举例1二进制香农编码二进制香农编码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编码效率编码效率离散无记忆信源的熵：离散无记忆信源的熵：平均码长：平均码长：采用香农编码后的信息率：采用香农编码后的信息率：编码效率：编码效率：结论：结论：1、香农编码对信源进行了压缩。若对该信源采用等长编码，香农编码对信源进行了压缩。若对该信源采用等长编码，要做到无失真译码，每个符号至少要用要做到无失真译码，每个符号至少要用3个比特表示。个比特表示。2、编码效率并不是很高。编码效率并不是很高。香农编码举例2 以二进制费诺编码为例，编码步骤如下：以二进制费诺编码为例，编码步骤如下：排序：排序：将概率按从大到小的顺序排列，令将概率按从大到小的顺序排列，令p(x1)p(x2)p(xn)分组：分组：按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二按编码进制数将概率分组，使每组概率尽可能接近或相等。如编二 进制码就分成两组，编进制码就分成两组，编m进制码就分成进制码就分成m组。组。编码：编码：给每一组分配一位码元。给每一组分配一位码元。重复：重复：将每一分组再按同样原则划分，重复步骤将每一分组再按同样原则划分，重复步骤2和和3，直至概率不再可分，直至概率不再可分 为止为止。费诺编码步骤4.5实用的无失真信源编码方法举例例例8 设有一单符号离散信源设有一单符号离散信源对该信源编二进制费诺码。编码过程如下表所示。对该信源编二进制费诺码。编码过程如下表所示。费诺编码举例1010101010100011011011101111222344编码效率编码效率该信源的熵该信源的熵:平均码长平均码长:编码效率编码效率:结论：结论：费诺码比较适合于费诺码比较适合于每次分组概率都很接近每次分组概率都很接近的信源。特别是对的信源。特别是对每次每次分组概率都相等分组概率都相等的信源进行编码时，可达到理想的编码效的信源进行编码时，可达到理想的编码效率。率。费诺编码举例34.5实用的无失真信源编码方法举例霍夫曼编码编码规则：编码规则：1)排序：排序：将信源消息将信源消息U按概率大小排序（由大至小）按概率大小排序（由大至小）p(x1)p(x2)p(xn)2)定规则并编码：定规则并编码：从从最最小小概概率率的的两两个个符符号号开开始始编编码码，并并赋赋予予一一定定规规则则，如如下下支支路路小小概概率率为为“1”，上上支支路路大大概概率率为为“0”。若若两两支支路路概概率率相相等等，仍仍为为下下支支为为“1”上支为上支为“0”。3)概率合并：将已编码两支路概率合并，重新排队，编码。概率合并：将已编码两支路概率合并，重新排队，编码。4)重复：重复步骤重复：重复步骤3）直至合并概率归一时为止。）直至合并概率归一时为止。5)确定最终码子：从概率归一端沿树图路线逆行至对应消息编码。确定最终码子：从概率归一端沿树图路线逆行至对应消息编码。霍夫曼编码举例霍夫曼编码举例1例9：0101011001010110霍夫曼编码举例霍夫曼编码举例1例9：010101100101011011霍夫曼编码举例霍夫曼编码举例1例9：010101100101011011000霍夫曼编码举例霍夫曼编码举例1例9：010101100101011011000001霍夫曼编码举例霍夫曼编码举例1例9：010101100101011011000001010霍夫曼编码举例霍夫曼编码举例1例9：0101011001010110110000010100110霍夫曼编码举例霍夫曼编码举例1例9：010101100101011011000001010011001110霍夫曼编码举例霍夫曼编码举例1例9：01010110010101101100000101001100111001111霍夫曼编码举例霍夫曼编码举例2特点：特点：编码不是唯一的编码不是唯一的保证了概率大的符号对应于短码，概率小的符号对应于长码，而保证了概率大的符号对应于短码，概率小的符号对应于长码，而且短码得到充分利用且短码得到充分利用每次缩减信源的最后二个码字总是最后一位码元不同，前面各位每次缩减信源的最后二个码字总是最后一位码元不同，前面各位码元相同（二元码情况）码元相同（二元码情况）每次缩减信源的最长两个码字具有相同码长每次缩减信源的最长两个码字具有相同码长 后三个特点保证了所得到的后三个特点保证了所得到的huffman码一定是最佳码（证明见李亦农码一定是最佳码（证明见李亦农信息信息论基础教程论基础教程2005年年1月第一版月第一版p114）每次对缩减信源两个概率最小的符号分配每次对缩减信源两个概率最小的符号分配“0”和和“1”码元是任码元是任意的，所以可得到不同的码字。只要意的，所以可得到不同的码字。只要在各次缩减信源中保持码元在各次缩减信源中保持码元分配的一致性分配的一致性，即能得到可分离码字。，即能得到可分离码字。不同的码元分配，得到的具体码字不同，但码长不同的码元分配，得到的具体码字不同，但码长ki不变，平均码长不变，平均码长 也不变，所以没有本质区别；也不变，所以没有本质区别；缩减信源时，若合并后的新符号概率与其他符号概率相等，从编缩减信源时，若合并后的新符号概率与其他符号概率相等，从编码方法上来说，码方法上来说，这几个符号的次序可任意排列，编出的码都是正这几个符号的次序可任意排列，编出的码都是正确的，但得到的确的，但得到的码字不相同码字不相同。不同的编法得到的不同的编法得到的码字长度码字长度ki也不尽也不尽相同相同。霍夫曼编码举例3例例10 单符号离散无记忆信源单符号离散无记忆信源 用两种不同的方法对其编二进制哈夫曼码。用两种不同的方法对其编二进制哈夫曼码。方法一方法一：合并后的新符号排在其它相同概率符号的后面。：合并后的新符号排在其它相同概率符号的后面。霍夫曼编码举例霍夫曼编码举例4对应该图画出树图 霍夫曼编码举例霍夫曼编码举例6xiP(xi)码字码长x10.411x20.2012x30.20003x40.100104x50.100114方法二方法二：合并后的新符号排在其它相同概率符号的前面。合并后的新符号排在其它相同概率符号的前面。霍夫曼编码举例霍夫曼编码举例7霍夫曼编码举例霍夫曼编码举例8xiP(xi)码字码长x10.4002x20.2102x30.2112x40.10103x50.101130001011x5x4x3x2x11单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均单符号信源编二进制哈夫曼码，编码效率主要决定于信源熵和平均码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，码长之比。对相同的信源编码，其熵是一样的，采用不同的编法，得到的平均码长可能不同。平均码长越短，编码效率就越高。得到的平均码长可能不同。平均码长越短，编码效率就越高。编法一的平均码长为编法一的平均码长为编法二的平均码长为编法二的平均码长为可见可见 ，本例两种编法的平均码长相同，所以编码效率相同。，本例两种编法的平均码长相同，所以编码效率相同。霍夫曼编码举例霍夫曼编码举例9思考题：哪种方法更好？思考题：哪种方法更好？讨论：1)两种方法平均码长相等。2)计算两种码的码长方差：第二种方法编出的码码字长度变化较小，便于实现。4.5实用的无失真信源编码方法举例实用的无失真信源编码方法举例霍夫曼霍夫曼编码应用编码应用考察考察例例6和下例：例和下例：例12：对以下平稳信源进行霍夫曼编码：对以下平稳信源进行霍