当前课程知识点:信息论 > 第三章 信源的熵率、冗余度与马尔科夫信源编码 > 第十二讲 唯一可译码定理以及前缀码的构造 > 第十二讲 唯一可译码以及前缀码的构造视频
各位老师 同学大家好
上一讲我们讲了定长编码定理
定长编码有自身的很多缺陷
为了克服这些缺陷问题
本讲和大家一起讨论离散无记忆变长编码
变长编码有很多优点
首先我先给大家介绍一下码字的分类
码可分为两类
一是固定长度的码叫等长码
码中所有码字的长度都相同
二是可变长度码
变长码
码中的码字长度各不相同
奇异码和非奇异码
若信源符号和码字是一一对应的
则称这种码为非奇异码
若不是一一对应
则称为奇异码
唯一可译码
任意有限长的码元序列
只能被唯一地分割成一个一个的码字
这种码称为唯一可译码
唯一可译码又分为
非即时码与即时码两种
非即时码
即接收端收到一个完整的码字后
不能立即进行译码
还需要等下一个码字开始接收后
才能判断是否可以译码
即时码
即时码也称非延长码或非前缀码
即任意一个码字都不是其他码字的前缀部分
如果一个码组中
任一个码字都不是另一个码字的延长
或者说
任何一个码字后加上若干码元后
都不是码组中另一个码字
即时码总可以放在一个树形图上
因此我们考虑借助于树形图来构造即时码
考虑用树形图来构造即时码
在变长码中
若没有任何一个码字是其他码字的前缀
该码字就叫做即时码
请大家参照图
即时码图与非即时码图
需要给大家讲清楚树形图
以及即时码如何与树形图建立对应关系
树根 码字的起点
树枝数 码的数量
节点数 码字的一部分
节数 码字的长度
叶子 码字
同层的节点相互之间叫作兄弟节点
相邻不同层节点相互之间叫做父子节点
从如图所示的树形图上可以看出
即接收到一个完整的码字后不能立即译码
还需要等下一个码字开始接收后
才能判断是否可以译码
比如 1 10 100 1000
就是非即时码
参看非即时码
那现在摆在我们面前的一个问题是
如何构造前缀码呢
前缀码存在的条件是什么呢
为了回答这些问题
本讲首先给出Kraft定理
Kraft定理
设含有K个信源字母的信源
要用J个字母的码字母表
进行变长编码
则当且仅当各字母的长度l1 l2
等满足Kraft不等式(1)时
才存在前缀码
式子(1) 清楚的表明
匹配概率之和也小于1
该定理是存在前缀码字的充分必要条件
下面请容许我给大家证明一下这个定理
对于充分必要条件
一般而言先证明必要性
必要性是假定结论成立推出条件
而充分性是由条件推出结论
基于以上的考虑
我们先给大家证明必要性
请大家参照详细的证明过程
再证明充分性
Craft不等式给出的限制
也是所有唯一可译码必须满足的条件
此外
我与大家再讨论一下
唯一可译码定理 如(4)式所示
显然式匹配概率的和也必须小于1
其中K与J 是源字母与码字母的总数
lk是唯一可译码的长度
小结
该定理表明
对任何唯一可译码
可在不改变码字长度的条件下
得到相应的前缀码
换句话说
为了使得唯一可译码具有前缀码的性质
不会给码字长的下界增加限制
好 这一讲我们就讲到这里
-第一讲 信息论课程介绍以及信息论的概念 描述
--课件PPT
-第一章 学习材料
--思考与扩展
-第一章 作业
--第一章 作业
-同步阅读训练 关于中国新型肺炎数学模型的建立
--同步训练
-第二讲 离散熵 离散互信息 连续随机变量的熵与互信息
--第二讲 离散熵 离散互信息 连续随机变量的熵与互信息视频
--课件PPT
-第三讲 熵函数的定义
--第3讲PPT
-第四讲 熵函数的上凸性证明 案例的思考与扩展 熵函数的进一步讨论
--第四讲 熵函数的上凸性证明 案例的思考与扩展 熵函数的进一步讨论视频
--课件PPT
-第五讲二元变量的联合熵 联合熵的几种情形的讨论 联合熵不等式的证明
--第五讲 二元变量的联合熵 联合熵的几种情形的讨论 联合熵不等式的证明视频
-第六讲 互信息的定义 互信息的公式推导 平均互信息的几种情形的讨论
--第六讲 互信息的定义 互信息的公式推导 平均互信息的几种情形的讨论视频
-第七讲多变量平均互信息关系式证明 互信息函数的性质 互信息函数公式的进一步研究
--第七讲 多变量平均互信息关系式证明 互信息函数的性质 互信息函数公式的进一步研究视频
-第八讲 连续随机的熵函数与互信息
-第九讲 鉴别信息
-第二章 课程课件PPT
--第二章 学习材料
-第二章 作业练习与思考
--第二章 作业
--课外材料补充
-第十讲 平稳 离散 无记忆稳恒信源
-第十一讲 定长编码定义与渐进等同分割定理
-第十二讲 唯一可译码定理以及前缀码的构造
-第十三讲 变长编码的平均码长定理
-第十四讲 Huffman编码
-第十五讲 平稳有记忆Markov信源
-第十六讲 Markov信源的变长编码以及案例介绍
--第十六讲 Markov信源的变长编码以及案例介绍课程视频
-第三章 学习材料课件
-第三章 作业练习与思考
--第三章 作业
-第十七讲 信道、 信道模型以及分类
-第十八讲 前向信道状态转移概率矩阵引入与平均互信息
--第十八讲 前向信道状态转移概率矩阵引入与平均互信息课程视频
-第十九讲 离散无记忆信道的信道容量以及传输速率
-第二十讲 信道容量解的充分必要条件以及优化方法的介绍
--第二十讲 信道容量解的充分必要条件以及优化方法的介绍课程视频
-第二十一讲 对称离散无记忆信道
-第二十二讲 准对称离散无记忆信道 删除信道 案例分析
--第二十二讲 准对称离散无记忆信道 删除信道 案例分析课程视频
-第二十三讲 准对称离散无记忆信道案例分析
-第二十四讲 串联信道的信道容量
-第二十五讲 并联信道信道分类
-第二十六讲 连续信道
-第二十七讲 高斯分布函数在信道估计中的应用
-第二十八讲 重要定理的证明过程(重点关注证明过程技巧 如等效 与对数不等式的应用)
-第二十九讲 并联信道的信道容量费用函数优化建模以及在MIMO中的应用(5G 6G中应用)
--第二十九讲 并联信道的信道容量费用函数优化建模以及在MIMO中的应用课程视频
-第三十讲 模拟信道下的信道容量费用函数
-第四章 学习材料课件
--课堂课件PPT
--正交变换
-第四章 课外阅读材料 衰落信道描述 优化方法及介绍 5G 6G介绍
-- 课外阅读材料1
--阅读材料3
-第四章 作业练习与思考
--第四章 作业
-第三十一讲 熵压缩编码与信源的信息速率失真函数
-第五章 学习材料课件
--学习材料的补充
-第五章 作业
-第三十二讲 错误概率与译码似然准则
-第三十三讲 有噪信道编码以及最大似然准则引入
--菲诺不等式的讨论
--课件PPT
-第三十四讲 信道编码基本概念介绍
-第三十五讲 线性分组码的数学支撑 线性空间的引入
--第三十五讲 线性分组码的数学支撑 线性空间的引入课程视频
--课件PPT
-第三十六讲 线性分组码的生成矩阵与校验矩阵引入
-第三十七讲 伴随式 、错图样与译码
--课件PPT
-第三十八讲 循环码及其多项式描述 生成多项式引入
--第三十八讲 循环码及其多项式描述 生成多项式引入课程视频
--课件PPT
-第三十九讲 循环码及其矩阵描述
--课件PPT
-第四十讲 循环码的构造
--课件PPT
-第四十一讲 卷积码基本概念介绍
--课件PPT
-第四十二讲 卷积码及其图形描述 篱笆图 树形图
--第四十二讲 卷积码及其图形描述 篱笆图 树形图 课程视频
--课件PPT
-第四十三讲 卷积码的译码过程
-第六章 学习材料课件
--第六章 学习材料
-第六章 课外阅读材料 卷积码 阅读材料
-第六章 作业练习与思考
--第六章 作业
-翟永智关于Fano不等式以及Shannon第二定理 抗干扰定理知识点的详细解读
-第四十四讲 最小鉴别信息原理与最大熵原理
-第七章 学习材料课件
--第七章 学习材料
-第七章 作业练习与思考
--第七章 作业
-强化训练
--强化训练
-第二三四章计算证明题,请大家点击并下载 2020-2021期末考试试题以及答案
--2020-2021信息论期终考试题(命题人 翟永智 郑文秀 冯丹)
-2020年专家讲座PPT
--杰青讲座
--院士的讲座