《信息论与编码》课件第4章 离散信源编码理论-0525.ppt

1、目录u4.1 信源编码的基本概念u4.2 渐近等同分割性u4.3 信源无失真编码 4.3.1 等长码 4.3.2 变长码u4.4 信息率失真函数及性质 4.4.1失真测度 4.4.2 信息率失真函数的定义 4.4.3 信息率失真函数的性质u 4.5 信息率失真函数的计算u 4.6 信息率失真函数的迭代算法u 4.7香农第三定理通信通信本质本质信源信源信宿信宿信息信息 信源输出的符号经信源输出的符号经过信道传送到信宿，过信道传送到信宿，在信宿在信宿精确或者近似精确或者近似重现重现信源发送的信息信源发送的信息 解决两个问题：解决两个问题：(1)信源的输出如何描述，信源的输出如何描述，即如何计算信源

2、产生的即如何计算信源产生的信息量信息量(2)如何表示信源的输出，如何表示信源的输出，即即信源编码信源编码问题问题 信源输出的符号经过信道传送到信宿，在信宿信源输出的符号经过信道传送到信宿，在信宿精确或者精确或者近似重现近似重现信源发送的信息信源发送的信息 要求精确地重现信源的输出，信要求精确地重现信源的输出，信源产生的信息全部无损传送到信源产生的信息全部无损传送到信宿，对信源进行宿，对信源进行无失真编码无失真编码不要求在信宿精确重现不要求在信宿精确重现信源的输出，允许信息信源的输出，允许信息传输过程中出现一定失传输过程中出现一定失真，这就是真，这就是限失真编码限失真编码问题。问题。回顾回顾通信

3、系统的信道容量是有限的，根据第通信系统的信道容量是有限的，根据第3章中信源章中信源与信道匹配理论，为了有效传输信息，信道的输与信道匹配理论，为了有效传输信息，信道的输入分布应当尽可能接近信道要求的入分布应当尽可能接近信道要求的最佳分布最佳分布。实际信道很多都是对称信道，最佳分布为等概率分布，这就要求对信源进行编码，除去信源输出符号之间的相关性，从而实现信道输入与信道的匹配。4.1 信源编码的基本概念信源编码的基本概念 编编码码器器码码表表信信源源信信宿宿X Y 是对信源输出符号进行描述，将原始符号按是对信源输出符号进行描述，将原始符号按照一定的规则进行变换，以满足信息传输的要求照一定的规则进行

4、变换，以满足信息传输的要求。信源编码信源编码将信道编译码看作信道的将信道编译码看作信道的一部分，从而突出信源编一部分，从而突出信源编码，此时的信道称为编码码，此时的信道称为编码信道。信道。编码信道是一种广义信编码信道是一种广义信道。道。不考虑信道编码、译码不考虑信道编码、译码过程中是否会引入失真过程中是否会引入失真或者错误或者错误。12(,.,)iiiiNxxxxixiy按照一定按照一定的变换的变换在研究信源编码时，一般认为在研究信源编码时，一般认为信道是理想信道是理想的，的，即不考虑编码信道的干扰或者噪声对信源符号即不考虑编码信道的干扰或者噪声对信源符号重建的影响，认为信道编码具有重建的影响

5、，认为信道编码具有足够好的检错足够好的检错和纠错能力和纠错能力，信道译码器能够，信道译码器能够准确重建准确重建信源编信源编码器输出的消息码器输出的消息在有些情况下，信源编码也需要考虑编码方法的在有些情况下，信源编码也需要考虑编码方法的抗误码能力，并且将抗误码作为衡量信源编码的抗误码能力，并且将抗误码作为衡量信源编码的一项指标一项指标假设信源序列符号长度为 N，等待编码的符号序列为 这样产生的码称为分组码或这样产生的码称为分组码或者块码者块码12,.,qCCCC0,1,.,1Dd 例例4.1 表4.1为信源编码所使用的码表，信源输出序列的长度为N=1，信源共有4个符号，对应的概率空间为 输出序列

6、输出序列称为称为码字码字码字由码表产生。码字由码表产生。码字取值于一个码字集合，称为码字取值于一个码字集合，称为码集码集码集码集码字由码字由若干个符号构成，若干个符号构成，这些符号构成集合，称这些符号构成集合，称为为码符号集合码符号集合码符号码符号集合集合码符号集合码符号集合元素数量为元素数量为d，则称为，则称为d元码元码码字Ci的符号数量称为码字长度，记作Li12341234()()()()()aaaaXp ap ap ap ap x对于码1100a 201a 310a 411a 信源编码器输出共有4个码字，分别为00、01、10和11，码字的长度都为2。二元码码2的码字同样是由二进制码符号

