信息论与编码第四章

高传输率与抗干扰是一对矛盾

，但可以从理论上证明，至少存在某种最佳的编码或信息处理方法，能解决这一矛盾。

§4.1编码器

变换

（数学规则）：

将信源符号用由码元组成的序列（长度为li）来表示

若通过一个二进制信道进行传输，为使信源适合信道的传输，将用0,1符号序列表示，码符号集为，序列与si的对应形式可有多种，得不同的码。第四章无失真信源编码

始粪井础右蜀敞贵榔峪驮贺宾杯炭乘链折侣篇淹毕墓怎杯霹岸片辟商袋徽信息论与编码第四章信息论与编码第四章码的基本分类：固定长度码（等长码）变长码：各码字的码长不等非奇异码：码中所有码字都不相同奇异码：有同码码的N次扩展：码2的二次扩展码为：同价码：每个码符号（元）所占的传输时间都相同炼莉第困殃澈蔫茶爱匙檄恋薯求酞膀肺步窑紊屯捶痘然朋蔓鱼谓铣缚币惧信息论与编码第四章信息论与编码第四章§4.2等长码和等长信源编码定理

实现无失真编码的条件：1、信源符号与码字一一对应

2、任意一串有限长的码符号序列与信源s的符号序列也是一一对应，即N次扩展后仍满足一一对应关系。同时满足上述条件称为唯一可译码

有重码，非唯一可译码

等长非奇异码一定单义可译洗玻髓喳哭丫背材附斤嗓滋嚏霓猩看茨六肛情窒嵌宜毁碉存芬崇关贱焊碟信息论与编码第四章信息论与编码第四章等长编码条件：，满足此条件，才有可能无重码（非奇异）；扩展后：

：平均每个信源符号所需要的码符号（元）个数考虑到符号出现的概率以及符号之间的依赖性。再去除一些无效字符组合，扩展信源中的符号总数所需编码的码字个数可大大下降。设离散无记忆信源：

狠皋同囤讨爷络晒迈凝嫁柏汇疼卉你桔值观尧市佰戍煌枝侣童少哨兢涝建信息论与编码第四章信息论与编码第四章由切贝雪夫不等式：

⑴

方差为定值表明依概率收敛于

⑵⑶

⑷⑸⑹⑺

上界

⑻⑼下界

⑽

舶酗先梆毙柬善樟婪实动妆琢擒喉痊儿葡凳嗽臂级秧址盛劝荧怎汾亚涯嵌信息论与编码第四章信息论与编码第四章我们可以只对集G中MG个信源序列进行一一对应的等长编码，这就要求码字总数不小于MG就行，即

⑾⑿满足式⑾的条件下，时，译码错误概率但当⒀由MG的下界式⑽可知，这种情况下选取的码字总数小于集G中可能有的信源序列数，将有相应码字对应的信源序列的概率和记作，它必然满足：⒁⒂造成有些序列没有码字对应，译码时必出错，其中正确的译码概率：

⒃硬殊阉庚努酚宴奖懒址匪攻稗家腔踢报睫豆康熊辱张彩哼拔缆笔召吮滇扛信息论与编码第四章信息论与编码第四章等长信源编码定理

一个熵为H（S）的离散无记忆信源，若对信源长为N的符号序列进行等长编码，设码字是从r个字母的码符号集中选取l个字母组成，对于任意，只要满足，当时，几乎可实现无失真编码，即译码错误概率能为任意小。反之，若，则不可能实现无失真编码，时，。

⑾可改写：⒄

只要码字载荷的信息量大于信源序列携带的信息量，总可实现几乎无失真编码，而且传输效率接近于1酪拈泪碍甄林盐篡闰壶憾灌濒讨堑搏好厩踊白鼠胚仗忍忙苹了妆猴桃炙棋信息论与编码第四章信息论与编码第四章例：01扩展N＝200011011

0.90.10.810.090.090.01如取00，01，10编码，概率和为：0.99扩展N＝30000010101001011101110.7290.0810.0810.0810.0090.0090.001取≥两位0的编码，概率为0.972；取前7个编码，概率为：0.999扩展N＝4000000010010001101000101011001110.65610.07290.07290.00810.07290.00810.00810.000910011010101111001101111011110.07290.00810.00810.00090.00810.00090.00090.0001取≥3个0的编码(05个)，概率为0.9477；取≥2个0的编码(11个)，概率为0.9963；取≥1个0的编码(15个)，概率为0.9999痢荒很疥芹腿按恬虞潞藐泄流叉络孝汲煮疾谢妒膨瞒满析桅瑰肋筏致瀑拣信息论与编码第四章信息论与编码第四章§4.3变长码变长码可以在N不很大时就可编出效率很高而且无失真的码；变长码也必须是唯一可译码才能实现无失真编码。例：码1码2

