第五章无失真信源编码定理

第五章无失真信源编码定理5.1编码器5.2等长码5.3*渐进等分割性和典型序列5.5变长码5.4等长信源编码定理5.6变长信源编码定理1、信源编码的目的

——在不失真或允许一定失真条件下，如何用尽可能少的符号来传送信源信息，以便提高信息传输率。2、信道编码的目的

——在信道受干扰的情况下，如何增加信号的抗干扰能力，同时又使得信息传输率最大。5.1编码器5.1.1编码器的构成5.1.2有关常用码的概念5.1.1编码器的构成编码器S:信源符号码符号，或码元编码实质上是对信源的原始符号按一定的数学规则进行的一种变换。码字长度或码长C码字(信源符号)(信源序列)码字由码元组成码C由码字组成编码就是从信源符号到码字的一种映射，一一对应，可逆，则可实现无失真编码。5.1.2有关常用码的概念1、二元码码符号集为，所得码字是二元序列。2、等长码一组码中所有码字的码长都相同。3、变长码一组码中所有码字的码长各不相同。4、非奇异码C一组码中所有码字都不相同。即5、奇异码C一组码中有相同的码字。即6、同价码码符号集中每个码符号所占的传输时间都相同。一般二元码是同价码。对于同价码，等长码中每个码字的传输时间都相同，变长码每个码字的传输时间就不一定相同。7、码的N次扩展码N次扩展信源对应的N个码字组成的码字序列的集合。N次扩展码

B举例信源符号的码和二次扩展码的形式信源符号si符号概率P(si)码1码2s1P(s1)000s2P(s2)0101s3P(s3)10001s4P(s4)11111表5.1等长码变长码非奇异码表5.2码2的二次扩展码信源符号扩展码字信源符号扩展码字信源S的二次扩展信源信源S的二次扩展码8、唯一可译码码的任意一串有限长的码符号序列只能被唯一地译成所对应的信源符号序列，则此码称唯一可译码或单译可译码。(1)信源符号对应的码是非奇异码。(2)任意有限长的N次扩展码是非奇异的。例：码符号序列“0010”“0010”5.2等长码5.2.1等长码的唯一可译性5.2.2等长码的编码长度5.2.1等长码的唯一可译性若等长码是非奇异码，则它的任意有限长N次扩展码一定也是非奇异码，因此一定是唯一可译码。信源符号si符号概率P(si)码1码2s1P(s1)0000s2P(s2)0111s3P(s3)1010s4P(s4)1111表5.3唯一可译码非唯一可译码5.2.2等长码的编码长度1、q个信源符号：码元数为r：则码长必须满足下式例:(1)(2)（表4.2）必要条件

个信源符号：可得到等长非奇异码取对数：当N=1时是平均每个信源符号所需要的码符号个数2、对N次扩展信源编码3、等长码的码长仍可压缩考虑符号出现的概率和符号间的依赖关系，码长可压缩。例：其余且二次扩展信源

有个符号,

压缩至4个符号,编码即可.结论:考虑信源符号间的依赖关系后,

再考虑符号出现的概率时,所需平均码长可能缩短.5.3*渐进等分割性和典型序列对于离散无记忆信源

N次扩展信源当为有限值时,弱大数定律对于独立、等同分布的随机变量，只要n

足够大时，接近其数学期望E[X]。定理5.1

渐进等分割性(AEP):

若随机序列中相互统计独立并且服从同一概率分布,又，则依概率收敛于。

可表示成,对于任意弱大数定律:此渐近等分割性说明,离散无记忆信源的N次扩展信源中,信源序列的自信息的均值，依概率收敛于信源熵。当N为有限长时,在所有个长为N的信源序列中必有一些,其自信息量的均值与信源熵之差小于,即:或称N长序列为典型序列.中所有典型序列的集合表示为非典型序列集(2)若，则(3)设表示典型序列集中包含的典型序列的个数，定理5.2:对于任意小的正数当N足够大时，则(1)而显然证明:(1)可由定理5.1直接推得当时，契比雪夫不等式当依概率收敛于(2)可由变形证得。推论：当N足够大时，可任意小，表明典型序列出现的概率近似相等，所以称为渐进等概率序列。(3)由上述性质(2)证得。性质(1)表明，典型序列是经常出现的信源序列。时，成为必然事件。性质(2)表明接近等概分布性质(3)表明当时,