7、组成，与码1不同的是，并非所有的码字都具有相同的码字长度，所以称这种码为变长码。v1.非奇异码非奇异码v一个码是非奇异的，如果信源编码器输入的每个元素映射为不同的码字，即ijijCCxxv非奇异是输入序列的每个取值都得以明确描述的充分条件。v例如，采用表4.1中码2进行编码，由于编码器输入的每个元素映射为不同的码字，所以为非奇异码。v2.奇异码奇异码v一个码是奇异的，如果存在信源编码器的不同输入序列的元素映射为相同的码字，即 ijijCCxxv3.唯一可译码唯一可译码v任意有限长的码符号序列，只能被唯一地译码为所对应的信源符号序列，这样的码称为唯一可译码，即编码的码字只有一种可能信源序列与之相

8、对应，这就要求码是非奇异的。v例如,对表4.1给定的四个信源符号进行不等长编码v这样的码就是非唯一可译码的，比如给定码序列001，就存在两种解释：0，01和001，相应的译码就有两种：a1a2或者a3，因此这种编码不是唯一可译码的。10a 201a3001a，v4.即时码即时码v一个码称为即时码，如果不需要考虑后续的码符号，可以直接根据当前的码符号序列正确译出相应的码字。即时码的充要条件是没有一个码字是其它码字的前缀，所以即时码是唯一可译码；反之，唯一可译码不一定是即时码，有时可以通过搜遍整个码符号序列自后至前进行译码。例如，使用表4.1中的码2对信源进行编码，编码产生的比特串01101111

9、00110，译码器译码时不需要考虑后续码符号，直接解码为134213a a a a a a，所以码2为即时码 v5.树码树码v通常情况下可用码树来表示各个码字的构成，如果码序列符号为进制的，可以使用个符号的码树来构造码字。u每个码树有一个树根，树根有d个树枝，树枝的尽头称为节点，每个节点生出的树枝的数量等于码符号数量d，形成d进制的码树。u当某个节点被安排为一个码字后，不再继续生出树枝，该节点称为终端节点。u每个树枝分别标上码符号，终端节点对应的码字就是从根节点出发到终端节点经过的路径所对应的码符号按顺序排列而成。v树码一定是即时码，反过来，任何即时码都可以用树码来表示。v利用树码可以推导出唯

10、一可译码的充分必要条件。v定理定理4.1 采用d进制符号集进行信源编码，产生的码字Ci所对应的长度为Li，则即时码存在的充分必要条件为 11iqlidv该不等式就是克劳夫特不等式(Kraft Inequality)4.2渐近等同分割性渐近等同分割性11NiiXXN1211log(.)NNp X XX12(.)Np X XX典型典型序列序列渐近等同分割性中的概念渐近等同分割性中的概念等长编码的基础等长编码的基础对于独立同一分布对于独立同一分布(i.i.d)的随机变量的随机变量X，和充分大的，和充分大的N大数定律大数定律的内容的内容 通俗说法通俗说法算术平均算术平均以概率逼以概率逼近统计平近统计平

11、均均independent identically distributed逼近其数学期望逼近其数学期望EX渐近等渐近等同分割同分割性性12(.)Np X XXX1,X2,XN服从独立同一分布服从独立同一分布逼近熵逼近熵H观察序列的概率观察序列的概率逼近逼近2NH自信息量自信息量的算术平的算术平均逼近熵均逼近熵|1p XEX 公式公式表示表示v例例4.2 随机变量X的概率空间为 01()(0)(1)Xp xpppq111211111loglog()(.)()NNiiiNiI XNp X XXNp XN121(.)()NNiip X XXp X独立独立序序列列分分类类将所有序列分为两个集合将所有序

12、列分为两个集合典型集合：典型集合：样样点值自信息量点值自信息量平均逼近熵平均逼近熵非典型集合：非典型集合：包含剩余序包含剩余序列。列。主要关心主要关心典型序典型序列列，典型序列的，典型序列的任何特性都是以任何特性都是以大概率成立的，大概率成立的，而且决定了样点而且决定了样点值的主要特性值的主要特性如果随机变量如果随机变量12,.,NX XX都服从独立同一分布都服从独立同一分布那么序列那么序列12(.)Nx xx的概率为的概率为1()Niip x如序列如序列(1,0,1,1,0,1)的概率为的概率为24iiNxxpqp qN足够大时，序列中“0”的数量以大概率逼近于Np 1渐近等同分割性渐近等同