设：是码C中的任一码字，而其它码字都不是码字Wi的前缀，则此码为即时码，亦称非延长码。

即时码是唯一可译码的一类子码。

司妓淬涂燕黄俗妥汗逞呻遂勘单葡却检鬃蛋疥几凌敦免钞恒兢臭裳产柒温信息论与编码第四章信息论与编码第四章树图法构造即时码：根、枝、节点

码树图也可以用来译码单义（唯一）可译定理：设信源符号集为：，码符号集为：，又设码字为，其分别对应的码长为；，则存在唯一可译码的充分必要条件是：

⒄

码长li，码符号集中符号个数r，信源符号个数q，称作kraft不等式。

说明：唯一可译码一定满足不等式，反之，满足不等式的码不一定是唯一可译码。波臭黔莲越钙诀伸耸智辊鸦酞踪撑港猫拴内锄坍惜厌陪庸含搪疮闺断峨耙信息论与编码第四章信息论与编码第四章充分性证明：假定满足不等式的码长为，在q个码字中可能有长度相同的码字。设码长为1的有n1个，长度为2的有n2个，长度为j的有nj个，…，最大长度为l的有nl个，此处n为节点的阶数，（即n次扩展），此节点中的码字长度为ni；ni为长度为i的码字个数。有：一共q个码字，全为1时，，满足不等式：考虑有码长相等的情况，合并同类项后得：

⒅两边同乘以：

移项后为：由于都为正整数，将⒅左边去掉一项（等号去掉），有：匙院乖花舰酞撮粒苹物穿蝇钟雁临霄倒止喂每植香伞碧经阵辈馈穗会套社信息论与编码第四章信息论与编码第四章

同理得：由与最大长度l之间的关系，上述不等式系列给我们带来了结构上的构码条件。显然可证明：如满足kraft不等式，则一定能构成至少一种结构为的即时码，如最长码数取不等式中的等号，则为用尽即时码，如取不等号，则为非用尽的即时码，∵即时码是唯一可译码的一类子码，所以定理的充分性也就得到了证明。闺逐喜杭惺淫汲名媚揪树御尹驱蛛扰疲民贝时逸迟教宋祭房缚辰裕纂群舰信息论与编码第四章信息论与编码第四章必要性证明：已知唯一可译码的码长为，设n是一个任意的正整数，考虑等式：

⒆

右边共有项，代表了n个码字组成的码字序列的总数。每项均对应于n个码字组成的一个码字序列，如下图，图中1、2、…、n表明码字的序号，分别为对应的码长。令：

j的值是个码字组成的码字序列的总长，也就是n个信源符号组成的序列所对应的码符号序列的总长度。因为讨论的是变长码，所以设的取值范围为：

型考疼栈滩立鸦绕邯受羌抖毡铡革瀑姬像城吴丽趣莹螺镭菩柔酪集驹索搀信息论与编码第四章信息论与编码第四章

则j的取值范围为

式⒆为各项之和，都可取而又都可取值为，所以相同数值j的出现不止一次，也就是在个码字序列中码符号总长相等的码字序列不止一个，令为个，换句话说，就是把总长度为j的序列的数目记为，例如由唯一可译码三个码字所组合成的长度的序列共有7种：

101001，100101，011001，010011，001101，001011，010101

a1a2a3，a1a3a2，

a2a1a3，

a2a3a1，

a3a1a2，a3a2a1，a2a2a2

因此：式（19）可以合并：

将代入上式：

对于所有正整数n，上式都要成立，当时

所以必须有：证毕

蕊岁描简近灌尸攫碳擒沪踪筛气倍拔宴昆酷缔会奋骆冶行雅忌钦学捣改蝎信息论与编码第四章信息论与编码第四章§4.4变长信源编码定理平均码长：一个信源符号所需的平均码符号数为：可见：越短，越大，信息传输效率就越高，因此，我们总希望编出来的码平均码长最短，可作为衡量唯一可译码的有效性高低的一个标准。

昼养探拢碟矩勇扶磕涤口度恶肪契刘咬殊曾孪表姑病宋佣扬够搪侨橡串赂信息论与编码第四章信息论与编码第四章

定理4.3，若一个离散无记忆信源具有熵为，并有r个码符号的符号集，则总可找到一种无失真编码方法，构成唯一可译码，使其平均码长满足：下界证明：由证明过程知，上述等式成立的充要条件是：

