信息论与编码第四章

1、 高传输率与抗干扰是一对矛盾 ，但可以从理论上证明，至少存在某种最佳的编码或信息处理方法，能解决这一矛盾。 4.1 编码器变换 （数学规则）：将信源符号用由码元组成的序列（长度为li）来表示若通过一个二进制信道进行传输，为使信源适合信道的传输，将用0,1符号序列表示，码符号集为 ，序列与si的对应形式可有多种，得不同的码。第四章第四章 无失真信源编码无失真信源编码 coder12,qssss1:rxxx12:,qcwww 1 , 0 x 码的基本分类：码的基本分类： 固定长度码（等长码） 变长码：各码字的码长不等 非奇异码：码中所有码字都不相同 奇异码：有同码 码的码的n n次扩展：次扩展：

2、码2的二次扩展码为： 同价码：每个码符号（元）所占的传输时间都相同1110010102111001001码码,;,;44163132121112ssassassassas1111110010100100111101001010101001110001001001610987654321aaaaaaaaaaa4.2 等长码和等长信源编码定理 jw实现无失真编码的条件：实现无失真编码的条件： 1、信源符号与码字一一对应 2、任意一串有限长的码符号序列与信源s的符号序列也是一一对应，即n次扩展后仍满足一一对应关系。同时满足上述条件称为唯一可译码唯一可译码 有重码，非唯一可译码 等长非奇异码一定单义可

3、译 0100100:4321csssss0001000000100001001100010101000000001000433323134232221241312111ssssssssssssssssssssssss01010100011001044342414ssssssss等长编码条件等长编码条件： ，满足此条件，才有可能无重码（非奇异）；扩展后： lrq lnrqrlqnloglogrqnlloglog1nrqllog/lognl ：平均每个信源符号所需要的码符号（元）个数 考虑到符号出现的概率以及符号之间的依赖性 。再去除一些无效字符组合，扩展信源中的符号总数 所需编码的码字个数可大大