13、分割性 v定理定理4.2 如果如果X1,X2,XN服从独立同一分布服从独立同一分布p(x)，那么，那么v以概率逼近H(X)。121log(.)Np X XXNv证明：证明：X服从独立同一分布 p(x),那么log()ip X服从独立同一分布。根据弱大数定律 1211log(.)log()Niip x xxp xNN log()Ep x-()HX以概率定义定义4.1 关于关于p(x)的典型集合的典型集合()NA是序列是序列12(.)Nx xxX的集合，具有下列性质的集合，具有下列性质()()1 22(.)2N H XN H XNp xxx含义含义对于给定的基本信源和参数对于给定的基本信源和参数，

14、对于一个具体排，对于一个具体排列列(样本样本)，满足上述关系，则属于典型序列的，满足上述关系，则属于典型序列的一个元素；所有这类元素构成典型集合一个元素；所有这类元素构成典型集合例如例如 一个二元信源，一个二元信源，p(0)=0.75,p(1)=0.25,则则H(x)=0.811，取，取=0.111，N=100()2821.758 10N H X()2228.47 10N H X100个元素都是个元素都是0的序列，对应的联合概率为的序列，对应的联合概率为0.75100=3.2110-13,那么该序列就不是典型序列那么该序列就不是典型序列80个元素都是个元素都是0的序列，对应的联合概率为的序列，

15、对应的联合概率为0.75800.2520=9.210-23,那么该序列就是那么该序列就是典型序列典型序列定理定理4.3()12(,.,)NNx xxA121()log(,.,)()NH Xp x xxH XN(1)如果，那么(2)当N充分大时，()1Np A(3)其中|A|表示集合A的元素个数()()|2NN H XA()()|(1)2NN H XA(4)当N充分大时，所以典型序列的概率几乎为几乎为1，典型序列的所有元素几乎是等概率的，元素个数元素个数几乎是 2NH性质性质(1)可以根据定义直接证明可以根据定义直接证明证明证明两边同时取对数两边同时取对数12()(.)()NN H Xlbp x

16、 xxN H X 121()(.)()NH Xlbp x xxH XN 性质性质(2)可以由定理可以由定理4.2加以证明加以证明N 121|log(.)()|1Npp x xxHXN 令令典型典型 序列集合以概率逼近序列集合以概率逼近1，根据大数定理，根据大数定理得到性质得到性质2性质性质(3)1()NxpXX()()NApXX()()2NN H XAX()()2|N H XNA 渐近等同渐近等同分割含义分割含义典型序列典型序列定义定义相同数据相同数据相加相加性质性质(4)对于充分大的对于充分大的N()1Np A()1Np A()()2NN H XAX()()2|N H XNA ()()|(1

17、)2NN H XA得到得到定理定理4.4 设离散无记忆信源设离散无记忆信源X的特定序列的特定序列12()iiiiNx xx对于任意给定的对于任意给定的00存在一个整数存在一个整数N00NN时时log()|()|1ippH XN典型序列的平均典型序列的平均自信息量以概率自信息量以概率逼近熵逼近熵 2 渐近等同分割性与编码渐近等同分割性与编码数据数据压缩压缩服从独立同一分布的随机变量服从独立同一分布的随机变量X1,X2,XN构成随机变量序列构成随机变量序列XN为了实现为了实现数据压缩数据压缩将序列所有可能将序列所有可能取值分类两类取值分类两类典型集合及其补集每个集合都按每个集合都按照某种顺序对照某

18、种顺序对序列进行序列进行排序排序序列排序的序号来描述每序列排序的序号来描述每个序列；实现数据压缩个序列；实现数据压缩方法方法1典型序列数量不大于典型序列数量不大于2N(H(X)+)编码：编码：0+序列编号码长码长非典型序列非典型序列编码：编码：1+序列编号码长：码长：log|1NX()2N H前前缀缀码码这是一种无失这是一种无失真编码方法真编码方法v上述的编码方案具有下列性质：上述的编码方案具有下列性质：u码与序列之间是码与序列之间是一一对应一一对应的，的，第一位是前缀码第一位是前缀码，表示码的长，表示码的长度或者类型。度或者类型。u非典型序列采用的是枚举法，尽管没有考虑非典型序列的长非典型序

