《应用编码与计算机密码学》第一章.pptVIP

第1章 变长码概述 1.1 字（Word）与语言（Language） 1.2 唯一可分码与McMillan定理 1.3 前缀码与Kraft定理 1.4 应用编码三个基本目标 1.1 字与语言 字母表∑：非空有限集合 定义连接运算 字w：字母表上中若干个元素的连接 空字：连接运算的单位元 字的长度：|w| 1.1 字与语言 字的各部分表示 前缀 后缀 子串 真前缀 子序列 1.1 字与语言 例1.1.1 设∑表示英文中的26个小写字母，即∑=（a，b，……，z）。则 w1=word w2=aaa w3=λ w4=ee……e 就是字母表上4个长度分别为4、3、0和无限的字，即 l (w1) = 4, l (w2) = 3, l (w3) = 0, l (w4) = ? 1.1 字与语言 定理1.1.1 设∑(|∑|=m(1))是一个有限字母表，ｎ是一个给定的正整数，则有 （1）|∑n| = mn； （2）|∑n| =( mn+1 -1) / (m-1)。 1.2 唯一可分码和Mcmillan定理 定义1.2.1 设∑是一个字母表，C? ∑+是∑上 任意一个语言。如果对于任意正整数 ｎ,ｍ ?1 c1,c2,……,cn ;c1’,c2’,……,cm’， 当 c1,c2,……,cn = c1’,c2’,……,cm’时, 1.2 唯一可分码和Mcmillan定理 定义1.2.1 则必有 ｎ＝ｍ 且 ci=ci’ i=1,2,……,n。那么称语言C为字母表上的一个码或唯一可分码。 1.2 唯一可分码和Mcmillan定理 定义1.2.2　 设是一个字母表，是一个任意语言。如果C中每一个字的长度都相同，则称C为一个定长码。虽然，一个一致码的任意子集合必是一个定长码。 1.2 唯一可分码和Mcmillan定理 定义1.2.3 设S = { s1, ……, sq} 是一个有限集合，称为信源字母表。设C是字母表 的一个码。如果存在一个从S到C的一一对应f，即 　　　　　　　f : S ? C 1.2 唯一可分码和Mcmillan定理 定义1.2.3 是一个双射。也就是把信源字母表S中的每一个信源字母唯一对应C中的一个码字， ，那么有序对（C，f）就称为信源字母表S的一个编码(Encoding) 1.2 唯一可分码和Mcmillan定理 定义1.2.4 设C是字母表?上的一个码。如果C不被包含在?上任意另外一个码中，则称C为 ?上的一个极大码。即，设C’是?上的任意一个码，且C ? C’，则C = C’。 1.2 唯一可分码和Mcmillan定理 定理1.2.1 设C = {c1，c2 , ......, cq }是r 个字母的字母表?上的一个码，且 l (ci) = li , i = 1,……,q 。那么 　　 1.2 唯一可分码和Mcmillan定理 定理1.2.1 (1) （McMillan定理） （称为Kraft不等式）; (2) ,当且仅当C一个极 大码 1.3前缀码与kraft定理 定义1.3.1 设Alice发送给Bob一个码字序列c1,…,cm, ci? C是一个码。如果当Bob接收到码子序列c1……cm的同时就能唯一确定c1,c2……cm是C中的码字。 则我们称码C是瞬时性的 。 1.3前缀码与kraft定理 定理1.3.1 如果一个码C中的任意一个码字C均不是C中其它码字的真前缀，则称C是一个前缀码。 1.3前缀码与kraft定理 定理1.3.2 一个码是瞬时的，当且仅当它是一个前缀码。 1.3前缀码与kraft定理 定义1.3.2 设C字母表?上的一个前缀码。如果对任意字w??*\C,C ? {w}不再是一个前缀码，则称C是一个极大前缀码。 1.3前缀码与kraft定理 定理1.3.3 设?是一个含有r 个字母的字母表。 (1) （Kraft定理）存在? 上的一个前缀码C = {c1,c2,……,cq}的充要条件是C的码字长度序列l(c1) = l1, l(c2) = l2,… l(cq) = lq, 满足Kraft不等式，即 1.3前缀码与kraft定理 定理1.3.3 (2) 前缀码C是极大前缀码的充要条件是