当前课程知识点:信息论 > 第三章 信源的熵率、冗余度与马尔科夫信源编码 > 第十四讲 Huffman编码 > 第十四讲 Huffman编码课程视频
各位老师同学大家好
上一讲我们讨论了
变长编码的平均码长相关的基本概念定理
大家已经明白
使得平均码长尽量的接近信源熵
能实现编码效率与能量节省
二者之间的良好折中
平均码长与信源熵之间的关系告诉我们
如何实现最优编码的基本思想
与有效的途径
基于该思想
本讲我们主要讨论最优编码
尤其与大家一起讨论
Huffman码编码的详细过程
希望大家能熟练掌握
最优编码是凡能保证传输一定的信息量
且码字的平均长度为最短的码字集合
该码意味着采用最优编码的等效信源
发出的平均信息量达到最大
或者说在不改变信源的条件下
采用最优编码后
编码效率必然是最高的
根据信源字母概率的统计特性
将信源符号集合中
出现概率大的符号编成较短的码字
而对那些出现概率小的符号
编成较长的码字
从而使得平均码长最短
为了实现此目标
我们重点给大家介绍 Huffman编码
该码是建立在以下两个定理的基础上
根据这两个定理
本讲主要讨论二元数字的情况下
Huffman编码的详细过程
定理1
对任意给定的离散无记忆信源
存在一个最优的二元前缀码
该码中最少发生的两个码字
必须具有相同的长度
且码中相同长度的码字
有两个或者两个以上时
其中必有两个码字的差别只在最后一位
定理2
设C是某信源经缩减后得到的
缩减信源的最优前缀码
将C中的信源中最小的概率的两个字母缩减
得到的字母所对应的码字后各加0与1
作为原信源的最小概率的两个码字
其余码字不变
则这样得到的码C对信源也是最优的
在Huffman编码过程中
利用了构成信息序列的符号
出现的概率统计特性
对出现概率较大的符号赋予短码
对出现概率较小的符号赋予长码
使平均码长最短
这是一种编码效率很高的变长编码方法
Huffman编码方法的具体步骤如下
将n个信源消息符号按概率大小
依次进行排序
如式(1)所示
对两个概率较小的信源
分别赋予0和1两个码元
然后将这两个概率相加
作为一 个新的符号概率
与其他符号重新按概率大小排列
3 对重排后两个概率最小的符号
进行重复步骤2的过程
4不断继续上述过程
直到最后两个符号分别赋予0和1为止
5从最后一级开始向前返回
这就得到各个信源符号所对应的码元序列
考虑到Huffman编码方法
给出的码字不是唯一的
因为每次赋予两个概率最小的符号0和1时
也可以赋予1和0
这样编码后的各符号码字将会不同
但码字的长度是一样的
此外
将两个概率最小的符号合并后
的新符号的概率与其它信源符号的概率相等时
重新排列时新符号的位置次序
可以放在相等概率符号的上面
也可以放在下面
不同的编码方法
将会得到不同的Huffman码字
相应的码字的质量也是不一样的
通常将合并后的符号放在上面
以减小符号合并的次数
得到码字的方差较小的Huffman码
下面我给一个具体的实例给大家介绍一下
Huffman编码的详细过程
请大家一定要做好笔记
设单符号离散无记忆信源如(2)式所示
要求对信源进行二进制Huffman码
编码过程如下
编码结果为
1 001 011 0000 0100
0101 00010 00011
在表中读取码字的时候
一定要从后向前读
此时编出来的码字
才是可分离的最优前缀码
若从前向后读取码字
则码字不可分离
Huffman码性能分析
信源熵为2.55bit/s
平均码长为:2.61bit/s
编码效率为:97.7%
实际测试表明
相对于shannon编码
哈夫曼编码效率提高了12.7%
注意
哈夫曼的编码方式并不唯一
每次对缩减信源两个概率最小的符号
分配0和1的码元是任意的
所以可得到不同的码字
只要在各次缩减信源中
保持码元分配的一致性
即能得到可分离码字
不同的码元分配
得到的具体码字不同
但码长ki不变
平均码长也不变
所以没有本质区别
缩减信源时
若合并后的新符号概率
与其他符号概率相等
则编码方法方式来说
这几个符号的次序可任意排列
编出的码字都是正确的
但得到的码字不相同
不同的编码得到的码字长度ki
也不尽相同
那现在摆在我们面前的问题是
这两种方式编码所得到的码字
究竟哪种码字的性能好呢
要回答这个问题
请大家看下面例子
即用两种不同的方法
对其进行二进制Huffman编码
然后对其性能进行分析
显然
二进制Huffman码编码的方法
一 参看表1
二进制 Huffman码编码的方法二 参看表2
方法一
合并后的新符号
排在其它相同概率符号的后面
方法二
合并后的新符号
排在其它相同概率符号的前面
该两种编码哪一种决策更好呢
如何衡量这两种 Huffman编码的性能呢
两种编码的平均码长是一样的
都是2.2
然后我们不妨计算一下
平均码长的方差
计算结果表明
第二种编码方法的码长方差要小许多
这就意味着第二种编码方法的码长变化较小
比较接近于平均码长
第一种方法编出的5个码字
有4种不同的码长
第二种方法编出的5个码字
只有2种不同的码长
显然第二种编码方法更简单
更容易实现
所以更好
评述
在哈夫曼编码过程中
对缩减信源符号按概率
由大到小的顺序重新排列时
应使合并后的新符号
尽可能排在靠前的位置
这样可使合并后的新符号
重复编码次数减少
使短码得到充分利用
最优编码是针对稳恒信源序列的
而且信源的随机统计特性是已知的
在实际中
信源一般是非稳恒的
因此必须采取自适应的措施
跟踪信源的统计特性
使得最优编码的性能
适应信源统计特性的变化
好 今天我们就讲到这里
-第一讲 信息论课程介绍以及信息论的概念 描述
--课件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
--杰青讲座
--院士的讲座