第7讲-离散无记忆信源等长编码

离散无记忆信源

等长编码第七讲信源编码基本概念字母表信源输出序列消息集码字集集合码字序列等长码不等长码D元码唯一可译码信源符号

信源符号出现概率

码表码0码1码2码3码4a1p(a1)=1/2000011a2p(a2)=1/40111101001a3p(a3)=1/8100000100001a4p(a4)=1/811110110000001信源编码基本概念信源编码器码表信源信道XYL长序列N长码字无失真等长编码英文电报27个符号,K=27,L=1,D=2(二元编码)每个英文电报符号至少要用5位二元符号编码

实际英文电报符号信源，在考虑了符号出现的概率以及符号之间的依赖性后，平均每个英文电报符号所提供的信息量约等于1.4比特，即编码后5个二元符号只携带约1.4比特的信息量，远小于5比特(最大熵)，可见编码后的信息传输效率极低。实例信源编码器码表信源信道XYL长序列N长码字无失真等长编码几乎无失真编码几乎无失真等长编码选择L足够长，使其中，为与L有关的正数，且当时有,才能不损失信息。然而这样的编码不总能保证单义可译，但非单义可译所引起的错误可渐近为任意小。反之，若，编码误差变得任意大。令信源的熵为，的方差为，则的均值为方差为由契比雪夫大数定理，对于可选，这可以通过适当选择L来实现，上式可以写成即当L足够大时，将以概率1取值为H(U)。典型序列令H(U)是集的熵，定义为给定信源U输出长为L的典型序列集，又可称作弱ε典型序列集；的补集为非典型序列集。令H(U)是集的熵，定义为给定信源U输出长为L的典型序列集，其中，是L序列中出现的次数，又称之为强典型序列集。相应信源划分定理定理：给定信源和，当时，由契比雪夫大数定理，对于可选，这可以通过适当选择L来实现，上式可以写成即当L足够大时，将以概率1取值为H(U)。信源划分定理定理：给定信源和，当时，对于任意小，存在有正整数，使得当时，有由契比雪夫大数定理，对于可选，这可以通过适当选择L来实现，上式可以写成即当L足够大时，将以概率1取值为H(U)。，则证明：从典型序列定义式有即等式两边各项取指数，即得证。若推论1(特定序列出现的概率)即推论2(典型序列数目)当L足够大时，对于给定的信源的个数满足证明：即由有即和,典型序列即理解典型序列一个离散无记忆信源输出的消息序列可以分为两组，各序列出现的概率近于相等；每个序列平均符号的信息量接近于信源熵H(U)；所有典型序列的概率和趋近于1。

个别非典型序列的概率不一定比个别典型序列的概率低。

虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。理解典型序列

个别非典型序列的概率不一定比个别典型序列的概率低。

虽然非典型序列集中序列的总概率很小，但是元素数目不一定小。掷硬币试验：正面出现概率p，反面出现概率1-p典型序列非典型序列（全反）离散无记忆信源编码模型无错有错错误概率编码速率可达对于给定的信源和编码速率R以及任意若存在有使当码长时就称R是可达的，否则称此R不可达。无扰编码定理若R>H(U)，则R是可达的；若R<H(U)，则R是不可达的。对于给定的离散无记忆信源，若D元码的速率R超过信源的熵，即，则存在有编码方法，当L足够大时就能使译码错误概率任意小。编码效率证明充分性令，取。由信源划分定理推论2，对于通过选择足够大的L，可使对于每个依次标以码号1,2,…,2LR-1,并令作为相应消息的码字；而对于，都用第2LR个标号(000···000)表示。编码：相应号数的二元序列译码：若若因此，R为可达速率。则则证明必要性令，则正确译码概率为因为，所以有个码字，序列的个数至少为，所以在序列可以找到码字的概率为而由此得随着L的加大，上式趋于0，即从而R是不可达的。而典型中的本节小结

信源编码基本概念DMS等长编码无失真编码充要条件几乎无失真编码充要条件（本节内容见课本53-62页）定义等长码不等长码唯一可译码

D元码典型序列例题掷硬币：正面出现p=0.25，这时信源熵H(U)=0.81。（1）若采用等长二元无错编码时，（2）若采用只对典型序列编码，要求译码错误概率，求L由可得