19、列采用的是枚举法，尽管没有考虑非典型序列的长度一定小于信源符号的个数，但是这种描述方法也是十分有度一定小于信源符号的个数，但是这种描述方法也是十分有效的，因为非典型序列对应的概率较小，对平均长度的贡献效的，因为非典型序列对应的概率较小，对平均长度的贡献较小。典型序列的最小描述长度约为较小。典型序列的最小描述长度约为NH。方法方法2非典型序列不参与编码非典型序列不参与编码典型序列排序的序号典型序列排序的序号来描述每个序列来描述每个序列()2N H码长一旦非典一旦非典型序列出型序列出现，出现现，出现译码错误译码错误由于非典型序由于非典型序列对应概率小，列对应概率小，几乎无失真几乎无失真编编码码方法

20、方法3非典型序列使用非典型序列使用典型序列代替典型序列代替一旦非典一旦非典型序列出型序列出现，同样现，同样出现译码出现译码错误错误其他与方其他与方法法2一样一样等长编码理论是建等长编码理论是建立在后两种编码方立在后两种编码方法基础上法基础上4.3 信源无失真编码信源无失真编码 v无失真信源编码就是要求信源符号与码字之间形成一一映射关系，并且要求编码输出的码字序列对应的反变换是唯一的，即是唯一可解码的，否则会造成译码错误或者失真。根据信源编码输出码长的特点，可以将信源编码分为等长编码和变长编码。如果对于信源不同的输出符号，码字的长度总是相同的，这样的编码称为等长编码，即v反之，如果编码产生的码长

21、不完全相同，称这样的码为变长码。ijijlllxxv定理定理4.5 设离散无记忆信源设离散无记忆信源X的符号数量为的符号数量为r，信源，信源熵为熵为H(X)，对应，对应N次扩展信源次扩展信源XN为为1212()()()NNNrrXpppPv现在使用码符号个数为现在使用码符号个数为d的码符号集合，对次扩展的码符号集合，对次扩展信源进行等长编码，码长为信源进行等长编码，码长为l，对于任意，对于任意0，只，只要满足要满足()loglH XNdv则当则当N足够大时，错误译码的概率为任意小，即可足够大时，错误译码的概率为任意小，即可实现几乎无失真编码。实现几乎无失真编码。反之，如果反之，如果()2log

22、lHXNdv则当充分大时，译码错误的概率趋向则当充分大时，译码错误的概率趋向1，不可能实，不可能实现无失真编码。现无失真编码。v 证明：证明：根据渐近等分割定理可知，在离散无记忆根据渐近等分割定理可知，在离散无记忆信源输出中，典型序列对应的概率应当满足条件信源输出中，典型序列对应的概率应当满足条件()()2()2N H XN H Xipv设典型序列集合设典型序列集合G中序列数量为中序列数量为NG，于是有，于是有()2()1iGN H XGiNNp()1()2iGN H XiGNpN()()(1)22N H XN H XGNv当当N足够大时，典型序列的数量所占比例很小，这足够大时，典型序列的数量

23、所占比例很小，这样就可以只对典型序列进行一一对应的等长编码，样就可以只对典型序列进行一一对应的等长编码，那么码字的总数应当不小于那么码字的总数应当不小于NG，即，即 v典型序列集合中所有的序列都有不同的码字与之相对应，而非典型序列没有相应的码字。v尽管非典型序列出现的概率很小，但是仍然有可能出现，一旦非典型序列出现，就会造成译码错误，相应的错误概率就是非典型序列集合的概率，即 lGdN()2lN H XGdN()loglH XNd2()()(,)CiED I aPp GNN如果满足/()/logl NH Xd当N趋向无穷大时，译码错误的概率PE趋向于0 反之，如果等长码的码长满足()2lo g

24、lHXNd()2)2lN H Xd该定理可以扩展到平稳离散有记忆信源，但是要求有记忆信源的极限熵存在，并将上述定理中的替换为极限熵。v上述定理的意义在于：u(1)对于给定的离散无记忆信源X和码符号集合D，如果对的次扩展信源进行无失真等长编码，那么当码长满足下列条件 log()ldHXNv时，一定存在一种编码方案，使得正确译码的错误概率趋向0，即能够实现无失真编码；u反之，如果上述不等式不成立，不可能存在一种编码方案，能使得正确译码的概率趋向0，也就是说，不可能进行无失真编码。v(2)对于给定的信源离散无记忆对于给定的信源离散无记忆X，信源的熵是一定的，当码，信源的熵是一定的，当码符号数量选定时

25、，可以增加信源序列的长度符号数量选定时，可以增加信源序列的长度N，使得无失真，使得无失真编码产生的每个符号平均长度尽可能小，但是无论怎样增加编码产生的每个符号平均长度尽可能小，但是无论怎样增加序列长度序列长度N，信源每个符号的平均码长不可能小于，信源每个符号的平均码长不可能小于H(X)/logd，即平均码长的极限为即平均码长的极限为H(X)/logd。v(3)当序列长度当序列长度N一定，译码错误概率为一定，译码错误概率为 2()(,)iED I aPNN221()()log()()riiiiD I ap ap aHX其中 定义定义4.2 设离散无记忆信源设离散无记忆信源X的熵为的熵为H(x)，