典型序列的总数占信源序列的比值为：一般所以，当

是高概率集，它含有序列数常常比非典型序列数要少很多。所有信源序列非典型序列集

典型序列集结论：只对少数的高概率典型序列进行一一对应的等长编码。码字总数减少，所需码长就可以减小了。AEP结论：当N足够大时

所有典型序列出现的概率近似相等.2.可粗略认为典型序列出现的概率为3.所有典型序列的概率和接近为1,5.4等长信源编码定理5.4.1等长信源编码定理5.4.2平稳有记忆信源的码长5.4.3对于编码好坏的评价5.4.1等长信源编码定理—

定理5.31、定理内容：一个离散无记忆信源，熵为，信源长为N，码符号r个，码字长，对于任意，只要满足则当N足够大时，可实现几乎无失真编码。译码错误概率为任意小。

若则不能实现无失真编码，而当N足够大时，译码错误概率近似等于1。

比较公式:

一般，当信源符号有依赖时，，所以得到压缩2、证明：(1)

整理

错误概率设(3)当二元编码时，定理5.3为等长编码时平均每个信源符号所需要的二元码符号的极限值是H(s)。(2)

选取的码字总数小于集中可能有的信源序列数，译码时定会产生错误。当N很长时，5.4.2平稳有记忆信源的码长对平稳有记忆信源：用替代定理5.3中的H(s)

无失真编码不能实现无失真编码5.4.3编码的评价定理5.3

式(1)表示长为的码符号载荷的最大信息量大于信源序列携带的信息量时,可实现几乎无失真编码.

式(2)令

称编码信息率,表示编码后平均每个信源符号能载荷的最大信息量.只有编码信息率大于信源的熵,才能实现几乎无失真编码.编码效率编码效率用来衡量编码效果等长编码的最佳效率得

表示编码前后平均每个信源符号能载荷的最大信息率之比。即在已知方差和信源熵的条件下,容许错误概率愈小,编码效率愈高,则信源序列长度N必须愈长.在实际情况下,要实现几乎无失真的等长编码,N要大到难以实现的程度.已知当允许错误概率小于时代入采用二元编码，要求编码效率，允许错误概率，求编码长度？解:例5.1

已知离散无记忆信源当N取4120万以上时，才能按要求实现几乎无失真编码。因此N有限的等长码往往引入一定的失真和错误。5.5变长码5.5.1唯一可译变长码与即时码5.5.2即时码的树图构造法5.5.3克拉夫特（kraft）不等式5.5.4唯一可译变长码的判别法1、唯一可译码5.5.1唯一可译变长码与即时码信源si概率P(si)码1码2码3码4s11/20011s21/411101001s31/80000100001s41/8110110000001表5.4奇异码非唯一可译码非即时码即时码（1）在唯一可译变长码中，译码时无需参考后续的码符号就能立即作出判断，译成对应的信源符号，这类码称为即时码

结构特点：

即时码：码字不是其它码的前缀或延长

