那么对任何 我们定义 (3.1.2)
那么称 是 的扩张编码。这时 是一个从(Xn)*到(U)*的映射。
(2)如果 是一个从X到U*的变长码,如果 是一个消息字母,那么对任何 定义
那么称 是 的扩张编码.这时 是一个从X*到U*的映射。
(3)无论是定长编码还是变长编码,它们的扩张 都是一个从(Xn)*(或X*)到U*的映射,如果 是一个1-1映射,那么我们称 是一个惟一可译码(或可还原码)
方法
方式（手段）：多媒体；
方法：讲授法。
教学
内容
及时
间分
配第Βιβλιοθήκη 节课：3.1信源编码问题；-------------------------45分钟
第二节课：
3.2前缀码与即时码；---------------------30分钟
3 3信源变长编码问题。------------------15分钟
例题、练习题
定理3.1.1惟一可译码与1-1码有以下关系:
(1)无论是定长编码还是变长编码,惟一可译码必须是一个1-1码.
(2)如果 是一个1-1定长码,那么 是一个惟一可译码.
(3)变长的1-1码,不一定是惟一的可译码.
3.1.3信源变长码的编码问题
定义3.1.4如 是一个信源, 是一个变长的编码,那么对任何 , 是U*中的一个向量,我们记 是 的向量长度.那么定义 为变长码f的平均码长。
东北电力大学
教案封皮
开课单位
理学院信息与计算教研室
课程名称
信息与编码
授课教师
常志文
授课对象
信息与计算专业121
选用教材
信息论与编码理论（沈世镒）
总学时
60（含课内实验10学时）
课次
6
第3章
第1~3节信源编码问题，前缀码与即时码，信源变长编码的编码问题。
教学目的
及要求
教学目的及要求：
要求学生掌握信源编的产生及要解决的主要问题；
(2)记 为定长编码的码字集合。称 为编码的信号体积.而称
为编码 的码率.
定义3.1.7(信源序列编码的可达速率)称R是信源序列 的一个可达速率,如果存在一个数列 (当 时)及存在一组编码序列 ,使以下条件成立.
(1)对任何
(2)对任何 其中
定义3.1.8(信源序列的最小可达率和它的编码问题)对已给的信源序列 ，全体可达率的最小值(或下确界)称为该信源序列的最小可达速率.信源序列的编码问题就是求它的最小可达率.
3.1.2定长编码与变长编码
定义3.1.2如果 是从Xn到Um的映射,m,n是两个固定的正整数,那么称 是从Xn到Um的定长编码。定长码又称分组码,它表示编码是一段一段地进行,各消息与信号段的长度都相同.
如果 是从X到U*的映射,那么称 是一个变长编码(或不定长编码)。
定义3.1.3(1)如果 是一个从Xn到Un的定长码,记 ,其中
成立
3.3.3无记忆信源平均码长的上、下界估计
定义3.3.1称 是由 确定的无记忆信源序列,如果对任何,如果对任何 有 是X的 维乘积空间,而且 。
定理3.3.3如果 是由 确定的无记忆信源, 是消息字母表的字母数,那么最优变长即时码 的码长估计式为
其中 是 的概率分布
编码是一种对应关系
1-1对应与唯一可译关系。
衡量编码效率的方法之一就是平均码长。
平均误差为错误概率。
码率即编码效率。
注意：前缀码的定义与字义相反。
Kraft不等式说明对于指定一组码字长度的前缀码是否存在。
定义3.1.5(变长信源编码问题)如 是一个给定的信源,变长信源编码问题是:求惟一可译的变长码 ,使 为最小.也就是求惟一可译的变长码 ,它对其他惟一可译的变长码 ,总有
成立,这时称 为 的最优变长码。
3.1.4信源序列的定长编码问题
定义3.1.6编码的平均误差与可达速率定义如下:
(1)对固定的信源 ,与编、译码函数 ,它们的平均误差为
掌握前缀码与即时码以及变长编码理论。
教学重点处理安排
教学重点：
前缀码与即时码；
处理安排：
通过实例与原理说明前缀码与即时码。
教学难点处理安排
教学难点：
前缀码与即时码的区别；
变长码与定长码的不同；
处理安排：
由定义以及唯一可译码与即时可译码区别说明前缀码与即时码的区别；
由平均码长说明变长码的优点。
教学方式、
例题：平均码长计算实例，非唯一可译码实例，唯一可译但非即码实例。
作业、思考题
P72，3.2 3.3
教案
内容
备注
第三章信源编码
3.1信源编码问题
3.1.1信源编码
定义3.1.1我们称 是一个1-1码,如果 ,必有 。如果 是一个1-1码,那么我们又称 满足1-1性.
为了使编码是可还原的,编码 必须满足1-1性.但我们从下文可看到,1-1码不一定是可还原码.
3.3信源变长码的编码定理
3.3.1最优变长码平均码长的下界估计
最优变长码平均码长的下界估计式由以下定理确定.
定理3.3.1如果 是给定信源, 是即时码,那么
,
其中 上取对数为 为底的熵函数,而等号成立的充分必要条件是
证明略
3.3.2最优变长码平码长的上界估计
定理3.3.2对于已给信源 ,它的 元最优变长即时码 必有
3.2前缀码与即时码
3.2.1惟一可译变长码的构造成
定义3.2.1我们称一个码是即时码,如果在任意的码串中,从左到右,如果一个码字出现,就可惟一译出这个码字所对应的信源字母.
定义3.2.2两个字符串 与 ,称 是 的前缀,如果 ,且有
成立.
如果任何一个码字都不能是另一个码字的前缀称这个码是前缀码.
定理3.2.1前缀码一定是即时码,反之亦然.
.
3.2.2 Kraft不等式
定理3.2.2(Kraft不等式)如果 是一个变长码,它的码元集为C,它的码字长度分别是 ,记为 ,如果 是一个即时码,那么它必满足Kraft不等式 。
反之,如果有一组数 满足Kraft不等式,那么必存在一个码长为 的即时码.
以上定理说明了满足Kraft不等式的 ,必存在即时码使它的长度为 .反之长度满足Kraft不等式的码不一定是即时码.