26、对，对N次扩展信源次扩展信源的符号序列的符号序列XN进行等长无失真编码，码长为进行等长无失真编码，码长为L，定义，定义自信息自信息量方差量方差loglRdN为编码信息率。为编码信息率。每个符号每个符号的平均码的平均码长长 从定理从定理4.5可知，如果编码信息率可知，如果编码信息率RH(x),总是存在一种总是存在一种编码方法，能够实现无失真编码；反之，则不能够实现无失编码方法，能够实现无失真编码；反之，则不能够实现无失真编码。真编码。定义定义4.3 定义编码信息率与信源熵之比为编码效率定义编码信息率与信源熵之比为编码效率()()lo gHXHXlRdN已知自信息量方差和编码效率情况下，信源序列长

27、度已知自信息量方差和编码效率情况下，信源序列长度N与最佳编码效率与最佳编码效率和允许错误概率和允许错误概率之间的关系之间的关系222()()(1)iD I aNHX允许错误概率越小，编码效率越高，信源序列的长允许错误概率越小，编码效率越高，信源序列的长度就越大度就越大例例4.3 设某离散无记忆信源的熵为设某离散无记忆信源的熵为H(x)=0.6比特比特/符号，符号，采用二元码编码，分别使用长度为采用二元码编码，分别使用长度为10和和100的序列进行的序列进行等长无失真编码，分别计算最短平均码长和编码效率。等长无失真编码，分别计算最短平均码长和编码效率。解：当解：当N=10时时1()/log10

28、0.6/1 6lNH Xd比特比特/10符号符号考虑到码长必须为整数，所以最短码长为考虑到码长必须为整数，所以最短码长为17l 最短平均码长为最短平均码长为1170.71 0llN比特比特/符号符号编码效率为编码效率为111()()0.685.7%0.7logH XH XlRdN当当N=100时时2()/log100 0.6/1 60lNH Xd比特比特/100符号符号261l 平均码长为平均码长为22610.61100llN比特比特/符号符号编码效率为编码效率为222()()0.698.4%0.61logH XH XlRdN结论结论：随着随着N的增加，平均码长减小，编码效率增加的增加，平均码

29、长减小，编码效率增加不过序列长度的增加，意味着编码复杂度相应增加，编不过序列长度的增加，意味着编码复杂度相应增加，编码付出的代价会越大，可见通过无限制增加码长提高编码付出的代价会越大，可见通过无限制增加码长提高编码效率并不总是一种有效方法。码效率并不总是一种有效方法。例例4.4设离散无记忆信源为设离散无记忆信源为12()0.80.2Xaap x如果要求编码效率为如果要求编码效率为92%，允许错误概率为，允许错误概率为510求编码序列的长度求编码序列的长度 解：信源的熵为解：信源的熵为()0.8 0.8 0.2 0.2 0.722H Xlblb比特比特/符号符号222()0.8 0.80.2 0

30、.20.7220.64iD I alblb自信息量方差为自信息量方差为如果采用二进制码，则序列长度应当满足如果采用二进制码，则序列长度应当满足2722()1.62 10()(1)iD I aNHX 从指标来看，编码效率从指标来看，编码效率和允许错误概率的要求和允许错误概率的要求并不高，但是序列的长并不高，但是序列的长度却很大。度却很大。这是因为等这是因为等长码的编码长码的编码没有充分利没有充分利用信源统计用信源统计特性的结果。特性的结果。等长编码使用等长编码使用概率方式概率方式：根据概率大小，将序列划根据概率大小，将序列划分为典型序列和非典型序分为典型序列和非典型序列；列；所有典型序列的码长相

31、等，所有典型序列的码长相等，没有充分利用每个序列的没有充分利用每个序列的概率指导编码，所以编码概率指导编码，所以编码效率难以提高效率难以提高等长编码的平均码长等长编码的平均码长受到熵的约束；受到熵的约束；增加序列长度有利于增加序列长度有利于提高编码效率。提高编码效率。归纳归纳序列长度增加会提高序列长度增加会提高编码复杂度。编码复杂度。2.变长码变长码 u等长码编码定理表明：增加序列长度可以提高信源编码效率。等长码编码定理表明：增加序列长度可以提高信源编码效率。u但序列长度的增加，会增加系统编码的复杂度。但序列长度的增加，会增加系统编码的复杂度。u等长编码之所以编码效率难以提高，是因为等长码没有