可见，只有当选择每个码长：时，才能达到这个下界值,式中必须为正整数，每个必须呈现的形式（是正整数）。奶添送巴暂淖倦疆枫量糙韶窘次钝眶浸亿或锨姑遮袭诅曹是坍孵鞋屡狙蓟信息论与编码第四章信息论与编码第四章上界证明：只需证明在上界与下界中间可以找到一种唯一可译码就行。在如下区间取之整数

⒇

证毕信源给定，H（S）确定，那么，该信源的唯一可译码的平均码长的下界值也就随之确定，信源编码的有效性的限度也就确定了，在不改变编码的对象，即信源本身的统计特性的情况下，单靠改变编码方法来继续提高有效性是无潜力可挖了。黑姑真铱裕翅衰写季姥贮烦宣习榔变草奖在依卫免毕搁几拨踌蓟粒泣这匝信息论与编码第四章信息论与编码第四章定理4.4离散无记忆信源S的N次扩展信源，熵为，并有码符号集。对信源进行编码，总可以找到一种编码方法，构成唯一可译码，使信源中每个信源S中每隔信源符号所需的码字平均长度满足：或者且式中：令N＝1就是定理4.3证明：用SN替代定理4.3中的S，得：，其中是以r进制为单位的扩展信源SN的熵。代入上式结论可推广到平稳遍历的有记忆信源（如马尔可夫信源）

酌嗓溯汇哩哇梦犊停爷烬雀溅腕蝉括利踢也策置娶册销曳滚验服闻誊郧稍信息论与编码第四章信息论与编码第四章以上分析表明，要进一步提高编码的有效性，必须考虑到信源符号间的依赖性，以减少信源每发一个符号所携带的平均信息量，缩短平均码长的长度。考虑的依赖性越仔细，即记忆长度越长，平均码长就可能越短，编码就越有效。

如前所述，我们还可以用扩展信源的手段，达到数据压缩的目的，扩展的程度越高，压缩的效果越好。但增加了编码的复杂性（代价）。变长无失真信源编码定理（香农第一定理）也可这样来描述：设信源S的熵为H（S），无噪离散信道容量为C，于是，信源的输出可以进行这样的编码，使得在信道上传输的平均速率为每秒个信源符号，其中可以是任意小的正数，要使传输的平均速率大于是不可能的。编码效率：码的剩余度：

肃敢蜗抡植符口篙弘邦氏罐武蕴蒙斡苔侥没纺梧辙品券乏楷李硬琳韦恰惨信息论与编码第四章信息论与编码第四章§4.5变长码的编码方法香农编码：，可使不超过上界，但不一定保证是紧效码哈夫曼编码：1、将信源消息（符号）按概率大小顺序排队。2、从最小概率的两个消息开始编码，并给予一定的编码规则，如小概率的下支络编为1（或0），大概率的上支络编为0（或1），两相等，也按上、下支络给值。3、将已编码的两个消息对应概率合并，并重新按概率大小排队，重复24、重复3，直至剩两个符号为止。5、编成的变长码按后出先编的方法，从树根沿编码路线逆行至对应的消息（从最后级向前返回），得出各信源符号所对应的码符号序列。赁箍侯洱溶猖胖秤寸蝗草掉动征女祥壬滚凹用云拈萧沈玫震梯玛帕惮臃绿信息论与编码第四章信息论与编码第四章Huffman码一定是紧效码

证明：由H氏编码方法最后一步得到的缩减信源Sa必定只有r个符号.这r个符号的概率和必为1，且这r个符号分别只授于一个码符号(1,2,3…r)，所以缩减信源Sa对应的单义可译码Ca的平均码长一定等于1，平均码长等于1的单义可译码当然是最佳码。设某一缩减信源Sj，已找到一个最佳码Cj，其平均码长为，由编码方法，对于Sj中某一元素Sa（由前一个缩减信源中概率最小的r个符号合并而来的，且，对于信源的码，其平均码长为。由于在中除了这r个符号相应的r个码字比缩减信源Sj中的符号Sa相应的码字多一个r进制码符号外，其余码字长度都是相同的。所以满足以下关系：鸦楷桨彭吟倪德椿魔两根柄炙哭佃眠咋障靡啪爽阻挫拾柜软袭忽股遏象湿信息论与编码第四章信息论与编码第四章用反证法来证明：假设找到另一个码的最佳码，即其平均码长，设的码字为，各码字的长度分别为，再假设这些码字的排列次序是按照码字概率递减的次序，得（可以通过改变码字的标号来达到这一要求）。而在这些码中除了最后一个码符号不同外，其它码符号全部相同，也就是说有本层的码字长度相等如我们在中。，与上式相比由假设，应有：