网站首页  词典首页

请输入您要查询的论文:

 

标题 香农编码的优化算法与哈夫曼编码探究
范文 孔元君+宋玉



摘 要:香农编码作为一种十分重要的变长信源编码的编码方案,具有重要的指导意义.但其在实际应用中也存在着效率低的不足.本文针对这一缺点,通过判断相邻码字之间是否互为前缀对香农编码进行了优化,并进行了仿真对比分析。最后,通过引入有‘最佳编码之称的哈夫曼编码,与香农编码及其优化算法进行对比,说明哈夫曼编码策略的确是一种更加高效、更为可行的编码方法。
关键词:香农编码;信源编码;哈夫曼编码;最佳编码
1 香农编码
1.1 香农编码原理
美国的工程师香农于1948年在美国贝尔实验室期刊上刊登发表了一篇长文《通讯的数学原理》[1] 。香农编码是一种不定长编码方式,通常将频繁出现的消息信号编成短码,不经常出现的消息信号编成长码,从而有效地提高通信效率。香农第一定理指出了
平均码长与信源字符之间的对应关系,同时也指出:可以通过信源编码方式使平均码长达到极限。
香农第一定理指出,每个码字的长度Ki应该满足下式:
-log2 p(xi)≤ Ki <1-log2 p(xi) (1)
就能得到这种码字。这种编码方法就称作香农编码 。
1.2 编码步骤
二进制香农编码的步骤如下:
(1)将信源符号按概率从大到小的顺序排列
(2)对第j个前的概率进行累加得到pa(aj)
(3)由-logp(ai) ki<1-logp(ai)求得码字长度ki
(4)用二进制方式表示pa(aj),并取小数点后的ki位当作符号ai的编码码字。
1.3 仿真实验
假设有7个信源符号,其概率分布为 {0.20,0.19,0.18,0.17,0.15,0.10,0.01},在Visual Studio 2012上运行,其编码后的码字和编码效率如图2所示。
2 哈夫曼编码
2.1 哈夫曼编码原理
哈夫曼编码算法是满足前缀条件下,所得到的平均二进制码长最短的一种编-源表示,它将较短的码字分配给大概率的信源符号。算法是:在信源符号集合中,首先将两个最小概率的信源输出合并为新的输出,其概率是兩个相应输出符号的概率的和值。重复该过程,直到仅仅剩下一个合并输出为止,这个最后的输出符号概率为1。
例如,对信源符号概率0.4,0.2,0.2,0.1,0.1的编码过程如表2所示
通过上表的对信源缩减合并过程,从而完成了对信源的霍夫曼编码。
2.2 编码步骤
编码步骤主要分为两步,首先是码树形成:对信源概率合并,形成编码码树。第二是码树回溯:在码树上调配编码码字,最终得到哈夫曼码。
1、码树构造流程:将信源概率依据从小到大的顺序排序,同时建立到相应位置的索引。然后依照上述规则进行信源合并,再对信源依次排序,并建立新的位置索引,直至结束合并。在该过程中每一次都把经过排序的信源概率存放入矩阵G中,位置索引放入矩阵Index中。
表2 哈夫曼编码过程
2、码树回溯流程:在码树上调配码字,并最终得到Huffman编码。从索引矩阵M的尾行向前回溯。
2.3 仿真实验
假设有7个信源符号,其概率分布为 {0.20,0.19,0.18,0.17,0.15,0.10,0.01},在MATLAB 2014a平台上仿真实现,实验结果如图3所示。
3 结论
从上述实验可以看出,对同一信源概率矩阵,传统香农编码的效率为0.830,经过文献法改进,剔除了先限定每个码字的码长这一过程,通过判断码字之间是否互为前缀来确定码字,去除了大量冗余,编码算法的效率达到了0.891,提高了6%。最后,哈夫曼编码作为最佳编码的代表,其编码效率可以达到0.960,可见的确是一种更为高效可行的编码方式。
参考文献
[1] Shannon C E.A Mathematical Theory of Communication[J].The Bell System Technical Journal,1948,27:379—423
[2] 邵军花, 刘玉红, 邸敬,等. 香农编码的优化算法研究[J]. 兰州交通大学学报, 2010, 29(6):110-113.
[3] Robert J,M The theory of information and coding [M].北京:电子工业出版社,2003:84—91
[4] Travis G.Shannon coding[J] Information Processing Letters,2007,102(2):15—20.
[5] Yang Yan,Qian Tao.Co—dimension—P Shannon sampling theorems[J].Complex variables and elliptic equations。2007,52(1):46—55.
随便看

 

科学优质学术资源、百科知识分享平台,免费提供知识科普、生活经验分享、中外学术论文、各类范文、学术文献、教学资料、学术期刊、会议、报纸、杂志、工具书等各类资源检索、在线阅读和软件app下载服务。

 

Copyright © 2004-2023 puapp.net All Rights Reserved
更新时间:2025/3/15 20:52:47