32、充分等长编码之所以编码效率难以提高，是因为等长码没有充分利用信源及扩展信源的统计特性进行编码，而是无论概率大利用信源及扩展信源的统计特性进行编码，而是无论概率大小，给每个信源符号分配等长码字，从而无法降低平均码长。小，给每个信源符号分配等长码字，从而无法降低平均码长。变长码的基本思想是变长码的基本思想是：对于给定的信源，当信源符号对应：对于给定的信源，当信源符号对应的先验概率不是等概率分布时，为了提高编码效率，给概的先验概率不是等概率分布时，为了提高编码效率，给概率大的符号分配较短码字，概率小的符号分配长码字，从率大的符号分配较短码字，概率小的符号分配长码字，从而使得平均码长尽可能短。而使得平

33、均码长尽可能短。往往在序列长度不是很大时，变长码即可实现很高效率往往在序列长度不是很大时，变长码即可实现很高效率的无失真信源编码。的无失真信源编码。麦克米伦不等式与格拉夫特不等式具有相同的形式，该不麦克米伦不等式与格拉夫特不等式具有相同的形式，该不等式首先由格拉夫特在研究即使码存在的条件时提出，后等式首先由格拉夫特在研究即使码存在的条件时提出，后来麦克米伦证明唯一可解码的条件也满足该不等式。来麦克米伦证明唯一可解码的条件也满足该不等式。当信源给定时，使用相同的码符号对信源进行变长编码，当信源给定时，使用相同的码符号对信源进行变长编码，得到的即时码或者唯一可解码也可以有许多种。得到的即时码或者唯

34、一可解码也可以有许多种。现在的问题是那种码最好？现在的问题是那种码最好？从提高有效性角度考虑，应当选择码长作为衡量编码方法从提高有效性角度考虑，应当选择码长作为衡量编码方法好坏的准则。好坏的准则。定理定理4.6 设信源符号数为设信源符号数为r，对信源进行无失真编码，码符号，对信源进行无失真编码，码符号的个数为的个数为d，码字的长度分别为，码字的长度分别为12,.,rlll则唯一可译码存在的充分必要条件是则唯一可译码存在的充分必要条件是11irlid该不等式就是麦克米伦不等式该不等式就是麦克米伦不等式(Mcmilan Inequality)定义定义4.4 设信源的概率空间为设信源的概率空间为12

35、12()()()()rraaaXp ap ap ap x码符号个数为码符号个数为d，编码产生的码字对应的长度分别为，编码产生的码字对应的长度分别为12,.,rl ll则平均长度为则平均长度为1()riiiLp al含义：信源符号编码所需要的平均码符号个数含义：信源符号编码所需要的平均码符号个数定义定义4.5 给定信源给定信源X的熵为的熵为H(X),编码得到的每个信源符号编码得到的每个信源符号平均长度为平均长度为 ,那么定义平均每个码元携带的信息量为编那么定义平均每个码元携带的信息量为编码后信道的信息传输率码后信道的信息传输率L()HXRL物理含义：物理含义：平均每个码元平均每个码元所载荷信息量

36、所载荷信息量v定理定理4.7 设离散无记忆信源的熵为设离散无记忆信源的熵为H(X)，编码使用，编码使用的符号个数为的符号个数为d，一定存在一种无失真编码方法，一定存在一种无失真编码方法，构成唯一可译码，使得平均码长满足构成唯一可译码，使得平均码长满足()()1loglogH XH XLdd v首先证明下界，根据熵和平均码长的定义首先证明下界，根据熵和平均码长的定义11()log()log()log()rriiiiiiH XLdp ap adp a l 11()log()()logirrliiiiip ap ap ad 1()log()ilriiidp ap a ()()E f xf E x根据

37、詹森不等式香农第一定香农第一定理的基本形理的基本形式式先求数学期望，先求数学期望，后求函数后求函数先求函数，后先求函数，后求数学期望求数学期望v唯一可译码存在的条件就是满足即克拉夫特不等式，即唯一可译码存在的条件就是满足即克拉夫特不等式，即令()ilidxp a，可得1()log()log()ilriiidH XLdp ap a11log()log()iilrrliiiidp adp a11irlid1()logloglog1 0irliH XLdd()logH XLdv下面证明上界 v对于给定的概率分布p(ai)，一定存在一个正整数mi，使得下列不等式成立(1)()iimmidp adv选择

