多进制霍夫曼编码方法及最优性证明.pdf

学术研究 曰esearch 多进制霍夫曼编码 方法及最优性证明 郑世林 (咸宁学院物理系，湖北咸宁，47000) 【摘 要】信源编码最常用的霍夫曼可变长编码是性能最优的唯一可译即时码。在讨论编码方法时常以二进制为例进行。 多进制的霍夫曼编码如何进行，怎样证明得到的编码一定是平均码长最短的唯一可译即时码，是本文讨论和证明的主题。 【关键词】霍夫曼编码 扩张信源和扩张编码 最优编码 1中图分类号]TN.7 [文献标识码】A Huffmancodingofmanyentityanddemonstratingoftheoptimization ZhengShilin (DepartmentofPhysicsXianningCollege,HubeiXianning,437000,China) [Abstract]Inthispaper,aHuffmanexpandingsignalandcodingconcepthavebeenintroduced.Amathematicalmodelisdevel- opedtodescribethecodingprocess.Furthermore,theoptimizationofvariableHuffmancodinghasbeenmathematicallydemonstrated. [Keywords]Huffmancodingexpandingsignalandcodingcodingoptimization l 序言 2 多进制霍夫曼编码过程 信息论和编码理论中，主要讨论的是通信的有效性和可 我们从一个具体的编码实例开始，介绍多进制霍夫曼可 靠性因素，其中少不了关于霍夫曼(Huffman)编码的内容。在 变长编码的方法，进而建立霍夫曼编码的数学模型。我们给 有关信息论的教材和参考书籍中[1]2[13141，对于可变长编码，无 一例外的都讲到霍夫曼编码是效率最高的唯一可译即时码， 断个信源模型:GkPI一{立孟。，及，，及，，及，戈，找，。 即平均码长最短的唯一可译非延长码。我们从许多具体编码 该信源有q个信息元，分别对应着p(ai)的概率分布。r 实例的验证中，认识到这一结论确实正确。但得到这一结论 表示编码代码符号数，即进制数。假定q=9，编码代码符号 应该有数学上的一般性证明，不能仅凭有限个数的具体实例 数r=4，具体概率空间分布按照由大到小顺序排列，列入表 来取代理论分析。本文从一个具体的霍夫曼可变长编码实例 1中的第一列。后面奇数列的概率值是在编码过程中变换得 人手，介绍多进制霍夫曼编码的方法，认识编码过程特征，在 到的，即第一列取最小的q-k(r-1)个概率值相加后又顺序排 此基础上介绍霍夫曼扩张信源和扩张编码的概念01，建立霍 列。若q-k(r-1)=0，则取r-1个相加，若q-k(r-1)=1，则 夫曼编码过程的数学模型，据此展开讨论，并力图给出一般 表1 多进制霍夫曼可变长编码的数据压缩表、编码表 J险数学证明。 概率 码字 概率 码字 概率 码字 0.22 1 0.22 1 .45 0