4、下降。设离散无记忆信源： nq)(),(,:)(:11qnqqnapapaaapsqiiiqisssanniniii, 1, 1),(2121，nkikipap1)(nqi, 2 , 1nknkikikiisipapai11)(log)(log)()()()(snhshaienih(s)mxxpe(x)x）（)()()()(22shsiensindaidiiiqiqiiiiippppn1212log)(log22222m2m-x2p(x)p(x)mxp(x)2m-p(x)xp(x)m-x）（由切贝雪夫不等式： 方差为定值 表明 依概率收敛于 上界 下界 2)()()()(naidnsnhaip

5、ii),(/)()()(2nnsidshnaipii0)(lim),(lim2nsidninn( )/ii an)(sh)()(:shnaiagii)()(:shnaiagii),()(0ngp1)(),(1gpn)()()()()(shnaishnshnaiii)()(2)(2shnishnapmin( )( )1igigmp ap g)(2)(minshnigapi)(2shngmi1(, )( )max p(a )gnp gm)(2)(maxshniap)(2),(1 shngnm我们可以只对集g中mg个信源序列进行一一对应的等长编码，这就要求码字总数不小于mg就行，即 满足式的条件下，

6、 时，译码错误概率 但当 由mg的下界式可知，这种情况下选取的码字总数小于集g中可能有的信源序列数，将有相应码字对应的信源序列的概率和记作 ，它必然满足： 造成有些序列没有码字对应，译码时必出错，其中正确的译码概率： glmr lshngrm )(2rshnlshnrllog)()(log2)(,()(nsidngppie2)(2log2)(shnlrrshnln0epilargp个中)(maxigalilaprargpi个中nshnshnilargp222)(2)(个中glmr pppee112lniegrap 中 个nep21n1ep等长信源编码定理等长信源编码定理 一个熵为h（s）的离散

7、无记忆信源，若对信源长为n的符号序列进行等长编码，设码字是从r个字母的码符号集中选取 l 个字母组成，对于任意 ，只要满足 ，当 时，几乎可实现无失真编码，即译码错误概率能为任意小。 反之，若 ，则不可能实现无失真编码， 时， 。 可改写： 只要码字载荷的信息量大于信源序列携带的信息量，总可实现几乎无失真编码，而且传输效率接近于1 0rshnllog)(nrshnllog2)(n1ep)(logsnhrl例： 0 1 扩展n2 00 01 10 11 0.9 0.1 0.81 0.09 0.09 0.01如取00，01，10编码，概率和为：0.99扩展n3 000 001 010 100 10

8、1 110 111 0.729 0.081 0.081 0.081 0.009 0.009 0.001取两位0的编码，概率为0.972；取前7个编码，概率为：0.999扩展n4 0000 0001 0010 0011 0100 0101 0110 0111 0.6561 0.0729 0.0729 0.0081 0.0729 0.0081 0.0081 0.0009 1000 1001 1010 1011 1100 1101 1110 11110.0729 0.0081 0.0081 0.0009 0.0081 0.0009 0.0009 0.0001取3个0的编码 (05个)，概率为0.94

9、77；取2个0的编码 (11个)，概率为0.9963；取1个0的编码 (15个)，概率为0.99994.3 变 长 码 变长码可以在n不很大时就可编出效率很高而且无失真的码；变长码也必须是唯一可译码才能实现无失真编码。例：码1 码2 设： 是码c中的任一码字，而其它码字 都不是码字wi的前缀，则此码为即时码，亦称非延长码。 即时码是唯一可译码的一类子码即时码是唯一可译码的一类子码 。 10001001014321ssss00010010114321ssss)(1imiixxw)(1kjkkxxwmj 树图法构造即时码：根、枝、节点 码树图也可以用来译码单义（唯一）可译定理单义（唯一）可译定理：

10、设信源符号集为： ，码符号集为： ，又设码字为 ，其分别对应的码长为； ， 则存在唯一可译码的充分必要条件是： 码长 li ，码符号集中符号个数r，信源符号个数q，称作kraft不等式。 说明说明：唯一可译码一定满足不等式，反之，满足不等式的码不一定是唯一可译码。21qssss21rxxxxqwww21qlll2111qilir 充分性证明：充分性证明：假定满足不等式的码长为 ，在q个码字中可能有长度相同的码字。设码长为1的有n1个，长度为2的有n2个，长度为j的有nj个，最大长度为l 的有nl个，此处n为节点的阶数，（即n次扩展），此节点中的码字长度为ni；ni为长度为i的码字个数。有： 一

11、共q个码字，全为1时， ，满足不等式 ： 考虑有码长相等的情况，合并同类项后得： 两边同乘以 ： 移项后为： 由于都为正整数，将左边去掉一项（等号去掉），有：qlll,21liiqn1ql 1121qilllllqjirrrrrliiillrnrnrnrn1221111lrrnrnrnrnlllll12211lllllrnrnrnrn12211lililirrn1rnrnrnrnlllll12211 同理得： 由 与最大长度l 之间的关系，上述不等式系列给我们带来了结构上的构码条件。显然可证明：如满足kraft不等式，则一定能构成至少一种结构为 的即时码，如最长码数 取不等式中的等号，则为用尽

12、即时码，如取不等号，则为非用尽的即时码，即时码是唯一可译码的一类子码，所以定理的充分性也就得到了证明。 111liiirnrnrnrnrnrnrnrnrnrnrnrnrnrnrnllllllllll11222213334231222322111rnlqrii,inrq,ln必要性证明：已知唯一可译码的码长为 ，设n是一个任意的正整数，考虑等式： 右边共有 项，代表了n个码字组成的码字序列的总数。每项均对应于n个码字组成的一个码字序列，如下图，图中1、2、n表明码字的序号， 分别为对应的码长。令： j的值是个码字组成的码字序列的总长，也就是n个信源符号组成的序列所对应的码符号序列的总长度。因为讨

13、论的是变长码，所以设 的取值范围为： qlll,21 qiqiqilllnlllnqilniniiqirrrrr111)(1122121 qqninilllllqilqilrrrrrrr1211111121n n1il2il1inlinln共 个码字nqln21,llliijlllinii21qiin, 2 , 11il 则j的取值范围为式为各 项之和， 都可取 而 又都可取值为 ，所以相同数值j的出现不止一次，也就是在 个码字序列中码符号总长相等的码字序列不止一个，令为 个， 换句话说，就是把总长度为j的序列的数目记为 ，例如由唯一可译码 三个码字所组合成的长度 的序列共有7种：1 01 0

14、01，1 001 01，01 1 001，01 001 1，001 1 01，001 01 1，01 01 01a1 a2 a3 ，a1 a3 a2， a2 a1 a3， a2 a3 a1 ， a3 a1 a2， a3 a2 a1，a2 a2 a2 因此：式（19）可以合并：将 代入上式： 对于所有正整数n，上式都要成立，当 时 所以必须有： 证毕maxminlllimaxminnljnlmin1lmaxnljnjrinill,1,21qlll,1qllmaxmin, 2 , 1llnqjaja001,01, 1:w6jmax1nlnjjjnqilrarijjra maxmax1max1max

15、1nlnjjnlnjjnqilnlnnlrrrinqilnlri11max)(n1max)(lim1nnnl11qilir4.4 变长信源编码定理平均码长：平均码长：一个信源符号所需的平均码符号数为： 可见： 越短， 越大，信息传输效率就越高，因此，我们总希望编出来的码平均码长 最短， 可作为衡量唯一可译码的有效性高低的一个标准。 qiiilspl1)(lshbitlshr)(/)(信符码符信符/bit 码符号ltshrt)(sbit /ltrll81814121: )(:4321sssssps3, 3, 2, 14321nnnn1882222332141ilir3,111,110, 2,10

16、, 1, 043432211llwwlwlw81438122411211l1, 0, 2,10, 3,110,11144332121nwnwnnww8213213412811812l 定理定理4.34.3，若一个离散无记忆信源具有熵为 ，并有r个码符号的符号集，则总可找到一种无失真编码方法，构成唯一可译码，使其平均码长满足：下界证明：由证明过程知，上述等式成立的充要条件是： 可见，只有当选择每个码长： 时，才能达到这个下界值,式中 必须为正整数，每个 必须呈现 的形式（ 是正整数）。)(shrshlrshlog)(1log)(0log)(log/ )(rlshrshlqiqiiiiilsprs

17、psprlsh11)(log)(log)(log)(qiqiilqiiliiisprsprspspspii111)(log)(log)()(log)(01loglog)()(log11qilqiiliiirsprsp1)(ilspriilirsp)(log( )log( )logiiip slrp sr )(1logiisprl il)(ispiar1ia 上界证明：只需证明 在上界与下界中间可以找到一种唯一可译码就行。在如下区间取之整数 证毕 信源给定，h（s）确定，那么，该信源的唯一可译码的平均码长 的下界值也就随之确定，信源编码的有效性的限度也就确定了，在不改变编码的对象，即信源本身的统

18、计特性的情况下，单靠改变编码方法来继续提高有效性是无潜力可挖了。 l1)(log)(logiriirsplspil1iq)()(1ilisprrspi( )( )iliip srp srqiiqilqiisprrspri1111)()(1qiiirqiiqiiispspsplsp111)()(log)()(1log)(rshll定理定理4.44.4 离散无记忆信源s的n次扩展信源 ，熵为 ，并有码符号集 。对信源 进行编码，总可以找到一种编码方法，构成唯一可译码，使信源中每个信源s中每隔信源符号所需的码字平均长度满足： 或者 且 式中： 令n1就是定理4.3 证明：证明：用sn替代定理4.3中

19、的s，得： ，其中 是以r进制为单位的扩展信源sn的熵。代入上式结论可推广到平稳遍历的有记忆信源（如马尔可夫信源） ,21qnnaaas)(nsh,1rxxxnsrshnlnrshnlog)(1log)()(1)(shnlnshrnr)(limshnlrnnnqiiinapl1)(1)()(nrnnrshlsh)(nrsh)()(snhshrnrnshnlshsnhlsnhrnrrnr1)()(1)()(n)(limshnlrnn 以上分析表明，要进一步提高编码的有效性，必须考虑到信源符号间的依赖性，以减少信源每发一个符号所携带的平均信息量，缩短平均码长的长度。考虑的依赖性越仔细，即记忆长度越

20、长，平均码长就可能越短，编码就越有效。 如前所述，我们还可以用扩展信源的手段，达到数据压缩的目的，扩展的程度越高，压缩的效果越好。但增加了编码的复杂性（代价）。变长无失真信源编码定理（香农第一定理）也可这样来描述：设信源s的熵为h（s），无噪离散信道容量为c，于是，信源的输出可以进行这样的编码，使得在信道上传输的平均速率为每秒 个信源符号，其中 可以是任意小的正数，要使传输的平均速率大于 是不可能的。编码效率： 码的剩余度： )(shc)(shc1)(lshrlshr)(114.5 变长码的编码方法香农编码香农编码 ： ，可使不超过上界，但不一定保证是紧效码 哈夫曼编码哈夫曼编码：1、将信源消

21、息（符号）按概率大小顺序排队。2、从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支络编为1（或0），大概率的上支络编为0（或1），两相等，也按上、下支络给值。3、将已编码的两个消息对应概率合并，并重新按概率大小排队，重复24、重复3，直至剩两个符号为止。5、编成的变长码按后出先编的方法，从树根沿编码路线逆行至对应的消息（从最后级向前返回），得出各信源符号所对应的码符号序列。 1iiialahuffman码一定是紧效码 证明证明：由h氏编码方法最后一步得到的缩减信源sa必定只有r个符号.这r个符号的概率和必为1，且这r个符号分别只授于一个码符号(1,2,3r)，所以缩减信源sa

22、对应的单义可译码ca的平均码长 一定等于1，平均码长等于1的单义可译码当然是最佳码。设某一缩减信源sj，已找到一个最佳码cj，其平均码长为 ，由编码方法，对于sj中某一元素sa（由前一个缩减信源中 概率最小的r个符号 合并而来的，且 ，对于 信源的码 ，其平均码长为 。由于在 中除了 这r个符号相应的r个码字比缩减信源sj中的符号sa相应的码字多一个r进制码符号外，其余码字长度都是相同的。所以 满足以下关系：aljl1jsaraasss21,riiaspsp)()(1js1jcjjll11jcaraasss21,jjll与1riaijaraajjsplspspspll1211)()(1)(1)(1用反证法来证明：假设找到另一个码 的最佳码，即其平均码长 ，设 的码字为 ，各码字的长度分别为 ，再假设这些码字的排列次序是按照码字概率递减的次序，得 （可以通过改变码字的标号来达到这一要求）。而在这些码中 除了最后一个码符号不同外，其它码符号全部相同，也就是说有本层的码字长度相等 如我们在