38、该信源符号对应码字的长度 limi。(1)loglog()logiiildp aldlog()1logiip ald v两边同乘以p(ai)，并且对求i和得11()log()()1logriiriiiip ap ap a ld()1logH XLd 根据熵、平均码长的定义 消息符号自消息符号自信洗量上取信洗量上取整整v该定理的意义：u无失真不等长编码的平均码长不能小于极限Hd(X)，否则唯一可解码不存在；u同时给出上界1+Hd(X)，说明小于上界的唯一可解码是存在的；u最佳码的平均码长应当满足上述不等式;u当然，平均码长超出上界的唯一可解码是存在的。定理定理4.8（香农第一定理）（香农第一定理

39、）设离散无记忆信源的概率空间为1212()()()()rraaaXp ap ap ap x信源的熵为H(X)，其N次扩展信源为 v扩展信源的熵为 H(XN)。使用d元码对次N扩展信源进行编码，可以找到一种编码方法，构成唯一可译码，使得信源编码得到的每个信源符号的平均码长满足 1212()()()()NNNrNrXpppp x()1()loglogNH XLH XdNNdv证明证明：由于信源X为无记忆信源，其次扩展信源XN也是无记忆的，而且有()lim()logNdNLH XH XNd()()NH XNH Xv直接应用定理4.7的结论()()1loglogNNNH XH XLdd v将扩展信源的

40、熵代入上式得()()1loglogNNH XNH XLdd()1()loglogNH XLH XdNNdv可以将该结论加以推广，对于平稳、遍历的有记忆信源 limlogNNHLNd香农第一定理的意义：香农第一定理的意义：使用使用d元码对信源进行无失真编码，信源编码每个符号平均元码对信源进行无失真编码，信源编码每个符号平均码长的极限就是信源的熵；码长的极限就是信源的熵；如果编码产生的平均码长大于信源的熵，唯一可解码是存如果编码产生的平均码长大于信源的熵，唯一可解码是存在的在的;反之，唯一可解码是不存在的，即在译码时一定会引入失反之，唯一可解码是不存在的，即在译码时一定会引入失真或者差错。真或者差

41、错。如果要取得好的编码效果，序列的长度应当更长，从而增如果要取得好的编码效果，序列的长度应当更长，从而增加系统编码复杂度。加系统编码复杂度。当然实际编码时，往往是通过变换方法进行编码，降低编当然实际编码时，往往是通过变换方法进行编码，降低编码系统复杂度。码系统复杂度。定义定义4.7 设信源设信源X进行变长编码得到的平均码长为进行变长编码得到的平均码长为L定义编码效率为定义编码效率为()dHXL衡量各种编码方法的优劣指标之一衡量各种编码方法的优劣指标之一定义定义4.8 定义变长码的码剩余度为定义变长码的码剩余度为()11dHXL例例4.5 设离散无记忆信源的概率空间为设离散无记忆信源的概率空间为

42、12()0.75 0.25Xaap x()0.75 0.75 0.25 0.250.811H Xlblb（1）如果采用二元码对其进行等长编码，映射关系为）如果采用二元码对其进行等长编码，映射关系为120,1aa编码效率为编码效率为()0.811H XL该编码方案可以使用信道形式表示，对应条件转移概率该编码方案可以使用信道形式表示，对应条件转移概率矩阵为矩阵为1001P其中信道的输入为其中信道的输入为12,aa，输出则为，输出则为0,1。显然这是一个无噪无损信道显然这是一个无噪无损信道（2）现在对信源进行二次扩展，并且采用下列编码方法进行）现在对信源进行二次扩展，并且采用下列编码方法进行变长编码

43、变长编码1 11 22 12 2010110111aaaaaaaa扩展信源的概率分布为扩展信源的概率分布为1 1()9/16paa 1 2()3/16p aa 2 1()3/16p a a 22()1/16p a a，序列的平均码长序列的平均码长21 9/16 2 3/16 3 3/16 3 1/16 1.6875L 比特比特/序列序列每个符号平均码长为每个符号平均码长为2/20.84375LL比特比特/符号符号编码效率为编码效率为()0.961HXL编码方案对应条件转移概率矩阵为编码方案对应条件转移概率矩阵为1000010000100001P（3）如果采用序列等长编码，要求编码效率为）如果采

44、用序列等长编码，要求编码效率为=96%，而允许译码错误概率为而允许译码错误概率为 ，510根据信源统计特性，可以计算自信息方差根据信源统计特性，可以计算自信息方差222()0.75 0.750.25 0.250.8110.4715iD I alblb编码序列的长度应当满足编码序列的长度应当满足要取得相当的编码效率，在允许译码错误概率并不是要取得相当的编码效率，在允许译码错误概率并不是很小的情况下，定长编码所需要的序列长度很长，这很小的情况下，定长编码所需要的序列长度很长，这就意味着需要产生巨大的码表；就意味着需要产生巨大的码表；而采用变长编码，只采用二次扩展信源就可以得到相而采用变长编码，只采

