网站首页  词典首页

请输入您要查询的论文：

　

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



摘 要：香农编码作为一种十分重要的变长信源编码的编码方案，具有重要的指导意义.但其在实际应用中也存在着效率低的不足.本文针对这一缺点，通过判断相邻码字之间是否互为前缀对香农编码进行了优化，并进行了仿真对比分析。最后，通过引入有‘最佳编码之称的哈夫曼编码，与香农编码及其优化算法进行对比，说明哈夫曼编码策略的确是一种更加高效、更为可行的编码方法。
关键词：香农编码；信源编码；哈夫曼编码；最佳编码
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