非即时码：某些码字是其它码的前缀或延长。2、即时码（2）在译码过程中，当收到一个完整的码符号序列时，无需等待下一个符号到达后作判断，而能直接译成对应的信源符号。3、码的分类及关系奇异码非奇异码唯一可译码即时码所有码5.5.2即时码的树图构造法1、码树的构造过程（1）根：从根出发伸出树枝，树枝的数目等于码符号的总数r（2）节点：树枝的尽头为节点。从节点出发再伸出树枝，每次每个节点伸出r枝，依次下去构成一棵树。（3）终端节点：被安排为码字的节点,它不再继续伸枝，用粗黑点表示。（4）中间节点：没被安排为码字继续伸出枝的节点，用空心圆表示。（5）码字：由从根出发到终端节点走过的路径所对应的码符号组成。按树图法构成的码一定满足即时码的要求。（2）当码字长度给定，即时码不是唯一的（4）码树图可用来译码从根—中间节点—终端节点2、码字与树图的联系（1）当第阶的节点作为终端节点，相应码字的码长为。（3）当元节的码树的所有树枝都被用上时，第阶节点共有个终端节点—对应于长的等长编码—等长码也是即时码的一种。码3的码树

r=2,r=3

的三阶节点树图画出码4的树图码4的另一种树图小结：将变长码与码树建立“一一对应”关系：树根码字起点树枝数码的进制数节点码字或码字的一部分终止节点码字节数码长非满树变长码满树等长码

5.5.3克拉夫特（kraft）不等式1、定理5.4对于码符号为任意即时码(非延长码)，其码字为，所对应的码长为，则必定满足反之，若码长满足上面不等式，则一定存在具有这样码长的即时码。证明：充分性(1)r元树，第N阶的总枝数枝(2)第阶节点作为码字，使第N

阶减少的枝数(3)第阶的码长(4)个码字使第N阶减少的树枝数证得Kraft不等式的物理意义：给定信源符号数q和码符号数r，只要允许码字长度可以足够长，就总可以满足Kraft不等式，从而得到即时码。2、定理5.5

将定理5.4中的即时码改为唯一可译码，其余不变。推论:(1)当码长满足kraft不等式时，不一定是唯一可译码。(2)但一定存在至少一种码长相同的唯一可译码。不一定是即时码。(3)也一定能找到至少一种相同码长的即时码。5.5.4唯一可译变长码的判别法1、树图判别即时码2、尾随后缀法由A.A.Sardinas和G.W.Patterson1957年提出A1A2A3Am…B1B2B3Bn…5.5.4唯一可译变长码的判别法2、尾随后缀法步骤：(1)F1是C中所有码字尾随后缀的集合;(2)考察C和Fi两个集合,如果C中任一码字是Fi中元素的前缀,或者Fi中任一元素是C中码字的前缀,则将其相应的尾随后缀放入集合Fi+1;(3)(4)一旦F中出现了C中的元素,则算法终止,C不是唯一可译码;若出现Fi+1为空集或Fi+1中的元素在F中已经全部存在,算法终止,C是唯一可译码.5.5.4唯一可译变长码的判别法解:

例设消息集合共有7个元素,判断其编码的唯一可译性.siCF1F2F3F4F5s1as2cs3adds4abbbbs5badads6debebbs7bbcdecdedebcde非唯一可译码!5.6变长信源编码定理5.6.2离散无记忆信源的唯一可译码长的理论极限5.6.1平均码长5.6.3离散无记忆N次扩展信源编码的平均码长理论极限5.6.1平均码长对应码长为，而1、平均码长单位是：码符号/信源符号2、每个码元携带的信息量H(X)每个信源符号携带的信息量H(S)3、编码后信道的信息传输率显然，越短，越大，信息传输效率越高4、最佳码—或紧致码平均长度最小的唯一可译码。5.6.2离散无记忆信源的唯一可译码长的理论极限定理5.7

信源S熵为H(S),r个码元可以找到一种唯一可译码，使码长满足且的理论下限是，获得条件向上取整得香农码长！

定理5.7表达式定理5.7可表示成5.6.3离散无记忆N次扩展信源编码的平均码长理论极限定理5.8—香农第一定理

—无失真变长信源编码定理信源的熵为，r个码元，可构成唯一可译码，使信源S中每个信源符号所需的平均码长满足或

且式中

是对应的码字长度证明：定理指出，要做到无失真信源编码，编码每个信源符号所需要的码元数就是信源的熵(以r为底)。当扩展次数时，平均码长