网站首页  词典首页

标题	香农编码的优化算法与哈夫曼编码探究
范文	孔元君+宋玉 摘 要：香农编码作为一种十分重要的变长信源编码的编码方案，具有重要的指导意义.但其在实际应用中也存在着效率低的不足.本文针对这一缺点，通过判断相邻码字之间是否互为前缀对香农编码进行了优化，并进行了仿真对比分析。最后，通过引入有‘最佳编码之称的哈夫曼编码，与香农编码及其优化算法进行对比，说明哈夫曼编码策略的确是一种更加高效、更为可行的编码方法。 关键词：香农编码；信源编码；哈夫曼编码；最佳编码 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.
随便看	浅谈苏教版初中数学实践活动中学生能力的培养 基于心理学视角下多媒体技术在初中数学教学中应用策略 浅谈数学方法论在初中数学教学中的运用 契合特点，打造具有学科属性的全新数学课堂 数学创新教学中培养学生思维的批判性 数形结合思想在初中数学教学中的应用研究 翻转课堂理念下初中数学信息技术教学模式的应用探究 化归思想在初中数学教学中的运用 浅谈几何直观在初中数学教学中的运用 初中数学课堂教学中有效诱导学生发问 对“教学做合一”在初中数学中的应用之刍议 在实践中摸索，在摸索中前进 摭议初中数学课堂中有效使用多媒体的策略 对初中数学课堂习题课教学的思考和研究 试论“导学互动”教学模式对初中数学教学的作用 怎样转化学困生的一些尝试 数学思想在课堂教学中的实践路径与培养策略 初三数学教学有效教学的探索 谈如何走出初中数学复习课误区的策略 浅谈初中生数学自主学习能力的培养 关于初中数学后进生成因及对策研析 浅谈初中数学课堂教学中的师生互动 数学教学中的小故事 初中生数学课堂主动提问能力的培养策略 力求认识，掌握数学 caller display caller id caller ids callers' callers callfeature call feature call for call for sb call for sb to do sth call for sth callforwarding call forwarding call-girl calli calligrapher calligraphical calligraphically calligraphies calligraphy call-in call in call in a bond calling calling back 铤险 铤鹿走险 铥 铥铬 铦 铦兵 铦利 铦巧 铦袭 铦达 铦钢 铦钩 铦铓 铦锋 铦锐 铦锥 铦锷 铦颖 铧 铧和犁的并称 铧式犁 铧是铁打的 铧犁 铧锨 铧锹

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