45、用二次扩展信源就可以得到相同的编码效率，随着序列的长度增加，变长编码的效同的编码效率，随着序列的长度增加，变长编码的效率越接近率越接近1 1。22722225()0.4175 0.964.13 10()(1)0.8110.0410iDI aNH X v而等长编码是将符号序列分为两大类：典型序列和而等长编码是将符号序列分为两大类：典型序列和非典型序列。非典型序列。v典型序列分配相同长度的码字，而非典型序列被丢典型序列分配相同长度的码字，而非典型序列被丢弃或者通过附加前缀的方法与典型序列的码字区分弃或者通过附加前缀的方法与典型序列的码字区分开。开。v而典型序列的概率分布并不完全相同，分配相同的而典

46、型序列的概率分布并不完全相同，分配相同的码字显然没有利用统计特性，所以等长码不仅编码码字显然没有利用统计特性，所以等长码不仅编码效率难以提高，而且可能出现译码错误。效率难以提高，而且可能出现译码错误。v在香农的等长编码理论中，非典型序列是不编码的，在香农的等长编码理论中，非典型序列是不编码的，一旦非典型序列出现，不可能再现或者重建该序列，一旦非典型序列出现，不可能再现或者重建该序列，所以会存在译码错误。所以会存在译码错误。4.4 信息率失真函数及性质信息率失真函数及性质 无论是等长编码还是变长编码，都可以通过增加序列的长度提高编码效率。信源无失真编码平均码长是受信源熵的限制，无论采用何种编码方

47、案，平均码长不可能小于信源的熵。由于编码产生的信息率受到熵的限制，当其大于信道容量时，不能够在信道中有效传输信息。而在实际中，为了传输信息，允许出现一定的失真，从而降低信息传输率。那么在允许一定失真条件下，信源编码输出的信息率是否存在极限；或者说，当信息率一定时，是否会存在最小失真，使得在有效传输信源的信息同时，尽可能减小编码引入的失真。这就是将要讨论的问题。4.4.1失真测度失真测度 v从直观上来看，如果允许失真越大，信息传输率应当越小；反过来，如果允许失真越小，信息传输率越大，所以信息传输速率与信源编码引入的失真是相关的，在允许失真一定的情况下，应当存在一种信源编码方法使得信息传输率最小。

48、失真实际是距离的一种，其定义应当满足一定的条件，对失真实际是距离的一种，其定义应当满足一定的条件，对于任意于任意i，j满足满足1）非负性，即非负性，即(,)0ijd a b，当且仅当，当且仅当ijab等号成立等号成立2）可交换性可交换性(,)(,)ijjid a bd b a3）三角不等式三角不等式(,)(,)(,)ijjid a bd b cd c av失真的测度 111212122212(,)(,)(,)(,)(,)(,)(,)(,)(,)ssrrrsd a bd a bd a bd a bd a bd a bd a bd a bd a bD常用的失真函数有平方误差失真平方误差失真 2(,

49、)()ijijd a bab221212221222120()()()0()()()0rrrrababababababDr=s且ai=biv绝对失真：绝对失真：(,)|ijijd a bab121212120|0|0rrrrababababababD汉明失真：汉明失真：1(,)0ijijijabd a babr=s且ai=bi011101110Dr=s且ai=bi例例4.6 对于离散对称信源，信源发送符号变量为对于离散对称信源，信源发送符号变量为12,rXa aa再现符号变量为再现符号变量为12,rYb bb，定义单个符号失真为，定义单个符号失真为0(,)1ijijijabd a bab它表示

50、：当再现符号与信源发送符号相同时，就不存在它表示：当再现符号与信源发送符号相同时，就不存在失真和错误，所以失真度失真和错误，所以失真度 ，当再现符号与信，当再现符号与信源发送符号不同时，就有失真存在源发送符号不同时，就有失真存在(,)0ijd a b 011110111110 rrD例例4.7 对于删除信源，假设信源发送变量对于删除信源，假设信源发送变量12,rXa aa而再现符号变量为而再现符号变量为12,sYb bb，且，且s=r+1定义它的单个符号失真度为定义它的单个符号失真度为0(,)11/2ijijd a bijjs10121102 Dv无论是单个符号的失真还是序列的失真，实际都是反